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

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);

}

}

}

}

}