Tuesday, 24 May 2016

Breadth-first search (BFS) Implemetation in Java

Breadth-first seach implementation in java 


import java.util.Iterator;
import java.util.LinkedList;

public class GraphBFS {

     // No. of vertices
     private int vertives;

     //Adjacency Lists - Edges
     private LinkedList<Integer> adj[];

     GraphBFS(int vertices) {
           vertives = vertices;
           adj = new LinkedList[vertices];
           for (int i=0; i<vertices; ++i) {
                adj[i] = new LinkedList<Integer>();
           }
     }

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

     private void traverseBFS(int node) {
           /** Mark true if vertices are visited. */
           boolean visited[] = new boolean[vertives];

           /** Create a queue for BFS */
           LinkedList<Integer> queue = new LinkedList<Integer>();

           /** mark start node as visited by default. */
           visited[node] = true;
           queue.add(node);

           while(!queue.isEmpty()) {

                /** poll the first element of queue. */
                node = queue.poll();

                System.out.print(node+" ");

                /** add all the nearest node of processing node. */
                Iterator<Integer> iter = adj[node].listIterator();
                while (iter.hasNext()) {
                     int next = iter.next();
                     if (!visited[next]) {
                           visited[next] = true;
                           queue.add(next);
                     }
                }
           }
     }

     public static void main(String args[]) {

           /** Create a graph of size . */
           GraphBFS graph = new GraphBFS(4);

           /** Add edges in the graph.*/
           graph.addEdge(0, 1);
           graph.addEdge(0, 2);
           graph.addEdge(1, 2);
           graph.addEdge(2, 0);
           graph.addEdge(2, 3);
           graph.addEdge(3, 2);
           graph.addEdge(3, 1);

           System.out.println("BFS Traversal : ");

           /** start BS from any given node.*/
           graph.traverseBFS(1);
     }
}
Output
BFS Traversal:
1 2 0 3

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...