DAA- Graphs – BFS

Graphs – BFS

What is a Graph?

A Graph is said to be a non-linear data structure that consists of nodes and edges. The nodes are also called vertices and the edges are referred to as lines or the arcs that act as a bridge or connect any two nodes in the graph. For example, consider the following example to get a clear understanding of this.

In the above graph we have a set of vertices V which are given as 

V = {0,1,2,3,4},  and also a set of edges E = {01, 12, 23, 34, 04, 14, 13}.

Graphs can be utilized in order to solve many real-life problems. For example, graphs can be used to represent the connectivity of networks. The networks may include anything like the paths in a city, a telephone network, or a circuit network.

Breadth-First Search (BFS) Algorithm

Breadth-first search is a graph traversal algorithm where we traverse the graph starting from the root node and explore all the neighboring nodes. The algorithm then selects the nearest node and explores all the unexplored nodes. The algorithm follows the same process for all neighboring nodes until it finds the goal.

The algorithm starts with examining node A and all of its neighbors. Next, we explore the neighbors of the nearest node of A, and this process continues in the further steps until we explore all the nodes and ensure that each node is visited exactly once. Which means that no node is visited twice.

Algorithm for BFS:

• Step 1: SET STAT = 1 (ready state) for each node in G
• Step 2: Enqueue the starting node A and set its STAT = 2 (waiting state)
• Step 3: Now, repeat Steps 4 and 5 until the QUEUE is empty
• Step 4: Dequeue a node N. Process it and set its STAT = 3 (processed state).
• Step 5: Enqueue or add in all the neighbors of N that are in the ready state (whose STAT = 1) and set their state as STAT = 2 (waiting state)
• Step 6: EXIT

Example for BFS:

Consider the following graph G to calculate the minimum path from one node A to another node E. Also, we are given that each edge has a length of 1.

Solution:

We apply the breadth-first search algorithm to find the minimum Path P. We begin this process at node A and will end at E. The algorithm uses two queues here, which are QUEUE1 and QUEUE2. Here, QUEUE1 will hold all the nodes that are to be explored and QUEUE2 will hold all the nodes that have been explored and deleted from QUEUE1.

Let’s start by tracing the graph from Node A.

1. We start by adding A into QUEUE1 and NULL into QUEUE2. So, after this, the queues would look like,

QUEUE1 = {A}  

QUEUE2 = {NULL}  

2. Now, we delete Node A from QUEUE1 and insert all its neighbours into it. We then insert Node A into QUEUE2

QUEUE1 = {B, D}  

QUEUE2 = {A}  

3. Similarly, we delete node B from QUEUE1 and insert all its neighbours into the same. Then we insert node B into QUEUE2.

QUEUE1 = {D, C, F}   

QUEUE2 = {A, B}  

4. Now, we delete node D from QUEUE1 and insert all its neighbors into the queue. D has only 2 neighbors A and F out of which A id already visited. Also, F has been inserted into queue 1, so we will not insert it again. Insert node D into QUEUE2.

QUEUE1 = {C, F}  

QUEUE2 = { A, B, D}  

5. We now remove node C from QUEUE1 and insert all its neighbours in its place and then add node C into QUEUE2.

QUEUE1 = {F, E, G}  

QUEUE2 = {A, B, D, C}  

6. Now, we remove F from QUEUE1 and add all its neighbors into the queue. Since all neighbors of F have already been added, we will not add them again. So, we add node F to QUEUE2.

QUEUE1 = {E, G}  

QUEUE2 = {A, B, D, C, F}  

7. Later, we remove node E from QUEUE1, as all the neighbors of E have already been added to QUEUE1 we will not add them again into the queue. All the nodes have been visited and the target node E is encountered into QUEUE2.

QUEUE1 = {G}  

QUEUE2 = {A, B, D, C, F,  E}  

Now we backtrack from E to A using the nodes available in QUEUE2.

The minimum path would be A → B → C → E.

C Program for BFS traversal:

#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,front=0,rear=-1;
void bfs(int v) {
for (int i=1;i<=n;i++)
  if(a[v][i] && !visited[i])
   q[++rear]=i;
if(front<=rear) {
visited[q[front]]=1;
bfs(q[front++]);
}
}
void main() {
int v;
clrscr();
printf("\n Enter the number of vertices:");
scanf("%d",&n);
for (int i=1;i<=n;i++) {
q[i]=0;
visited[i]=0;
}
printf("\n Enter graph data in matrix form:\n");
for (i=1;i<=n;i++)
  for (j=1;j<=n;j++)
   scanf("%d",&a[i][j]);
printf("\n Enter the starting vertex:");
scanf("%d",&v);
bfs(v);
printf("\n The node which are reachable are:\n");
for (i=1;i<=n;i++)
  if(visited[i])
   printf("%d\t",i); else
   printf("\n Bfs is not possible");
getch();
}