-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathBreadthFirstSearchMatrix.java
More file actions
57 lines (48 loc) · 1.88 KB
/
BreadthFirstSearchMatrix.java
File metadata and controls
57 lines (48 loc) · 1.88 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
* Author: Kevin Richardson <[email protected]>
* Date: 9/13/11
* Time: 12:23 PM
*
* An implementation of a Breadth First Search algorithm utilizing adjacency matrices as a graph storage structure.
*/
import java.io.IOException;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Queue;
public class BreadthFirstSearchMatrix
{
public static void main(String[] args) throws IOException
{
Scanner keyboardScanner = new Scanner(System.in);
// Get the user's desired graph file and scan it in to the graph table.
System.out.print("Enter desired graph input file: ");
MatrixGraph graph = new MatrixGraph(keyboardScanner.nextLine());
// Run BFS on the graph starting at node 0.
breadthFirstSearch(graph, 0);
} // end main
// Breadth First Search starting at vertex on graph.
public static void breadthFirstSearch(MatrixGraph graph, int vertex)
{
// Store the node in a queue.
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(vertex);
// Mark the node as visited.
graph.visited[vertex] = true;
// Examine all nodes in the queue.
while(!queue.isEmpty())
{
vertex = queue.remove();
System.out.println(vertex + " has been visited.");
// Examine the graph table to determine which node to examine next.
for(int i = 0; i < graph.table[vertex].length; i++)
{
// If the node is adjacent to the current (and has not been visited), add it to the queue.
if((graph.table[vertex][i] == 1) && (!graph.visited[i]))
{
graph.visited[i] = true;
queue.add(i);
}
}
}
} // end breadthFirstSearch
} // end class