基础数据结构和算法十四：Directed Graphs
?
public class Digraph { private final int V; private int E; private Bag<Integer>[] adj; /** * Create an empty digraph with V vertices. * * @throws java.lang.IllegalArgumentException if V < 0 */ public Digraph(int V) { if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative"); this.V = V; this.E = 0; adj = (Bag<Integer>[]) new Bag[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<Integer>(); } } /** * Create a digraph from input stream. */ public Digraph(In in) { try { this.V = in.readInt(); if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative"); adj = (Bag<Integer>[]) new Bag[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<Integer>(); } int E = in.readInt(); if (E < 0) throw new IllegalArgumentException("Number of edges in a Digraph must be nonnegative"); for (int i = 0; i < E; i++) { int v = in.readInt(); int w = in.readInt(); addEdge(v, w); } } catch (NoSuchElementException e) { throw new InputMismatchException("Invalid input format in Digraph constructor"); } } /** * Copy constructor. */ public Digraph(Digraph G) { this(G.V()); this.E = G.E(); for (int v = 0; v < G.V(); v++) { // reverse so that adjacency list is in same order as original Stack<Integer> reverse = new Stack<Integer>(); for (int w : G.adj[v]) { reverse.push(w); } for (int w : reverse) { adj[v].add(w); } } } /** * Return the number of vertices in the digraph. */ public int V() { return V; } /** * Return the number of edges in the digraph. */ public int E() { return E; } /** * Add the directed edge v->w to the digraph. * * @throws java.lang.IndexOutOfBoundsException unless both 0 <= v < V and 0 <= w < V */ public void addEdge(int v, int w) { if (v < 0 || v >= V) throw new IndexOutOfBoundsException("vertex " + v + " is not between 0 and " + (V - 1)); if (w < 0 || w >= V) throw new IndexOutOfBoundsException("vertex " + w + " is not between 0 and " + (V - 1)); adj[v].add(w); E++; } /** * Return the list of vertices pointed to from vertex v as an Iterable. * * @throws java.lang.IndexOutOfBoundsException unless 0 <= v < V */ public Iterable<Integer> adj(int v) { if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); return adj[v]; } /** * Return the reverse of the digraph. */ public Digraph reverse() { Digraph R = new Digraph(V); for (int v = 0; v < V; v++) { for (int w : adj(v)) { R.addEdge(w, v); } } return R; } /** * Return a string representation of the digraph. */ public String toString() { StringBuilder s = new StringBuilder(); String NEWLINE = System.getProperty("line.separator"); s.append(V + " vertices, " + E + " edges " + NEWLINE); for (int v = 0; v < V; v++) { s.append(String.format("%d: ", v)); for (int w : adj[v]) { s.append(String.format("%d ", w)); } s.append(NEWLINE); } return s.toString(); }}
?
?
public class DirectedDFS { private boolean[] marked; // marked[v] = true if v is reachable // from source (or sources) // single-source reachability public DirectedDFS(Digraph G, int s) { marked = new boolean[G.V()]; dfs(G, s); } // multiple-source reachability public DirectedDFS(Digraph G, Iterable<Integer> sources) { marked = new boolean[G.V()]; for (int v : sources) dfs(G, v); } private void dfs(Digraph G, int v) { marked[v] = true; for (int w : G.adj(v)) { if (!marked[w]) dfs(G, w); } } // is there a directed path from the source (or sources) to v? public boolean marked(int v) { return marked[v]; }}
?
?
public class DepthFirstDirectedPaths { private boolean[] marked; // marked[v] = true if v is reachable from s private int[] edgeTo; // edgeTo[v] = last edge on path from s to v private final int s; // source vertex // single source public DepthFirstDirectedPaths(Digraph G, int s) { marked = new boolean[G.V()]; edgeTo = new int[G.V()]; this.s = s; dfs(G, s); } private void dfs(Digraph G, int v) { marked[v] = true; for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] = v; dfs(G, w); } } } // is there a directed path from s to v? public boolean hasPathTo(int v) { return marked[v]; } // return path from s to v; null if no such path public Iterable<Integer> pathTo(int v) { if (!hasPathTo(v)) return null; Stack<Integer> path = new Stack<Integer>(); for (int x = v; x != s; x = edgeTo[x]) path.push(x); path.push(s); return path; }}
?
public class BreadthFirstDirectedPaths { private static final int INFINITY = Integer.MAX_VALUE; private boolean[] marked; // marked[v] = is there an s->v path? private int[] edgeTo; // edgeTo[v] = last edge on shortest s->v path private int[] distTo; // distTo[v] = length of shortest s->v path // single source public BreadthFirstDirectedPaths(Digraph G, int s) { marked = new boolean[G.V()]; distTo = new int[G.V()]; edgeTo = new int[G.V()]; for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY; bfs(G, s); } // multiple sources public BreadthFirstDirectedPaths(Digraph G, Iterable<Integer> sources) { marked = new boolean[G.V()]; distTo = new int[G.V()]; edgeTo = new int[G.V()]; for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY; bfs(G, sources); } // BFS from single source private void bfs(Digraph G, int s) { Queue<Integer> q = new Queue<Integer>(); marked[s] = true; distTo[s] = 0; q.enqueue(s); while (!q.isEmpty()) { int v = q.dequeue(); for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] = v; distTo[w] = distTo[v] + 1; marked[w] = true; q.enqueue(w); } } } } // BFS from multiple sources private void bfs(Digraph G, Iterable<Integer> sources) { Queue<Integer> q = new Queue<Integer>(); for (int s : sources) { marked[s] = true; distTo[s] = 0; q.enqueue(s); } while (!q.isEmpty()) { int v = q.dequeue(); for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] = v; distTo[w] = distTo[v] + 1; marked[w] = true; q.enqueue(w); } } } } // length of shortest path from s (or sources) to v public int distTo(int v) { return distTo[v]; } // is there a directed path from s (or sources) to v? public boolean hasPathTo(int v) { return marked[v]; } // shortest path from s (or sources) to v; null if no such path public Iterable<Integer> pathTo(int v) { if (!hasPathTo(v)) return null; Stack<Integer> path = new Stack<Integer>(); int x; for (x = v; distTo[x] != 0; x = edgeTo[x]) path.push(x); path.push(x); return path; }}
?
?
public class DirectedCycle { private boolean[] marked; // marked[v] = has vertex v been marked? private int[] edgeTo; // edgeTo[v] = previous vertex on path to v private boolean[] onStack; // onStack[v] = is vertex on the stack? private Stack<Integer> cycle; // directed cycle (or null if no such cycle) public DirectedCycle(Digraph G) { marked = new boolean[G.V()]; onStack = new boolean[G.V()]; edgeTo = new int[G.V()]; for (int v = 0; v < G.V(); v++) if (!marked[v]) dfs(G, v); } // check that algorithm computes either the topological order or finds a directed cycle private void dfs(Digraph G, int v) { onStack[v] = true; marked[v] = true; for (int w : G.adj(v)) { // short circuit if directed cycle found if (cycle != null) return; //found new vertex, so recur else if (!marked[w]) { edgeTo[w] = v; dfs(G, w); } // trace back directed cycle else if (onStack[w]) { cycle = new Stack<Integer>(); for (int x = v; x != w; x = edgeTo[x]) { cycle.push(x); } cycle.push(w); cycle.push(v); } } onStack[v] = false; } public boolean hasCycle() { return cycle != null; } public Iterable<Integer> cycle() { return cycle; } // certify that digraph is either acyclic or has a directed cycle private boolean check(Digraph G) { if (hasCycle()) { // verify cycle int first = -1, last = -1; for (int v : cycle()) { if (first == -1) first = v; last = v; } if (first != last) { System.err.printf("cycle begins with %d and ends with %d\n", first, last); return false; } } return true; }}
public class DepthFirstOrder { private boolean[] marked; // marked[v] = has v been marked in dfs? private int[] pre; // pre[v] = preorder number of v private int[] post; // post[v] = postorder number of v private Queue<Integer> preorder; // vertices in preorder private Queue<Integer> postorder; // vertices in postorder private int preCounter; // counter or preorder numbering private int postCounter; // counter for postorder numbering // depth-first search preorder and postorder in a digraph public DepthFirstOrder(Digraph G) { pre = new int[G.V()]; post = new int[G.V()]; postorder = new Queue<Integer>(); preorder = new Queue<Integer>(); marked = new boolean[G.V()]; for (int v = 0; v < G.V(); v++) if (!marked[v]) dfs(G, v); } // depth-first search preorder and postorder in an edge-weighted digraph public DepthFirstOrder(EdgeWeightedDigraph G) { pre = new int[G.V()]; post = new int[G.V()]; postorder = new Queue<Integer>(); preorder = new Queue<Integer>(); marked = new boolean[G.V()]; for (int v = 0; v < G.V(); v++) if (!marked[v]) dfs(G, v); } // run DFS in digraph G from vertex v and compute preorder/postorder private void dfs(Digraph G, int v) { marked[v] = true; pre[v] = preCounter++; preorder.enqueue(v); for (int w : G.adj(v)) { if (!marked[w]) { dfs(G, w); } } postorder.enqueue(v); post[v] = postCounter++; } // run DFS in edge-weighted digraph G from vertex v and compute preorder/postorder private void dfs(EdgeWeightedDigraph G, int v) { marked[v] = true; pre[v] = preCounter++; preorder.enqueue(v); for (DirectedEdge e : G.adj(v)) { int w = e.to(); if (!marked[w]) { dfs(G, w); } } postorder.enqueue(v); post[v] = postCounter++; } public int pre(int v) { return pre[v]; } public int post(int v) { return post[v]; } // return vertices in postorder as an Iterable public Iterable<Integer> post() { return postorder; } // return vertices in preorder as an Iterable public Iterable<Integer> pre() { return preorder; } // return vertices in reverse postorder as an Iterable public Iterable<Integer> reversePost() { Stack<Integer> reverse = new Stack<Integer>(); for (int v : postorder) reverse.push(v); return reverse; } // check that pre() and post() are consistent with pre(v) and post(v) private boolean check(Digraph G) { // check that post(v) is consistent with post() int r = 0; for (int v : post()) { if (post(v) != r) { StdOut.println("post(v) and post() inconsistent"); return false; } r++; } // check that pre(v) is consistent with pre() r = 0; for (int v : pre()) { if (pre(v) != r) { StdOut.println("pre(v) and pre() inconsistent"); return false; } r++; } return true; }}
public class Topological { private Iterable<Integer> order; // topological order // topological sort in a digraph public Topological(Digraph G) { DirectedCycle finder = new DirectedCycle(G); if (!finder.hasCycle()) { DepthFirstOrder dfs = new DepthFirstOrder(G); order = dfs.reversePost(); } } // topological sort in an edge-weighted digraph public Topological(EdgeWeightedDigraph G) { EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G); if (!finder.hasCycle()) { DepthFirstOrder dfs = new DepthFirstOrder(G); order = dfs.reversePost(); } } // return topological order if a DAG; null otherwise public Iterable<Integer> order() { return order; } // does digraph have a topological order? public boolean hasOrder() { return order != null; } public static void main(String[] args) { String filename = args[0]; String delimiter = args[1]; SymbolDigraph sg = new SymbolDigraph(filename, delimiter); Topological topological = new Topological(sg.G()); for (int v : topological.order()) { System.out.println(sg.name(v)); } }}
?
?
?
?
