Prerequisites:
Before starting this tutorial, please complete below tutorials
1. Queue
Example - How BFS(Breadth First Search) traversal works :
We take below figure in consideration to understand functioning of BFS.
As shown in the above figure, there is a network of crackers connected through flammable yarn. Someone applies fire on cracker c2 in the network. Suppose the yarn material is uniformly flammable and fire spreads in all direction with same speed uniformly. Then below will be the order of blasting of crackers.
Note: For example purpose suppose flammable yarn spreads the fire only in the direction of arrow shown in the graph.
1. Since c2 is the first cracker which is ignited by the flame, it will be ready to blast first as given in the below figure.
2. Once c2 blasts its adjacent crackers(c4,c7) in the cracker network get flame from c2 and will be ready to blast as shown in the below figure.
3. The same process as mentioned above is continued on where c4 and c7 blast and their adjacent crackers will be ready for blast in next phase. Since c4 doesn't have any adjacent cracker to blast and only c7 has adjacent cracker c3 to blast, so in next phase only c3 will be ready to blast as shown in the below figure.
4. In the next phase c3 will blast and its adjacent crackers c1,c5 and c6 will be ready to blast as shown in the below figure.
5. At last c1,c5 and c6 will blast.
Definition:
As mentioned in the above example, Breadth First Search(BFS) is an graph traversal algorithm where a node is processed first before processing its adjacent vertices. Once node is processed its adjacent vertices are processed before processing their adjacent vertices.
BFS starts from a source/root vertex which is processed first then in next round all reachable vertices from root node are processed. In further rounds all reachable vertices which are next to all processed vertices are processed. This process is continued on till all vertices are processed.
Here vertices having same distance from source/route node are processed in same iteration. Due to processing of vertices level by level from source/root vertex, BFS is also called Level Order Traversal.
In other words we can define Breadth First Search as:
It starts at the root (or any arbitrary node) and explores all the neighboring nodes at the present depth before moving on to nodes at the next depth level.
Implementation
From the above mentioned definition it is clear that the vertex which is encountered first is processed first and then its adjacent vertices are processed later one by one in the order. Then next level of vertices are processed, which indicates a queue data structure will be used to preserve property first come first serve in the BFS algorithm implementation.
Below is the algorithm to apply BFS on the given graph G(V,E)|(V is set of vertices and E is set of edges of the graph) where BFS starts at node sourceNode.
BFS(G(V,E), sourceNode)
{
1. Define a queue Q
2. Q.enQueue(sourceNode)
3. visitedNodes.add(sourceNode)
4. while Q is not empty
5. {
6. item=Q.dequeue()
7. process item
8. for all vertex v adjacent to item
9. {
10. if v is not in visitedNodes
11. {
12. Q.enQueue(v)
13. visitedNodes.add(v)
14. }
15. }
16. }
}
We are taking below example to implement it through java code where source vertex will be A.
Below is the java code implementation for the above mentioned BFS traversal algorithm
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class BFSTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Hashtable<Character,List<Character>> graph=new Hashtable<Character, List<Character>>();
List<Character> children =new ArrayList<Character>();
children.add('B');
children.add('C');
graph.put('A', children);
children =new ArrayList<Character>();
children.add('A');
children.add('D');
children.add('E');
graph.put('B', children);
children =new ArrayList<Character>();
children.add('A');
children.add('F');
graph.put('C', children);
children =new ArrayList<Character>();
children.add('B');
graph.put('D', children);
children =new ArrayList<Character>();
children.add('B');
children.add('F');
graph.put('E', children);
children =new ArrayList<Character>();
children.add('C');
children.add('E');
graph.put('F', children);
BFS dfs=new BFS(graph);
dfs.applyBFS('A');
}
}
class BFS
{
Hashtable<Character,List<Character>> graph;
public BFS(Hashtable<Character,List<Character>> g)
{
graph=g;
}
public void applyBFS(char source)
{
Queue<Character> q=new LinkedList<Character>();
HashSet<Character> visitedNodes=new HashSet<Character>();
q.add(source);
visitedNodes.add(source);
while(!q.isEmpty())
{
char item=q.remove();
System.out.println("Processed Item is:"+item);
for(char v:graph.get(item))
{
if(!visitedNodes.contains(v))
{
q.add(v);
visitedNodes.add(v);
}
}
}
}
}
Characteristics:
- Time Complexity of BFS: , where is the number of vertices and is the number of edges.
- Space Complexity of BFS: , due to the storage required for the queue and the visited nodes.
