-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathDepthFirstSearchStackList.java
More file actions
65 lines (53 loc) · 2.15 KB
/
DepthFirstSearchStackList.java
File metadata and controls
65 lines (53 loc) · 2.15 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
58
59
60
61
62
63
64
65
/**
* Author: Kevin Richardson <[email protected]>
* Date: 9/13/11
* Time: 10:05 PM
*
* A stack-based Depth First Search algorithm utilizing Linked Lists to store graph structure.
*/
import java.io.IOException;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;
import java.util.Stack;
public class DepthFirstSearchStackList
{
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 a ListGraph.
System.out.print("Enter desired graph input file: ");
ListGraph graph = new ListGraph(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(ListGraph graph, int vertex)
{
// Store the node in a stack.
Stack stack = new Stack();
stack.push(vertex);
// Mark the node as visited.
graph.visited[vertex] = 1;
// Examine all nodes on the stack.
while(!stack.empty())
{
vertex = (Integer) stack.pop();
System.out.println(vertex + " has been visited.");
// Get this vertex's list of previousConnections (starting at the end of the list).
LinkedList list = graph.connections.get(vertex);
ListIterator listItr = list.listIterator(list.size());
// Loop through the list backwards. This is done so destinations will come out in numerical order.
while(listItr.hasPrevious())
{
int destination = (Integer) listItr.previous();
// If the node has not already been visited, add it to the stack for processing.
if(graph.visited[destination] == 0)
{
graph.visited[destination] = 1;
stack.push(destination);
}
}
}
} // end depthFirstSearch
} // end class