Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2009·March 23, 2010 9:28:26 PM4.2 Directed GraphsReferences: Algorithms in Java, 3rd edition, Chapter 19‣digraph API‣digraph search‣transitive closure‣topological sort‣strong components2Directed graphsDigraph. Set of vertices connected pairwise by oriented edges.AddressHolland TunnelNew York, NY 10013©2008 Google - Map data ©2008 Sanborn, NAVTEQ™ - Terms of UseTo see all the details that are visible on the screen,use the"Print" link next to the map.3Link structure of political blogsVertex = web page.Edge = hyperlink.Page ranks with histogram for a larger example18316421328324922451 1440487441041290391191230262146524374335473823163643 1727203415219 33258 0 .002 1 .017 2 .009 3 .003 4 .006 5 .016 6 .066 7 .021 8 .017 9 .040 10 .002 11 .028 12 .006 13 .045 14 .018 15 .026 16 .023 17 .005 18 .023 19 .026 20 .004 21 .034 22 .063 23 .043 24 .011 25 .005 26 .006 27 .008 28 .037 29 .003 30 .037 31 .023 32 .018 33 .013 34 .024 35 .019 36 .003 37 .031 38 .012 39 .023 40 .017 41 .021 42 .021 43 .016 44 .023 45 .006 46 .023 47 .024 48 .019 49 .0166 224Web graph5Ecological food web graphVertex = species.Edge: from producer to consumer.Vertex = synset.Edge = hypernym relationship.6WordNet graphĞǀĞŶƚŚĂƉƉĞŶŝŶŐ ŽĐĐƵƌƌĞŶĐĞ ŽĐĐƵƌƌĞŶt ŶĂƚƵƌĂůͺĞǀĞŶƚĐŚĂŶŐĞ ĂůƚĞƌĂƚŝŽŶ ŵŽĚŝĨŝĐĂƚŝŽŶĚĂŵĂŐĞ ŚĂƌm ŝŵƉĂŝƌŵĞŶƚƌƵŶ ůĂĚĚĞƌ ƌĂǀĞ ůƚƌĂŶƐŝƚŝŽŶůĞĂƉ ũƵŵƉ ƐĂůƚĂƚŝŽŶũƵŵƉ ůĞĂƉĂĐt ŚƵŵĂŶͺĂĐƚŝŽŶ ŚƵŵĂŶͺĂĐƚŝǀŝƚLJŐƌŽƵƉͺĂĐƚŝŽŶĨŽƌĨĞŝƚ ĨŽƌĨĞŝƚƵƌĞƐĂĐƌŝĨŝĐĞĂĐƚŝŽŶĐŚĂŶŐĞƌĞƐŝƐƚĂŶĐĞ ŽƉƉŽƐŝƚŝŽŶƚƌĂŶƐŐƌĞƐƐŝŽŶĚĞŵŽƚŝŽŶǀĂƌŝĂƚŝŽŶŵŽƚŝŽŶ ŵŽǀĞŵĞŶt ŵŽǀĞůŽĐŽŵŽƚŝŽŶ ƚƌĂǀĞůƌƵŶ ƌƵŶŶŝŶŐĚĂƐŚ ƐƉƌŝŶƚĚĞƐĐĞŶƚũƵŵƉ ƉĂƌĂĐŚƵƚŝŶŐŝŶĐƌĞĂƐĞŵŝƌĂĐůĞŵŝƌĂĐůĞ^ƵŶĚĂLJ DĂƌĐŚ Ϯϵ ϮϬϬϵϭϭϯϯ WD 8QILOHG 1RWHV 3DJH 7Digraph applicationsgraphvertexedgetransportationstreet intersectionone-way streetwebweb pagehyperlinkfood webspeciespredator-prey relationshipWordNetsynsethypernymschedulingtaskprecedence constraintfinancialstock, currencytransactioncell phonepersonplaced callinfectious diseasepersoninfectiongameboard positionlegal movecitationjournal articlecitationobject graphobjectpointerinheritance hierarchyclass inherits fromcontrol flowcode blockjump8Some digraph problemsPath. Is there a directed path from s to t?Shortest path. What is the shortest directed path from s and t?Strong connectivity. Are all vertices mutually reachable?Transitive closure. For which vertices v and w is there a path from v to w?Topological sort. Can you draw the digraph so that all edges pointfrom left to right?Precedence scheduling. Given a set of tasks with precedence constraints,how can we best complete them all?PageRank. What is the importance of a web page?9‣digraph API‣digraph search‣topological sort‣transitive closure‣strong components10Digraph API public class Digraph public class Digraphdigraph data typedigraph data typeDigraph(int V)Digraph(int V)create an empty digraph with V verticesDigraph(In in)Digraph(In in)create a digraph from input streamvoidaddEdge(int v, int w)addEdge(int v, int w)add an edge from v to wIterable<Integer>adj(int v)adj(int v)return an iterator over the neighbors of vint V()V()return number of verticesint E()E()return number of edgesDigraphreverse()reverse()return reverse of this digraph (all edges reversed) In in = new In(); Digraph G = new Digraph(in); for (int v = 0; v < G.V(); v++) for (int w : G.adj(v)) /* process edge v!w */% more tinyDG.txt 13 13 0 1 0 2 0 5 0 6 4 3 5 3 5 4 6 4 7 8 9 10 9 11 9 12 11 1211Set of edges representationStore a list of the edges (linked list or array). 0 1 0 2 0 5 0 6 4 3 5 3 5 4 6 4 7 8 9 10 9 11 9 12 11 12064215371210911812Adjacency-matrix representationMaintain a two-dimensional V-by-V boolean array;for each edge v ! w in the digraph: adj[v][w] = true.012345678910111201234567891011120110011000000000000000000000000000000000000000000000000100000000000011000000000000100000000000000001000000000000000000000000000111000000000000000000000000010000000000000fromto0642153712109118Note: parallel edges disallowedMaintain vertex-indexed array of lists (use Bag abstraction).13Adjacency-list representation5 2 1 63434810 11 1212same as undirected graph,but one entry for each edge0:1:2:3:4:5:6:7:8:9:10:11:12:0642153712109118Same as Graph, but only insert one copy of each edge.14Adjacency-lists representation: Java implementationpublic class Digraph{ private final int V; private final Bag<Integer>[] adj; public Digraph(int V) { this.V = V; adj = (Bag<Integer>[]) new Bag[V]; for (int v = 0; v < V; v++) adj[v] = new Bag<Integer>(); } public void addEdge(int v, int w) { adj[v].add(w); } public Iterable<Integer> adj(int v) { return adj[v]; }}adjacency listscreate empty graph withV verticesadd edge from v to witerator for v's neighborsIn practice. Use adjacency-list representation.•Algorithms all based on iterating over edges incident to v.•Real-world digraphs tend to be sparse.15Digraph representationsrepresentationspaceinsert edgefrom v to wedge fromv to w?iterate over edgesleaving v?list of edgesE1 *EEadjacency matrixV211Vadjacency listE + V1 *outdegree(v)outdegree(v)adjacency setE + Vlog (outdegree(v))log (outdegree(v))outdegree(v)huge number of vertices,small average vertex degree* only if parallel edges allowed16‣digraph API‣digraph search‣transitive closure‣topological sort‣strong components17ReachabilityProblem. Find all vertices reachable from s along a directed path.sSame method as for undirected graphs.Every undirected graph is a digraph.•Happens to have edges in both directions.•DFS is a digraph algorithm.18Depth-first search in digraphsMark s as visited.Recursively visit all unmarked vertices w adjacent to s.DFS (to visit a vertex s)19Depth-first search (single-source reachability)Identical to undirected version (substitute Digraph for
View Full Document
Unlocking...