|
| 1 | +/** |
| 2 | + * Run nonrecursive depth-first search on an undirected graph. |
| 3 | + * Runs in O(E + V) time using O(V) extra space. |
| 4 | + * |
| 5 | + * Explores the vertices in exactly the same order as DepthFirstSearch.java |
| 6 | + * |
| 7 | + */ |
| 8 | +import java.util.Iterator; |
| 9 | + |
| 10 | +public class NonrecursiveDFS { |
| 11 | + private boolean[] marked; // marked[v] = is there an s-v path ? |
| 12 | + |
| 13 | + // Computes the vertices connected to the source vertex `s` in the graph `G` |
| 14 | + public NonrecursiveDFS(Graph G, int s) { |
| 15 | + marked = new boolean[G.V()]; |
| 16 | + |
| 17 | + validateVertex(s); |
| 18 | + |
| 19 | + // to be able to iterate over each adjacency list, keeping track of which vertex |
| 20 | + // in each adjacency list needs to be explored next |
| 21 | + Iterator<Integer>() adj = (Iterator<Integer>[]) new Iterator[G.V()]; |
| 22 | + for(int i = 0; i < G.V(); i++) |
| 23 | + adj[v] = G.adj(v).iterator(); |
| 24 | + // DFS using an explicit stack |
| 25 | + Stack<Integer> stack = new Stack<Integer>(); |
| 26 | + marked[s] = true; |
| 27 | + stack.push(s); |
| 28 | + while(!stack.isEmpty()) { |
| 29 | + int v = stack.peek(); |
| 30 | + if(adj[v].hasNext()) { |
| 31 | + int w = adj[v].next(); |
| 32 | + // StdOut.printf("check %d\n", w); |
| 33 | + if(!marked[w]) { |
| 34 | + // discovered vertex w for the first time |
| 35 | + marked[w] = true; |
| 36 | + stack.push(w); |
| 37 | + } |
| 38 | + } else { |
| 39 | + stack.pop(); |
| 40 | + } |
| 41 | + } |
| 42 | + } |
| 43 | + |
| 44 | + // is vertex `v` connected to the source vertex `s` |
| 45 | + public boolean marked(int v) { |
| 46 | + validateVertex(v); |
| 47 | + return marked[v]; |
| 48 | + } |
| 49 | + |
| 50 | + // throw an IllegalArgumentException unless `0 <= v < V` |
| 51 | + private void validateVertex(int v) { |
| 52 | + int V = marked.length; |
| 53 | + if(v < 0 || v >= V) |
| 54 | + throw new IllegalArgumentException("vertex" + v + " is not between 0 and " + (V - 1)); |
| 55 | + } |
| 56 | + |
| 57 | + // test |
| 58 | + public static void main(String[] args) { |
| 59 | + In in = new In(args[0]); |
| 60 | + Graph G = new Graph(in); |
| 61 | + int s = Integer.parseInt(args[1]); |
| 62 | + NonrecursiveDFS dfs = new NonrecursiveDFS(G, s); |
| 63 | + for(int v = 0; v < G.V(); v++) |
| 64 | + if(dfs.marked(v)) |
| 65 | + StdOut.print(v + " "); |
| 66 | + StdOut.println(); |
| 67 | + } |
| 68 | +} |
0 commit comments