Implement a breadth-first search algorithm using Java. The program will read a t

Question

Implement a breadth-first search algorithm using Java. The program will read a text file that contains the linked lists of the graph.

Then you will ask the user for the node

E, D, B, D (or A, B, D, E, C) there could be more than one correct answer.

To approach this problem, one good way to do the following:

1) Loop through the files and create a linked list then hash the linked list in a dictionary using its first node

So for the above example, the dictionary will contain:

Key A, and value linked list A->E>D->B

Key E, and value linked list E->A

...

2) Find the linked list for the starting node given by the user (it'll be easy to do so since you have them stored in a dictionary and you don't need to search for that element using sequential search)

3) Queue all of the elements in the linked list

4) Dequeue one element at a time, visit that element and do step 2 (find the linked list for that element in the dictionary and add to the queue all of the element in its linked list).

5) Dequeue, visit, repeat.

*Do not visit any node more than once; you can use a dictionary to keep track of visited nodes (or nodes in the queue) and you can check that dictionary either before you print the node (or before adding it to the queue)

Explanation / Answer

public class BreadthFirstSearch { //To keep track of the nodes we check so we know if it connects to the source. //If a node was checked, then there is a path to the node from a source private boolean[] checked; //To keep track of the parents that each child is connected to private int[] connectedTo; //Where we start our search from in the graph private final int SOURCE; public BreadthFirstSearch(Graph g, int rootVertex) { //Initialize arrays with the size of the graph checked = new boolean[g.verticesInGraph()]; connectedTo = new int[g.verticesInGraph()]; SOURCE = rootVertex; bfs(g, rootVertex); } //Go over the graph selecting the best parent-child connections private void bfs(Graph g, int source) { Queue parentsQueue = new ArrayDeque(); //Create a queue //We check the source passed in as a parameter and mark it as checked checked[source] = true; parentsQueue.add(source); //We add our parent to the queue while(!parentsQueue.isEmpty()) { // We hold the parentVertex or source in this variable int parentVertex = parentsQueue.remove(); //For every child connected to the parent for(int child : g.getVerticesConnectedTo(parentVertex)) { if(!checked[child]) { // child is connected to the parent vertex connectedTo[child] = parentVertex; //So we don't check this node again checked[child] = true; //We add the next parent to the queue parentsQueue.add(child); } } } } //This method just allows us to check if a vertex is connected to the source. //If a vertex has been checked then it is connected public boolean hasPathTo(int vertex) { return checked[vertex]; } //This method returns the path from the SOURCE to a given vertex public List pathTo(int vertex) { if (!hasPathTo(vertex)) return null; List path = new ArrayList(); //First add the vertex passed in to the method path.add(vertex); //Since we are iterating through a queue, //we check form vertex(goal) to source while (connectedTo[vertex] != SOURCE) { vertex = connectedTo[vertex]; path.add(vertex); } path.add(SOURCE); //Now we add the source at the very end return path; //We return a path from the vertex to the source } }

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.