-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathDepthFirstSearchStackMatrix.java
More file actions
57 lines (48 loc) · 1.89 KB
/
DepthFirstSearchStackMatrix.java
File metadata and controls
57 lines (48 loc) · 1.89 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:30 PM
*
* A rendition of the first informal Depth First Search assignment.
*/
import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;
public class DepthFirstSearchStackMatrix
{
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 DFS on the graph starting at node 0.
depthFirstSearch(graph, 0);
} // end main
// Stack-based DepthFirstSearch starting at vertex on graph.
public static void depthFirstSearch(MatrixGraph graph, int vertex)
{
// Store the node in a stack.
Stack stack = new Stack();
stack.push(vertex);
// Mark the node as visited.
graph.visited[vertex] = true;
// Examine all nodes on the stack.
while(!stack.empty())
{
int node = (Integer) stack.pop();
System.out.println("Visited " + node);
// Examine the graph table to determine which node to examine next.
// Decrementing instead of incrementing so nodes are displayed in ascending, numerical order.
for(int i = graph.table[node].length - 1; i >= 0; i--)
{
// If the node is adjacent to the current (and has not been visited), add it to the stack.
if((graph.table[node][i] == 1) && (!graph.visited[i]))
{
graph.visited[i] = true;
stack.push(i);
}
}
}
} // end depthFirstSearch
} // end class