001package algs42; 002import stdlib.*; 003import algs13.Queue; 004import algs13.Stack; 005import algs44.DirectedEdge; 006import algs44.EdgeWeightedDigraph; 007/* *********************************************************************** 008 * Compilation: javac DepthFirstOrder.java 009 * Execution: java DepthFirstOrder filename.txt 010 * Dependencies: Digraph.java Queue.java Stack.java StdOut.java 011 * EdgeWeightedDigraph.java DirectedEdge.java 012 * Data files: http://algs4.cs.princeton.edu/42directed/tinyDAG.txt 013 * http://algs4.cs.princeton.edu/42directed/tinyDG.txt 014 * 015 * Compute preorder and postorder for a digraph or edge-weighted digraph. 016 * Runs in O(E + V) time. 017 * 018 * % java DepthFirstOrder tinyDAG.txt 019 * v pre post 020 * -------------- 021 * 0 0 8 022 * 1 3 2 023 * 2 9 10 024 * 3 10 9 025 * 4 2 0 026 * 5 1 1 027 * 6 4 7 028 * 7 11 11 029 * 8 12 12 030 * 9 5 6 031 * 10 8 5 032 * 11 6 4 033 * 12 7 3 034 * Preorder: 0 5 4 1 6 9 11 12 10 2 3 7 8 035 * Postorder: 4 5 1 12 11 10 9 6 0 3 2 7 8 036 * Reverse postorder: 8 7 2 3 0 6 9 10 11 12 1 5 4 037 * 038 *************************************************************************/ 039 040public class DepthFirstOrder { 041 private final boolean[] marked; // marked[v] = has v been marked in dfs? 042 private final int[] pre; // pre[v] = preorder number of v 043 private final int[] post; // post[v] = postorder number of v 044 private final Queue<Integer> preorder; // vertices in preorder 045 private final Stack<Integer> revPost; // vertices in preorder 046 private final Queue<Integer> postorder; // vertices in postorder 047 private int preCounter; // counter or preorder numbering 048 private int postCounter; // counter for postorder numbering 049 050 // depth-first search preorder and postorder in a digraph 051 public DepthFirstOrder(Digraph G) { 052 pre = new int[G.V()]; 053 post = new int[G.V()]; 054 revPost = new Stack<>(); 055 postorder = new Queue<>(); 056 preorder = new Queue<>(); 057 marked = new boolean[G.V()]; 058 for (int v = 0; v < G.V(); v++) 059 if (!marked[v]) dfs(G, v); 060 } 061 062 // depth-first search preorder and postorder in an edge-weighted digraph 063 public DepthFirstOrder(EdgeWeightedDigraph G) { 064 pre = new int[G.V()]; 065 post = new int[G.V()]; 066 revPost = new Stack<>(); 067 postorder = new Queue<>(); 068 preorder = new Queue<>(); 069 marked = new boolean[G.V()]; 070 for (int v = 0; v < G.V(); v++) 071 if (!marked[v]) dfs(G, v); 072 } 073 074 // run DFS in digraph G from vertex v and compute preorder/postorder 075 private void dfs(Digraph G, int v) { 076 marked[v] = true; 077 pre[v] = preCounter++; 078 preorder.enqueue(v); 079 for (int w : G.adj(v)) { 080 if (!marked[w]) { 081 dfs(G, w); 082 } 083 } 084 postorder.enqueue(v); 085 revPost.push(v); 086 post[v] = postCounter++; 087 return; 088 } 089 090 // run DFS in edge-weighted digraph G from vertex v and compute preorder/postorder 091 private void dfs(EdgeWeightedDigraph G, int v) { 092 marked[v] = true; 093 pre[v] = preCounter++; 094 preorder.enqueue(v); 095 for (DirectedEdge e : G.adj(v)) { 096 int w = e.to(); 097 if (!marked[w]) { 098 dfs(G, w); 099 } 100 } 101 postorder.enqueue(v); 102 revPost.push(v); 103 post[v] = postCounter++; 104 } 105 106 public int pre(int v) { 107 return pre[v]; 108 } 109 110 public int post(int v) { 111 return post[v]; 112 } 113 114 // return vertices in postorder as an Iterable 115 public Iterable<Integer> post() { 116 return postorder; 117 } 118 119 // return vertices in preorder as an Iterable 120 public Iterable<Integer> pre() { 121 return preorder; 122 } 123 124 // return vertices in reverse postorder as an Iterable 125 public Iterable<Integer> reversePost() { 126 return revPost; 127 } 128 129 130 // check that pre() and post() are consistent with pre(v) and post(v) 131 private boolean check(Digraph G) { 132 133 // check that post(v) is consistent with post() 134 int r = 0; 135 for (int v : post()) { 136 if (post(v) != r) { 137 StdOut.println("post(v) and post() inconsistent"); 138 return false; 139 } 140 r++; 141 } 142 143 // check that pre(v) is consistent with pre() 144 r = 0; 145 for (int v : pre()) { 146 if (pre(v) != r) { 147 StdOut.println("pre(v) and pre() inconsistent"); 148 return false; 149 } 150 r++; 151 } 152 153 return true; 154 } 155 156 public static void main(String[] args) { 157 args = new String[] { "data/tinyDG.txt" }; 158 159 In in = new In(args[0]); 160 Digraph G = DigraphGenerator.fromIn(in); 161 162 DepthFirstOrder dfs = new DepthFirstOrder(G); 163 StdOut.println(" v pre post"); 164 StdOut.println("--------------"); 165 for (int v = 0; v < G.V(); v++) { 166 StdOut.format("%4d %4d %4d\n", v, dfs.pre(v), dfs.post(v)); 167 } 168 169 StdOut.print("Preorder: "); 170 for (int v : dfs.pre()) { 171 StdOut.print(v + " "); 172 } 173 StdOut.println(); 174 175 StdOut.print("Postorder: "); 176 for (int v : dfs.post()) { 177 StdOut.print(v + " "); 178 } 179 StdOut.println(); 180 181 StdOut.print("Reverse postorder: "); 182 for (int v : dfs.reversePost()) { 183 StdOut.print(v + " "); 184 } 185 StdOut.println(); 186 187 188 } 189 190}