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: