// Java program to print BFS traversal from a given source vertex. // BFS(int s) traverses vertices reachable from s. importjava.io.*;importjava.util.*;// This class represents a directed graph using adjacency list // representation classGraph{privateint V;// No. of vertices privateLinkedList<Integer> adj[];//Adjacency Lists // Constructor Graph(intv){ V = v; adj =newLinkedList[v];for(int i=0; i<v;++i) adj[i]=newLinkedList();} // Function to add an edge into the graph voidaddEdge(intv,intw){ adj[v].add(w);} // prints BFS traversal from a given source s voidBFS(ints){ // Mark all the vertices as not visited(By default // set as false) boolean visited[]=newboolean[V]; // Create a queue for BFS LinkedList<Integer> queue =newLinkedList<Integer>(); // Mark the current node as visited and enqueue it visited[s]=true;queue.add(s);while(queue.size()!=0){ // Dequeue a vertex from queue and print it s =queue.poll();System.out.print(s+""); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it Iterator<Integer> i = adj[s].listIterator();while(i.hasNext()){int n =i.next();if(!visited[n]){ visited[n]=true;queue.add(n);}}}} // Driver method to publicstaticvoidmain(Stringargs[]){Graph g =newGraph(4);g.addEdge(0,1);g.addEdge(0,2);g.addEdge(1,2);g.addEdge(2,0);g.addEdge(2,3);g.addEdge(3,3);System.out.println("Following is Breadth First Traversal "+"(starting from vertex 2)");g.BFS(2);}}// This code is contributed by Aakash Hasija
1) Shortest Path and Minimum Spanning Tree for unweighted graph
In an unweighted graph, the shortest path is the path with least number of edges.
2) Peer to Peer Networks.
In Peer to Peer Networks like BitTorrent, Breadth First Search is used to find all neighbor nodes.
3) Crawlers in Search Engines:
Crawlers build index using Breadth First. The idea is to start from source page and follow all links from source and keep doing same. Depth First Traversal can also be used for crawlers, but the advantage with Breadth First Traversal is, depth or levels of the built tree can be limited.
4) Social Networking Websites:
In social networks, we can find people within a given distance ‘k’ from a person using Breadth First Search till ‘k’ levels.
5) GPS Navigation systems:
Breadth First Search is used to find all neighboring locations.
6) Broadcasting in Network:
In networks, a broadcasted packet follows Breadth First Search to reach all nodes.
7) In Garbage Collection:
Breadth First Search is used in copying garbage collection using Cheney’s algorithm. Refer this and for details. Breadth First Search is preferred over Depth First Search because of better locality of reference:
In undirected graphs, either Breadth First Search or Depth First Search can be used to detect cycle. In directed graph, only depth first search can be used.
In Ford-Fulkerson algorithm, we can either use Breadth First or Depth First Traversal to find the maximum flow. Breadth First Traversal is preferred as it reduces worst case time complexity to O(VE2).
One of Dijkstra’salgorithm modifications on breadth-first search is its use of a priorityqueue instead of a normal queue. With a priority queue, each task added to the queue has a “priority” and will slot in accordingly into the queue based on its priority level.
public calss GraphNode{
int val;
List<GraphNode> neighnors;
}
HashSet<GraphNode> visited = new HashSet<GraphNode>();
// boolean[][] visited = new boolean[m][n]
public void DFS(GraphNode nd){
//print nd.val
visited.add(nd);
for(GraphNode next : nd.neighbours){
if(!visited.contains(next)){
DFS(next);
}
}
}
public void DFS(GraphNode start){
Stack<GraphNode> s = new Stack<GraphNode>();
q.push(start);
visited.add(start);
while(!s.empty()){
GraphNode cur = s.pop();
//print cur.val
for(GraphNode next : cur.children){
if(!visited.contains(next)){
s.push(next);
visited.add(next);//mark node as visited when adding to stack.
}
}
}//while end
}