In this assignment, you will have to implement a breadth-first search algorithm
ID: 674271 • Letter: I
Question
In this assignment, you will have to implement a breadth-first search algorithm using Java.
You will read a text file that contains the linked lists of the graph; for example, something like this:
A,E,D,B
E,A
D,A
B,A,C
C,B
Which looks like this:
Then you will ask the user for the node that you will have to start traversing at; say the user enters A.
You will then print the breadth-first search order, which in this case would be A, E, D, B, C (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) (previous assignment) 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
Answer :
import java.util.*;
public class BreadthFirstSearch
{
private Queue<Integer> queue;
public BreadthFirstSearch()
{
queue = new LinkedList<Integer>();
}
public void bfs(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[source] = 1;
queue.add(source);
while (!queue.isEmpty())
{
element = queue.remove();
i = element;
System.out.print(i + " ");
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
queue.add(i);
visited[i] = 1;
}
i++;
}
}
}
public static void main(String[] args)
{
int number_no_nodes, source;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph :");
scanner = new Scanner(System.in);
number_no_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
System.out.println("Enter the adjacent matrix :");
for (int i = 1; i <= number_no_nodes; i++)
for (int j = 1; j <= number_no_nodes; j++)
adjacency_matrix[i][j] = scanner.nextInt();
System.out.println("Enter the source vertex for graph :");
source = scanner.nextInt();
System.out.println("The BreadthFirstSearch traversal of graph is:");
BreadthFirstSearch bfs = new BreadthFirstSearch();
bfs.bfs(adjacency_matrix, source);
} catch (InputMismatchException inputMismatch)
{
System.out.println("The given input is wrong");
}
scanner.close();
}
}