Breadth First Search

Graph Traversal means visiting each node exactly once. There are two methods of traversing the graph -

• Breadth First Search (BFS)
• Depth First Search (DFS)

Breadth First Search

The Breadth First Search is an algorithm for a graph or a tree traversal. It begins at the root node and explores all the neighbouring nodes in breadth(full graph width) before going in deeper. A queue and a graph or a tree is used as a data structure in a breadth first algorithm.

In this, the traversal of elements of a graph or tree goes through level-by-level(left to right). It makes sure that every node is visited at least once. In each iteration, a vertex is removed from the queue and the adjacent vertices which are not visited are added in a queue. This algorithm terminates when the queue becomes empty.

The BFS is basically used to solve problems like - mapping routes, analyzing networks, puzzle game, scheduling, web crawlers etc.

The BFS is less space efficient than depth-first-search.

Algorithm for breath-first-search

These are the steps for the Breadth-First-Search algorithm -

• Initially, take an empty queue, pick a node and enqueue all its adjacent nodes into a queue.
• Dequeue(removed) a node from the queue, marked it as visited and enqueue all its neighbour nodes into a queue.
• Repeat the above process till the queue becomes empty.

``````Step 1: SET STATUS = 1 (ready state)
for each node in G
Step 2: Enqueue the starting node A to queue and mark it visisted
and set its STATUS = 2
(waiting state)
Step 3: Repeat Steps 4 and 5 until
QUEUE is empty
Step 4: Dequeue a node N. Process it
and set its STATUS = 3
(processed state).
Step 5: Enqueue all the adjacents of
N that are in the ready state and mark them visisted
(whose STATUS = 1) and set
their STATUS = 2
(waiting state)
[END OF LOOP]
Step 6: EXIT``````

Complexity of Breadth First Search

Time Complexity of BFS in Tree Traversal

If V is the number of nodes in a tree, the time complexity to traversed is O(V).

Time Complexity of BFS in Graph Traversal

If V is the number of vertexes and E is the number of edges in a graph, the time complexity to traversed is O(V + E).

Example of Breadth First Search

``BFS : 0 2 3 4 7 1 6 5 ``

Bredth First Search Program in C

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

#define MAX 100

#define initial 1
#define waiting 2
#define visited 3

int n;
int adj[MAX][MAX];
int state[MAX];
void generate_graph();
void bfs_traversal();
void BFS(int v);

int queue[MAX], front = -1,rear = -1;
void enqueue(int vertex);
int dequeue();
int check_emptyqueue();

int main()
{
generate_graph();
bfs_traversal();
return 0;
}

void bfs_traversal()
{
int v;

for(v=0; v rear)
return 1;
else
return 0;
}

int dequeue()
{
int delete_item;
if(front == -1 || front > rear)
{
printf("Queue Underflow\n");
exit(1);
}

delete_item = queue[front];
front = front+1;
return delete_item;
}

void generate_graph()
{
int count,max_edge,origin,destin;

printf("Enter number of vertices : ");
scanf("%d",&n);
max_edge = n*(n-1);

for(count=1; count<=max_edge; count++)
{
printf("Enter edge %d( -1 -1 to quit ) : ",count);
scanf("%d %d",&origin,&destin);

if((origin == -1) && (destin == -1))
break;

if(origin>=n || destin>=n || origin<0 || destin<0)
{
printf("Invalid edge!\n");
count--;
}
else
{
adj[origin][destin] = 1;
}
}
}``````

Output of the above program:

``````Enter number of vertices : 8
Enter edge 1( -1 -1 to quit ) : 0
2
Enter edge 2( -1 -1 to quit ) : 0
3
Enter edge 3( -1 -1 to quit ) : 0
4
Enter edge 4( -1 -1 to quit ) : 0
7
Enter edge 5( -1 -1 to quit ) : 2
1
Enter edge 6( -1 -1 to quit ) : 3
1
Enter edge 7( -1 -1 to quit ) : 4
6
Enter edge 8( -1 -1 to quit ) : 7
6
Enter edge 9( -1 -1 to quit ) : 1
5
Enter edge 10( -1 -1 to quit ) : 6
5
Enter edge 11( -1 -1 to quit ) : -1-1
Enter Start Vertex for BFS:
0
0 2 3 4 7 1 6 5
``````