Graph Theory : Breadth First Search

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key) and explores the neighbour nodes first, before moving to the next level neighbour.

BFS was invented in the late 1950s by E. F. Moore, who used it to find the shortest path out of a maze, and discovered independently by C. Y. Lee as a wire routing algorithm (published 1961).

[Source :https://en.wikipedia.org/wiki/Breadth-first_search ]

BFS of above tree would give : 1 -->2-->3-->4-->5-->6-->7-->8-->9-->10-->11-->12

Solution : 

In order to implement BFS , we use a queue data structure (Similar to level order traversal of a tree). We also maintain a boolean array to mark all the visited nodes with value='true'

We start with root , and add it to queue. 

Now we iterate through the queue as follows , until the queue is empty and do following :

• fetch a node from q,
• print it
• fetch all its adjacent nodes, mark them visited and add them in queue

Implementation :

// 1. Graph Class : 

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

class Graph {

private int v; // no of vertices in the graph
List<Integer> adj[]; // adjacency list

public Graph(int v) {

this.v = v;
adj = new ArrayList[v];

for (int i = 0; i < v; i++)
adj[i] = new ArrayList<Integer>();
}

public int getV() {
return v;
}

public void setV(int v) {
this.v = v;
}

public List<Integer>[] getAdj() {
return adj;
}

public void setAdj(List<Integer>[] adj) {
this.adj = adj;
}

public void addEdge(int v, int w) {
this.adj[v].add(w);
}

}

// 2. BFS CLASS 

class BFS {



public void printBFS(int v, Graph g) {

// mark all vertices as non visited

boolean visited[] = new boolean[g.getV()];
LinkedList<Integer> q= new LinkedList<Integer>();


visited[v]=true;
q.add(v);



while (!q.isEmpty()) {

v = q.poll();
System.out.print(v+"==>");

Iterator<Integer> it = g.adj[v].iterator();
while(it.hasNext()){
int n = it.next();
               if (!visited[n])
               {
                   visited[n] = true;
                   q.add(n);
               }


}
}


}


}


//TESTER CLASS : 

public class GraphTester {

    public static void main(String args[]){

        Graph g=new Graph(4);
        g.addEdge(0,1);
        g.addEdge(0, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(1, 2);
        g.addEdge(3, 3);



        BFS bfs= new BFS();
        System.out.println("BREADTH FIRST SEARCH TRAVERSAL OF INPUT GRAPH ");

        bfs.printBFS(2, g);
}

}


****************************************************************************

OUTPUT :

BREADTH FIRST SEARCH TRAVERSAL OF INPUT GRAPH 

2==>0==>3==>1==>