- 24th Nov 2022
- 04:10 am
- Admin
Java Programming Assignment Help - Implementation of a Breadth-First Search
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 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 queue = new LinkedList();
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 neigh = graph.getNeighbors(source);
for(int i=0;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 visited[i] = 0;
parents[i] = -1;
}
return s;
}
} // end of class