Write a complete and simple to understand JavaScript code fo

Write a complete and simple to understand JavaScript code for implementing Breadth First Search algorithm

Solution

// java program to print bfs traversal from a given source vertex

// BFS ( int s ) traverses vertices reachable from s

import java.io.*;

import java.util.*;

// this class represents a directed graph using adjacency list

// representation

class Graph

{

   private int V ; // no of vertices

   private LinkedList < Integer > adj [ ] ; // adjacency list

// constructor

Graph ( int v )

   {

       V = v ;

       adj = new LinkedList[ v ];

       for ( int i = 0 ; i < v ; ++i )

          adj [ i ] = new LinkedList( ) ;

   }

// function to add an edge into the graph

void addEdge( int v , int w )

{

    adj[v].adj(w);

}

// print BFS traversal from given source s

void BFS ( int s )

{

   // mark all the vertices as not visited ( by default

   // set as false )

   boolean visited[ ] = new boolean[ V ] ;

   // create queue for BFS

   LinkedList<Integer> queue = new LinkedList<Integer>( ) ;

// mark the current node as visited and enqueue it

visited[s] = true ;

queue.add(s);

while (queue.size() ! = 0 )

{

   // dequeue a vertex fom queue and print it

      s = queue.poll( ) ;

     System.out.print( s + \" \" ) ;

     // get all adjacent vertices of the dequeued vertex s

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

            }

   }

}

}

public static void main ( String args [ ] )

{

Graph g = new Graph ( 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 ) ;

}

}

output :

following is breadth first traversal ( starting from vertex 2 )

2 0 3 1