Please type the following BFS PseudoCode in Java. function BreADTH-FIRST-SEARCH(
ID: 3871955 • Letter: P
Question
Please type the following BFS PseudoCode in Java.
function BreADTH-FIRST-SEARCH(problem) returns a solution, or failure node a node with STATE = problem.INITIAL-STATE, PATH-COST = 0 if problem.GoAL-TEST(node.STATE) then return SoLUTION(node) frontier a FIFO queue with node as the only element explored an empty set then retumSOLUTION(node) if EMPty?(frontier) then return failure node POP(frontier) /* chooses the shallowest node in frontier */ add node.STATE to explored for each action in problem.ACTIONs(node.STATE) do child CHILD-NODE( pro lem, node, action) if child.STATE is not in explored or frontier then if problem.GOAL-TEST(child.STATE) then return SoLUTION(child) frontier INSERT( child, frontier)Explanation / Answer
// 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 Lists
// 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].add(w);
}
// prints BFS traversal from a 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 a 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 from queue and print it
s = queue.poll();
System.out.print(s+" ");
// Get all adjacent vertices of the dequeued vertex s
// If a 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);
}
}