Graph Traversal using Breadth First Search (BFS)

Traversing is nothing but visiting each node/vertex of a graph in a systematic way. A graph is represented by its nodes and edges, so, visiting all the nodes of a graph is known as traversal of the graph.

There are two approaches for graph traversal, namely Breadth First Search (BFS) and Depth First Search (DFS). In this tutorial, we will discuss the BFS approach.

In this technique, first, we take any node as a starting node and all the adjacent nodes are chosen from that starting node. In the next step, the same approach is applied to all the newly visited nodes and continued until all the nodes are visited. We maintain the status of the visited node in one array so that no node can be traversed again.

This graph traversal technique uses a queue for traversing all the nodes of the graph.

---

Procedure

---

1. Insert starting node into the queue.
2. Delete front element from the queue and insert 
	   all its unvisited neighbours into the queue at the
	   end and traverse them. Also make the value of visited
	   array true for these nodes.
3. Repeat step 2 until the queue is empty.                

---

BFS Using Colour Scheme

---

This is another method for traversing graphs through BFS. Let's see the procedure and then we will understand the method by an example.

BFS(G,s)
for each vertex u &belongsto; V[G]-{s} do
   color[u]=white
   d[u]=&infinity;
   π[u]=NIL
color[s]=gray
d[s]=0
Enqueue(Q,s)
while Q!=φ do
   Dequeue(Q)
   for each v &belongsto; Adj[u] do
        if color[v]=white then
            color[v]=gray
            d[v]=d[u]+1
            π[v]=u
            Enqueue(Q,v)
        color[u]=black
   end for
end while        

Let's take an example of a graph which is shown in the following Figure.

Source Code

#include <stdio.h> #include <stdlib.h> #define MAX 20 typedef struct Q { int data[MAX]; int R,F; }Q; typedef struct node { struct node *next; int vertex; } node; void enqueue(Q *,int); int dequque(Q *); int empty(Q *); int full(Q *); void BFS(int); void readgraph(); void insert(int vi,int vj); int visited[MAX]; node *G[20]; int n; int main() { int i,op; do { printf("\n\n1)Create\n2)BFS\n3)Quit"); printf("\nEnter Your Choice: "); scanf("%d",&op); switch(op) { case 1: readgraph(); break; case 2: printf("\nStarting Node No. : "); scanf("%d",&i); BFS(i); break; case 3: return 0; } }while(op!=4); } void BFS(int v) { int w,i,visited[MAX]; Q q; node *p; q.R=q.F=-1; for(i=0;i<n;i++) visited[i]=0; enqueue(&q,v); printf("\nVisit\t%d",v); visited[v]=1; while(!empty(&q)) { v=dequeue(&q); for(p=G[v];p!=NULL;p=p->next) { w=p->vertex; if(visited[w]==0) { enqueue(&q,w); visited[w]=1; printf("\nvisit\t%d",w); } } } } int empty(Q *P) { if(P->R==-1) return(1); return(0); } int full(Q *P) { if(P->R==MAX-1) return(1); return(0); } void enqueue(Q *P,int x) { if(P->R==-1) { P->R=P->F=0; P->data[P->R]=x; } else { P->R=P->R+1; P->data[P->R]=x; } } int dequeue(Q *P) { int x; x=P->data[P->F]; if(P->R==P->F) { P->R=-1; P->F=-1; } else P->F=P->F+1; return(x); } void readgraph() { int i,vi,vj,no_of_edges; printf("\nEnter no. of vertices :"); scanf("%d",&n); for(i=0;i<n;i++) G[i]=NULL; printf("\nEnter no of edges :"); scanf("%d",&no_of_edges); for(i=0;i<no_of_edges;i++) { printf("\nEnter an edge (u,v) :"); scanf("%d%d",&vi,&vj); insert(vi,vj); insert(vj,vi); } } void insert(int vi,int vj) { node *p,*q; q=(node *)malloc(sizeof(node)); q->vertex=vj; q->next=NULL; if(G[vi]==NULL) G[vi]=q; else { p=G[vi]; while(p->next!=NULL) p=p->next; p->next=q; } }

---

Happy Exploring!