Login
Order Now
Support
Java Program for Implementation of a Breadth-First Search

Java Program for Implementation of a Breadth-First Search

  • 24th Nov, 2022
  • 16:40 PM

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

public class BFS {
    
    int visited[];
    int parents[];
    Graph graph;

    public BFS(Graph graph)
    {
        this.graph = graph;
        int V = graph.getNodes();
        visited = new int[V]; 
        parents = new int[V];
        
        for(int i=0;i<V;i++) {
            visited[i] = 0;        // The vertex is not yet discovered.
            parents[i] = -1;
        }
    }

    /*
     * Performs the Breadth-first search routine between the source and
     * destination nodes received as parameters and returns the traversed path
     * if found.
     * 
     * Must reset the visit state of all nodes each time this method is called.
     * 
     * @return the traversed path from source to destination or
     * "Destination unreachable." in case there is no such path.
     */
    public String runBFS(int source, int destination)
    {
        int osource = source;
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.add(source); 
        parents[source-1] = source;
        visited[source-1] = 1;        // vertex discovered.
        
        String s = "";
        while(queue.size() != 0) 
        { 
            source = queue.poll();  
            visited[source-1] = 1;        // All neighbors of the vertex processed.
            
            ArrayList<Integer> neigh = graph.getNeighbors(source); 
            for(int i=0;i<neigh.size();i++)
            { 
                 int n = neigh.get(i);
                 if (visited[n-1]==0)    // Vertex not yet discovered.
                 {
                    visited[n-1] = 1;
                    parents[n-1] = source;
                     queue.add(n);
                 }  
            }
        } 
       
        
        if(parents[destination-1]==-1)
            s = "Destination unreachable.";
        else {
            int i=0;
            while(destination!=osource){
                if(i>0)
                    s = destination + ", " + s;
                else
                    s = destination + "" + s;
                destination = parents[destination-1];
                i++;
            }
            s = "[" + osource + ", " + s + "]";
        }
        
        for(int i=0;i<graph.getNodes();i++){
            visited[i] = 0;
            parents[i] = -1;
        }    
        
        return s;
    }

}    // end of class

Share this post

assignment helpassignment helperassignment expertsassignment writing services