Please translate the following pseudocode into compilable java code: Note: Do no

ID: 3872696 • Letter: P

Question

Please translate the following pseudocode into compilable java code:

Note: Do not copy and paste from online sources!

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

#include<iostream>

#include <list>

using namespace std;

// This class represents a directed graph using adjacency list representation

class Graph

{

int V; // No. of vertices

list<int> *adj; // Pointer to an array containing adjacency lists

public:

Graph(int V); // Constructor

void addEdge(int v, int w); // function to add an edge to graph

void BFS(int s); // prints BFS traversal from a given source s

};

Graph::Graph(int V)

{

this->V = V;

adj = new list<int>[V];

}

void Graph::addEdge(int v, int w)

{

adj[v].push_back(w); // Add w to v’s list.

}

void Graph::BFS(int s)

{

// Mark all the vertices as not visited

bool *visited = new bool[V];

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

visited[i] = false;

// Create a queue for BFS

list<int> queue;

// Mark the current node as visited and enqueue it

visited[s] = true;

queue.push_back(s);

// 'i' will be used to get all adjacent vertices of a vertex

list<int>::iterator i;

while(!queue.empty())

{

// Dequeue a vertex from queue and print it

s = queue.front();

cout << s << " ";

queue.pop_front();

// Get all adjacent vertices of the dequeued vertex s

// If a adjacent has not been visited, then mark it visited

// and enqueue it

for(i = adj[s].begin(); i != adj[s].end(); ++i)

{

if(!visited[*i])

{

visited[*i] = true;

queue.push_back(*i);

}

// Driver program to test methods of graph class

int main()

{

// Create a graph given in the above diagram

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

cout << "Following is Breadth First Traversal "

<< "(starting from vertex 2) n";

g.BFS(2);

return 0;

}