BFS Graph Traversals (With Implementation In JAVA  Recursive And Iterative Both ) | Breadth First Search | Data structures



Breadth First Search for a graph is similar to Breadth First Traversal of a tree .The only thing here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. And uses a queue to remember to get the next vertex to start a search.

For More Understanding Watch This Video


Java Implementation of BFS :-


public class Edge {

public int src;

public int dest;

public Edge(int src, int dest) {

this.src = src;

this.dest = dest;

}

}

import java.util.ArrayList;

import java.util.List;


import sis.com.Edge;


public class Graph2 {

List<List<Integer>> adj = new ArrayList<List<Integer>>();

public Graph2(List<Edge> edges,int N) {

// TODO Auto-generated constructor stub

for (int i=0;i<N;i++) {

adj.add(new ArrayList<>());

}

for (Edge edge : edges) {

adj.get(edge.src).add(edge.dest);

adj.get(edge.dest).add(edge.src);

}

}

}

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

import sis.com.Edge;

public class Test {

public static void main(String[] args) {
// TODO Auto-generated method stub
List<Edge> edges = Arrays.asList(new Edge(1, 2),new Edge(1, 3),
new Edge(1, 4),new Edge(2, 5),new Edge(2, 6),
new Edge(4, 7),new Edge(4, 8),new Edge(5, 9),
new Edge(5, 10),new Edge(7, 11),new Edge(7, 12));
final int N = 13;
Graph2 graph2 = new Graph2(edges,N);
boolean discovered[] = new boolean[N];
for(int i=0;i<N;i++){
if(!discovered[i]){
bfs(graph2,i,discovered);
}
}
System.out.println("---------BFS---------");
//discovered[] = new boolean[N];
Queue<Integer> q = new ArrayDeque<Integer>();
for(int i=0;i<N;i++){
if(!discovered[i]){
q.add(i);
discovered[i] = true;
recursiveBFS(graph2,q,discovered);
}
}
}


private static void recursiveBFS(Graph2 graph2, Queue<Integer> q,
boolean[] discovered) {
// TODO Auto-generated method stub
while (!q.isEmpty()) {
int v = q.poll();
System.out.print(v+" ");
for(int ele:graph2.adj.get(v))
if(!discovered[ele]){
q.add(ele);
discovered[ele] = true;
}
}
recursiveBFS(graph2,q,discovered);
}

private static void bfs(Graph2 graph2, int v, boolean[] discovered) {
// TODO Auto-generated method stub
Queue<Integer> q = new ArrayDeque<Integer>();
q.add(v);
discovered[v] = true;
while (!q.isEmpty()) {
v = q.poll();
System.out.print(v+" ");
for (int dest : graph2.adj.get(v)) {
if(discovered[dest] == false){
discovered[dest] = true;
q.add(dest);
}
}
}
}

}