Preliminaries Download the Graph interface, the UndirectedUnweightedGraph templa
ID: 665396 • Letter: P
Question
Preliminaries
Download the Graph interface, the UndirectedUnweightedGraph template, and the driver.
You should also look carefully at the Graph interface and the UndirectedUnweightedGraph, as they differ slightly from how I introduced them in class.
Objective
Implement breadth-first search over a graph, where the graph is represented as an adjacency list. For simplicity, we will be working with a graph that is undirected, and does not have edge weights.
Description
Add the following method to UndirectedUnweightedGraph:
breadthFirstSearch - Implements breadth first search over the graph.params
node - The node at which to begin the search.
return - A list of nodes in the order traversed.
Graph interface:
}
UndirectedUnweightedGraph template:
}
Driver:
Example Dialog
Notes
The static graph used in the first portion of the driver is pictured below:
To better visualize the graph that is generated, a dot file is produced after each run. You can visualize this by using the program 'dot' fromGraphViz.
At the command prompt, type:
You can then open the graph.png file in any image viewer.
Explanation / Answer
// Breadth First Search
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BrFiSrch
{
private Queue<Integer> queue;
public BrFiSrch()
{
queue = new LinkedList<Integer>();
}
public void BrFiSrch(int AdjMat[][], int Src)
{
int NumOfNodes = AdjMat[Src].length - 1;
int[] Traversed = new int[NumOfNodes + 1];
int i, entity;
Traversed[Src] = 1;
queue.add(Src);
while (!queue.isEmpty())
{
entity = queue.remove();
i = entity;
System.out.print(i + " ");
while (i <= NumOfNodes)
{
if (AdjMat[entity][i] == 1 && Traversed[i] == 0)
{
queue.add(i);
Traversed[i] = 1;
}
i++;
}
}
}
public static void main(String... arg)
{
int number_no_nodes, Src;
Scanner scanner = null;
try
{
System.out.println("Please Input the number of vertices present in the graph under consideration");
scanner = new Scanner(System.in);
number_no_nodes = scanner.nextInt();
int AdjMat[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
System.out.println("Enter the matrix to be used as the adjacency matrix for this graph");
for (int i = 1; i <= number_no_nodes; i++)
for (int j = 1; j <= number_no_nodes; j++)
AdjMat[i][j] = scanner.nextInt();
System.out.println("Enter the Source information for the graph under consideration");
Src = scanner.nextInt();
System.out.println("The Breadth First Search traversal of the graph is ");
BrFiSrch BrFiSrch = new BrFiSrch();
BrFiSrch.BrFiSrch(AdjMat, Src);
} catch (InputMismatchException inputMismatch)
{
System.out.println("Entered data is not in the correct Syntax");
}
scanner.close();
}
}
// The above method BreadthFirstSearch can be added to undirectedWeightedGraph