A dense graph is given and you want to discover all the nodes, how would you start to discover ??
Randomly but its dense you will get lost that which has been discovered and which is not, So here we comes up with 2 basic ideas of traversing the graph i.e.
- Depth first Search
- Breadth First Search
Lets start with Breadth First Search ( bfs ) :
As name suggest breadth first, it explores from left to right and then top to bottom ,
So in this traversal is done in FIFO manner i.e. first in first out manner , so we have to use queue as a data structure.
The nodes at lower level is explored first rather than the ones at higher level.
Let's see it for clear understanding ,
Given Graph :
Start with 4 :
-
- Push 4 in Queue
- |4|
-
- Pop front 4 from Queue and Print it . Push adjacent nodes of 4 into Queue i.e. 2 and 6
- |2|6|
-
- Pop front 2 from Queue and Print it . Push adjacent nodes of 2 into Queue i.e. 1 and 3
- |6|1|3|
-
- Pop front 6 from Queue and Print it . Push adjacent nodes of 6 into Queue i.e. 5 and 7
- |1|3|5|7|
-
- Pop front 1 from Queue and Print it . Push adjacent nodes of 1 into Queue i.e. null
- |3|5|7|
-
- Pop front 3 from Queue and Print it . Push adjacent nodes of 3 into Queue i.e. null
- |5|7| ....
So Bfs of graph will be : 4,2,6,1,3,5,7
Lets implement it :
void bfs(int start_node)
{
queue<int> Q;
Q.push(start_node)
while(Q is not empty())
{
//pop out front from queue
front = Q.front()
Q.pop()
//bfs print
print front
// put all adjacent nodes in queue
for (all adjacent nodes of front)
{
if(node not visited)
{
push into the queue;
}
}
}
}
Time Complexity
O(V+E)
V - number of Nodes
E - number of Edges
Again basic of bfs , once you get this you will get to know how powerful and where we can use it in daily life example
Stay tuned for more ....