What is the use of namespace std in C++

Let's start with a problem to explain what namespaces are. We all know that we can't have functions, classes or any other kind of data that have the same name. Let's say that we have two libraries that both add a function, let's say print(). They both give a different function, but in naming they are indistinguishable. That's where namespaces come in. A namespace is like adding a new group name to which you can add functions and other data, so that it will become distinguishable.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

namespace bla { void print() { // function bla::print() } } namespace blabla { void print() { // function blabla::print() } }

Now, as you can see, there are two functions with the name print, yet there is no naming conflict, because of namespaces. The first function would be called by using: bla::print() and the second with blabla::print().

std is an abbreviation of standard. std is the standard namespace. cout, cin and a lot of other things are defined in it. (This means that one way to call them is by using std::cout and std::cin.)

The keyword using technically means, use this whenever you can. This refers, in this case, to the std namespace. So whenever the computer comes across cout, cin, endl or anything of that matter, it will read it as std::cout, std::cin or std::endl.

When you don't use the std namespace, the computer will try to call cout or cin as if it weren't defined in a namespace (as most functions in your codes). Since it doesn't exist there, the computer tries to call something that doesn't exist! Hence, an error occurs.

C Program to check whether a graph contains a cycle or not

We will be using the following graph

As we know a graph may or may not contain a cycle i.e a graph which does not contain a cycle is called a tree. We can use either BFS (Breadth First Search) or Depth First Search (DFS) to check whether a graph contains a cycle or not .
So basically here we are carrying out the dfs of a graph and for each graph node we check if its adjaceny list contains a element or node that is already visited. A graph may have cycle if and only if if there exists a back link to node predecessor from its ancestors.
Here we will be using the same array visited as in DFS to keep track of the nodes that are visited.
Below is the C implementation of the same.

#include<stdio.h>
#include<stdlib.h>
int visited[10]={0,0,0,0};//take it to the no of nodes in graph ,or allocate memory dynamically
int flag=0;
struct node
{
    int a;
    struct node * next;
};
struct graph
{
    int v;
    struct node **array;
};
void addedge(struct graph *g,int s,int d)
{
    struct node*temp ;
    temp= (struct node *)malloc(sizeof(struct node));
    temp->a=d;
    temp->next=g->array[s];// adding the node at the starting of the list
    g->array[s]=temp;
}
void dfs(int x,struct graph *g)
{
struct node *temp;
if(visited[x]==1)
{
   flag=1;
   return;
}
else
   {
       printf("%d",x);
       visited[x]=1;

temp=g->array[x];
while(temp)
{
    dfs(temp->a,g);
    temp=temp->next;
}
   }
   return;
}

int main()
{
struct graph *g;
g=(struct graph *)malloc(sizeof(struct graph));
g->v=4;
g->array=(struct node **)malloc(5*sizeof(struct node*));
int i;
for(i=0;i<4;i++) //intializing the graph
{
    struct node *n;
    n= (struct node*)malloc(sizeof(struct node));
    n->a=i;
    n->next=NULL;
    g->array[i]=n;
}
addedge(g,0,1); //Creating the graph first here
addedge(g,0,2);
addedge(g,1,2);
addedge(g,2,3);
addedge(g,2,0);
addedge(g,3,3);
printf("DFs=\n");
dfs(2,g);
printf("\n");
if(flag)
printf("There exists a cycle");
else
printf("There does not exists a cycle");
return 0;
}

Output:

Program to implement Depth First Search/traversal in C 

We will be using the following graph :

As we know that the dfs of a graph is similar to the dfs of a tree with the only difference that the graph may have cycles too.

We will be using the same approach as in tree, We start from the starting and traverse its leftmost or rightmost children first and and then its children and so on before traversing its sibling nodes but as we are traversing a graph a node may have link to the already visited node that creates the cycle so that node may be repeated again and this process will continue on ..so inorder to avoid this ambiguity, we will be using an array "visited" to keep track of all nodes that are visited.

We will be using recursion to print all the nodes of the graph. We will first print the starting node then all its adjacent like nodes as passed on the recursive function unlike binary trees where we pass only tree->left and tree->right , Here we will pass all its adjacent elements from its adjaceny list and so on.

Below is the C implementation of the same:

#include<stdio.h>
#include<stdlib.h>
int visited[10]={0,0,0,0};  //take it to the no of nodes in graph ,or allocate memory dynamically
struct node
{
    int a;
    struct node * next;
};
struct graph
{
    int v;
    struct node **array;
};
void addedge(struct graph *g,int s,int d)
{
    struct node*temp ;
    temp= (struct node *)malloc(sizeof(struct node));
    temp->a=d;
    temp->next=g->array[s];// adding the node at the starting of the list
    g->array[s]=temp;
}
void dfs(int x,struct graph *g)
{
struct node *temp;
   if(visited[x]==0)
   {
       printf("%d",x);
       visited[x]=1;

temp=g->array[x];
while(temp)
{
    dfs(temp->a,g);
    temp=temp->next;
}
   }
   return;
}

int main()
{
struct graph *g;
g=(struct graph *)malloc(sizeof(struct graph));
g->v=4;
g->array=(struct node **)malloc(5*sizeof(struct node*));
int i;
for(i=0;i<4;i++) //intializing the graph
{
    struct node *n;
    n= (struct node*)malloc(sizeof(struct node));
    n->a=i;
    n->next=NULL;
    g->array[i]=n;
}
addedge(g,0,1); //Creating the graph first here
addedge(g,0,2);
addedge(g,1,2);
addedge(g,2,3);
addedge(g,2,0);
addedge(g,3,3);
printf("DFs=\n");
dfs(2,g);
return 0;
}

Output:

Program for Breadth First Search traversal of a graph in C
The graph used is shown below:

As we know the bfs traverses the tree or a graph across the width or say breadth of the graph. The bfs traversal of the graph is very much similar to the bfs of a tree with a difference that unlike trees graphs may have cycle too and we may traverse back to the previous visited node once again in the traversal if the next node that has to be visited has a link to the previously visited nodes.

So, We will be using an array "visit" to store the status of each node whether visited or not.
We will start from node '0' and visits its adjacent nodes using its adjacency list and store all its adjacent nodes in the queue provided its is not already visited using "visit" array, initially the queue contains the starting node i.e. 0

After that we process each element of the queue until it is empty 
The implementation of the above concepts is shown below :

#include<stdio.h>
#include<stdlib.h>
int visited[10];//take it to the no of nodes in graph ,or allocate memory dynamically
struct node
{
    int a;
    struct node * next;
};
struct graph
{
    int v;
    struct node **array;
};
void addedge(struct graph *g,int s,int d)
{
    struct node*temp ;
    temp= (struct node *)malloc(sizeof(struct node));
    temp->a=d;
    temp->next=g->array[s];// adding the node at the starting of the list
    g->array[s]=temp;
}

void bfs(struct graph *g)
{
    int i=0,v,f=0,r=0,c;
    struct node *temp;
int array[10],visit[5]={1,0,0,0,0};//we can initialize with only 1 also the rest will get by default to '0'
array[0]=0;
for(i=f;i<=r;i++)
{
    v=array[i];
    printf("%d",v);
    printf(" ");
    temp=g->array[v];
    while(temp->a!=v)
    {
        c=temp->a;
          if(visit[c]==0)
          {
             array[++r]=temp->a;
             visit[c]=1;
          }
        temp=temp->next;
    }
}

}

int main()
{
struct graph *g;
g=(struct graph *)malloc(sizeof(struct graph));
g->v=5;
g->array=(struct node **)malloc(5*sizeof(struct node*));
int i;
for(i=0;i<5;i++) //intializing the graph
{
    struct node *n;
    n= (struct node*)malloc(sizeof(struct node));
    n->a=i;
    n->next=NULL;
    g->array[i]=n;
}
addedge(g,0,1); //Creating the graph first here 
addedge(g,0,4);
addedge(g,4,0);
addedge(g,4,1);
addedge(g,4,3);
addedge(g,3,4);
addedge(g,3,1);
addedge(g,3,2);
addedge(g,1,0);
addedge(g,1,2);
addedge(g,1,3);
addedge(g,1,4);
addedge(g,2,1);
addedge(g,2,3);
printf("BFS\n");
bfs(g);
return 0;

}
OUTPUT:

Program for breadth first traversal of a tree in C 

It can be done using many methods
We will be using queue to implement bfs as it consumes space but takes less time due space time trade off

#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
struct node *left;
struct node *right;
};
void bfs(struct node *r)
{
    int front=0, rear=0;
struct node **queue= (struct node **)malloc(100*sizeof(struct node *));//using array of size 100 to store    the pointers to the node
// the array is the array of pointers and hence pointer to pointer double pointer is used here
//We can also use linked list form of queue but for simplicity we have taken a fixed size 
queue[0]=r;
struct node *temp;
while(queue[front]!=NULL)
{
temp=queue[front];
printf("%d",temp->key);
printf(" ");
if(temp->left)
{
  queue[++rear]=temp->left;
}
if(temp->right)
{
    queue[++rear]=temp->right;
}
front++;
}

}
int main()
{
struct node * root;
root= (struct node *)malloc(sizeof(struct node));
root->key=1;
struct node*temp;
//Lets First Create the tree
temp= (struct node *)malloc(sizeof(struct node));
temp->key=2;
temp->left=NULL;
temp->right=NULL;
root->left=temp;
temp= (struct node *)malloc(sizeof(struct node));
temp->key=3;
temp->left=NULL;
temp->right=NULL;
root->right=temp;
temp= (struct node *)malloc(sizeof(struct node));
temp->key=4;
temp->left=NULL;
temp->right=NULL;
root->left->left=temp;
temp= (struct node *)malloc(sizeof(struct node));
temp->key=5;
temp->left=NULL;
temp->right=NULL;
root->left->right=temp;
bfs(root);

return 0;
}

Output:

C Program to implement graphs 

As we know that a graph is generally represented using two notations 
namely 1) Adjacency Matrix 2) Adjacency List 
The first representation is pretty much simple but later is important one.
The choice of using either representation depends upon the task you are performing with the graph.
When the graph is sparse (i.e having less no. of edges we uses Adjacency List as it consumes less space when there are less no of edges in a graph)

