Graph Traversal – Explanation and Implementation
Visiting every vertices of a graph is referred as Graph Traversal, which is of two ways,
- Breadth First Traversing
- Depth First Traversing
Most of the problems that we’ve faced for the graph often goes with the traversal/searching of the graph.
Similar to tree traversals, where traversing is done starting with a root node, a graph traversal also has to start with a node. We can use same tree traversal algorithm for graph traversal as well, but the problem is, that a graph can have a cycle(s). This cycle can cause retraversal of some of the nodes. Hence, to avoid that an array namely, visited[n] is separately defined (each index represents the respective vertex of the graph).
Each entry is a flag states whether the vertex is already visited or not.
1. Depth First Traversal(DFT)
Similar to depth first of trees in this traversal we keep on exploring the childs of the current node and once we visit all the child nodes then we move on the adjacent node. See the above graph, V0 – V3 – V2 – V1.
Starting with V0, adjacent one is V3, therefore visit V3. Adjacent to V3 is V2. Now no one is adjacent to V2 as non-visited. Thus, go back to V3, check if there is an adjacent node as non-visited. Found none. Again, goes back, check the same, then found V1 non-visited. Therefore, visit V1.
Thus, it pretty looks like a stack.
Depth first traversal will be implemented using recursive function calling. Also, referring depth first searching is same as depth-first traversal.
Implementation of depth-first traversal in Graph:
Using Matrix representation of a graph depth-first traversal is implemented in c.
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
typedef struct graph{
int nVertices; //number of vertices in the graph
int nEdges; //number of edges in the graph
int **adjMatrix;
}Graph;
/*node of a Queue data structure*/
typedef struct QueueNode{
int data;
struct QueueNode *next;
}queueNode;
queueNode *head = NULL;
void printGraph(Graph *);
Graph * createAdjMatrixOfGraph(Graph *);
/* inserting to a queue data structure*/
void enqueue( int item){
queueNode *list = head;
queueNode *temp = (queueNode*)malloc(sizeof(queueNode));
temp->data = item;
temp->next = NULL;
if(list)
temp->next = list;
head = temp;
}
/*deleting from a queue data structure */
int dequeue(){
int itemDequeued;
queueNode *list = head;
queueNode *temp = (queueNode*)malloc(sizeof(queueNode));
/* if queue has no element */
if(!list){
return INT_MIN;
}
/* if queue containing one element */
else if(!list->next){
itemDequeued = list->data;
head = NULL;
free(list);
return itemDequeued;
}
/* at the end of loop temp points to second last queueNode*/
else{
while(list->next){
temp = list;
list = list->next;
}
}
itemDequeued = list->data;
temp->next = NULL;
free(list);
return itemDequeued;
}
/* this will create Adjacency matrix of the undirected graph graph */
Graph * createAdjMatrixOfGraph(Graph *g){
int i, u, v;
g = (Graph *)malloc(sizeof(Graph));
printf("Enter the number of Vertices and Edges:");
scanf("%d%d", &g->nVertices, &g->nEdges);
g->adjMatrix = (int **)malloc(sizeof(int *) * g->nVertices);
for(i = 0; i < g->nVertices; i++)
g->adjMatrix[i] = (int *)malloc(sizeof(int) * g->nVertices);
for(i = 0; i < g->nEdges; i++){
printf("Reading the endpoints of an edge(u v):\n");
scanf("%d %d", &u, &v);
g->adjMatrix[u][v] = 1;
g->adjMatrix[v][u] = 1;
}
return g;
}
void printGraph(Graph *g){
int i, j;
printf("\n***Adjacency Matrix of Graph***\n");
for(i = 0 ; i < g->nVertices; i++ ){
printf("\n\t");
for(j = 0 ; j < g->nVertices; j++ ){
if( g->adjMatrix[i][j] ){
printf("1 ");
}
else
printf("0 ");
}
}
}
void breadthFirstTraversal(Graph *g, int u, int *visited){
int i, j;
int vertexDequeued;
visited[u] = 1;
enqueue(u);
for(j = 0; j < g->nVertices; j++){
vertexDequeued = dequeue();
if(vertexDequeued == INT_MIN)
return;
printf(" %d", vertexDequeued);
for(i = 0; i < g->nVertices; i++){
if( (g->adjMatrix[vertexDequeued][i]) && ( !(visited[i]) ) ){
visited[i] = 1;
enqueue(i);
}
}
}
}
int main(void){
Graph *g = NULL;
int *visited;
g = createAdjMatrixOfGraph(g);
printGraph(g);
visited = (int *)malloc(g->nVertices*sizeof(int));
printf("\nBreadth First Traversal of the graph: ");
breadthFirstTraversal(g, 2, visited);
return 0;
}
Output:-
Enter the number of Vertices and Edges:
4 4
Reading the endpoints of an edge(u v):
0 1
Reading the endpoints of an edge(u v):
0 2
Reading the endpoints of an edge(u v):
0 3
Reading the endpoints of an edge(u v):
2 3
***Adjacency Matrix of Graph***
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
Depth First Traversal of the graph: 0 1 2 3
2. Breadth First Traversal(BFT)
Again similar to tree breadth-first traversal in this also we traverse all the nodes a given level first and save their child for the next step. Select one node, visit all its adjacent nodes and then move to their children.
It can be clearly seen how the data structure provides the way to visit the graph in breadth first traversing.
Implementation:
Using matrix representation of the graph, BFT is implemented in c.
#include<stdio.h>
#include<stdlib.h>
typedef struct graph{
int nVertices; //number of vertices in the graph
int nEdges; //number of edges in the graph
int **adjMatrix;
}Graph;
Graph * createAdjMatrixOfGraph(Graph *);
/* this will create Adjacency matrix of the undirected graph graph */
Graph * createAdjMatrixOfGraph(Graph *g){
int i, u, v;
g = (Graph *)malloc(sizeof(Graph));
printf("Enter the number of Vertices and Edges:");
scanf("%d%d", &g->nVertices, &g->nEdges);
g->adjMatrix = (int **)malloc(sizeof(int) * g->nVertices);
for(i = 0; i < g->nVertices; i++)
g->adjMatrix[i] = (int *)malloc(sizeof(int) * g->nVertices);
for(i = 0; i < g->nEdges; i++){
printf("Reading the endpoints of an edge(u v):\n");
scanf("%d %d", &u, &v);
g->adjMatrix[u][v] = 1;
g->adjMatrix[v][u] = 1;
}
return g;
}
void printGraph(Graph *g){
int i, j;
printf("\n***Adjacency Matrix of Graph***\n");
for(i = 0 ; i < g->nVertices; i++ ){
printf("\n\t");
for(j = 0 ; j < g->nVertices; j++ ){
if( g->adjMatrix[i][j] ){
printf("1 ");
}
else
printf("0 ");
}
}
}
void depthFirstTraversal(Graph *g, int u, int *visited){
int i;
visited[u] = 1;
printf(" %d", u);
for(i = 0; i < g->nVertices; i++){
if( (g->adjMatrix[u][i]) && ( !(visited[i]) ) ){
depthFirstTraversal(g, i, visited);
}
}
}
int main(void){
Graph *g = NULL;
int *visited;
g = createAdjMatrixOfGraph(g);
printGraph(g);
visited = (int *)malloc(g->nVertices*sizeof(int));
printf("\nDepth First Traversal of the graph: ");
depthFirstTraversal(g, 2, visited);
return 0;
}
Output:-
Enter the number of Vertices and Edges:5 4
Reading the endpoints of an edge(u v):
0 1
Reading the endpoints of an edge(u v):
0 3
Reading the endpoints of an edge(u v):
0 4
Reading the endpoints of an edge(u v):
3 2
***Adjacency Matrix of Graph***
0 1 0 1 1
1 0 0 0 0
0 0 0 1 0
1 0 1 0 0
1 0 0 0 0
Breadth First Traversal of the graph: 0 1 3 4 2
Note:-
Our implementation assumes the input provided will be a connected graph. In the case of an unconnected graph, the traversing function will be recursively called on each of the components.
Applications of Graph Traversals:
- Garbage collection typically can be implemented as the graph traversal reaching all the nodes.
- Topological sorting of a graph
- Solving puzzles such as Mazes
- Finding the shortest path between two nodes.
- Finding all the vertices in a connected component
- Finding minimum spanning tree
- Finding the articulation points(cut vertices).
- Finding strongly connected components.
- Testing if the graph contains cycle or not.
- Testing if the graph is bipartite or not.
So that’s all for this tutorial. Hope this helps and you like the tutorial. Do ask for any queries in the comment box and provide your valuable feedback.
Do not forget to SHARE and SUBSCRIBE.
Keep Coding!! Happy Coding!! 🙂
how to combine dft nd bft
This is a very broad question and it all depends on the scenario we want to implement. We just have to figure out the process and algorithm like on which condition we have to switch to DFT or to BFT and once we have figured that out we can use these algorithms to apply there