Here is the implementation of the same 
The graph used here is :

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int a;
    struct node * next;
};
struct graph
{
    int v;
    struct node **array;
};
void addedge(struct graph *g,int s,int d)
{
    struct node*temp ;
    temp= (struct node *)malloc(sizeof(struct node));
    temp->a=d;
    temp->next=g->array[s];// adding the node at the starting of the list
    g->array[s]=temp;
}
void printgraph(struct graph *g)
{
    struct node *temp;
    int i;
    printf("Adjaceny List representation of the graph is \n ");
    for(i=0;i<g->v;i++)
    {
        temp = g->array[i];
        printf("%d->",i);
        while(temp)
        {
            printf("%d->",temp->a);
            temp=temp->next;
        }
        printf("\n");
    }
}

int main()
{
struct graph *g;
g=(struct graph *)malloc(sizeof(struct graph));
g->v=5;
g->array=(struct node **)malloc(5*sizeof(struct node*));
int i;
for(i=0;i<5;i++) //intializing the graph
{
    g->array[i]=NULL;
}
addedge(g,0,1);
addedge(g,0,4);
addedge(g,4,0);
addedge(g,4,1);
addedge(g,4,3);
addedge(g,3,4);
addedge(g,3,1);
addedge(g,3,2);
addedge(g,1,0);
addedge(g,1,2);
addedge(g,1,3);
addedge(g,1,4);
addedge(g,2,1);
addedge(g,2,3);
printgraph(g);

return 0;

}
Output:

Program to connect nodes at the same level in the tree

For eg. We are given the tree in the figure(a) and we need to connect the tree node as shown in the figure (b)

#include<stdio.h>
#include<stdlib.h>
struct Tree
{
int key;
struct Tree* left;
struct Tree *right;
struct Tree *nextright;
}*root=NULL;
void displaytree(struct Tree *);
void conASL(struct Tree *);
int main()
{
struct Tree *temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
root =temp;
root->key=2;
root->nextright=NULL;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=3;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->left=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=4;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->right=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=5;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->left->left=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=6;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->left->right=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=7;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->right->left=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=8;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->right->right=temp;
conASL(root);
displaytree(root);
return 0;
}
void displaytree(struct Tree *node)
{
    if(node==NULL)
        return;
printf("key=%d",node->key);
if(node->nextright==NULL)
printf("nextright=NULL");
else
printf("nextright=%d",node->nextright->key);
displaytree(node->left);
displaytree(node->right);
}
void conASL(struct Tree *node)
{
    if((node->left==NULL)&&(node->right==NULL))
        return;
    else
    {
        node->left->nextright=node->right;
        if(node->nextright==NULL)
        {
            node->right->nextright=NULL;
        }
        else
        {
        node->right->nextright=node->nextright->left;
        }
   conASL(node->left);
   conASL(node->right);
    }

}

Output: