Directed Graphs BOS ORD JFK SFO LAX DFW MIA 2010 Goodrich Tamassia Directed Graphs 1 Digraphs A digraph is a graph whose edges are all directed E D Short for directed graph C Applications B one way streets flights task scheduling 2010 Goodrich Tamassia Directed Graphs A 2 E Digraph Properties D C B A graph G V E such that Each edge goes in one direction A Edge a b goes from a to b but not b to a If G is simple m n n 1 If we keep in edges and out edges in separate adjacency lists we can perform listing of incoming edges and outgoing edges in time proportional to their size 2010 Goodrich Tamassia Directed Graphs 3 Digraph Application Scheduling edge a b means task a must be completed before b can be started ics21 ics22 ics23 ics51 ics53 ics52 ics161 ics131 ics141 ics121 The good life ics151 2010 Goodrich Tamassia ics171 Directed Graphs 4 Directed DFS We can specialize the traversal algorithms DFS and BFS to digraphs by traversing edges only along their direction In the directed DFS algorithm we have four types of edges discovery edges back edges forward edges cross edges D C B A directed DFS starting at a vertex s determines the vertices reachable from s 2010 Goodrich Tamassia E Directed Graphs A 5 Directed DFS Back edge v w w is an ancestor of v in the tree of discovery edges E Forward edge v w v is an ancestor but not the parent of w in the tree of discovery edges Cross edge v w w is in the same level as v or in the next level in the tree of discovery edges D C B Discovery edge v w v is the parent of w in the tree of discovery edges Directed Graphs A 6 Reachability DFS tree rooted at v vertices reachable from v via directed paths E E D C D C F A E A B C A 2010 Goodrich Tamassia D Directed Graphs F B 7 Strong Connectivity Each vertex can reach all other vertices a g c d e b f 2010 Goodrich Tamassia Directed Graphs 8 Strong Connectivity How do you determine if a digraph is strongly connected a g c d e b f 2010 Goodrich Tamassia Directed Graphs 9 Strong Connectivity Algorithm Pick a vertex v in G Perform a DFS from v in G G If there s a w not visited print no Else print yes Running time O n m Transpose of Graph G 2010 Goodrich Tamassia Directed Graphs g c If there s a w not visited print no d Let G be G with edges reversed Perform a DFS from v in G a e b f a G g c d e b f 10 Graph connectivity Strongly 2010 Goodrich Tamassia Directed Graphs 11 Graph connectivity Strongly 2010 Goodrich Tamassia Directed Graphs 12 Strongly Connected Components Maximal subgraphs such that each vertex can reach all other vertices in the subgraph Can also be done in O n m time using DFS but is more complicated similar to biconnectivity a g a c g c d e b f 2010 Goodrich Tamassia Directed Graphs f d e b 13 Transitive Closure Given a digraph G the transitive closure of G is the digraph G such that G has the same vertices as G if G has a directed path from u to v u v G has a directed edge from u to v The transitive closure provides reachability information about a digraph 2010 Goodrich Tamassia Directed Graphs D E B C G A D E B C A G 14 Computing the Transitive Closure We can perform DFS starting at each vertex If there s a way to get from A to B and from B to C then there s a way to get from A to C O n n m Alternatively Use dynamic programming The Floyd Warshall Algorithm 2010 Goodrich Tamassia Directed Graphs 15 Floyd Warshall Transitive Closure Idea 1 Number the vertices 1 2 n Idea 2 Consider paths that use only vertices numbered 1 2 k as intermediate vertices i Uses only vertices numbered 1 k add this edge if it s not already in j Uses only vertices numbered 1 k 1 k 2010 Goodrich Tamassia Uses only vertices numbered 1 k 1 Directed Graphs 16 Floyd Warshall s Algorithm Number vertices v1 vn Algorithm FloydWarshall G Input digraph G Compute digraphs G G 0 n Output transitive closure G of G G G 0 i 1 G has directed edge v v if k i j for all v G vertices G has a directed path from denote v as vi vi to vj with intermediate i i 1 vertices in G0 G v1 vk for k 1 to n do We have that G G n Gk Gk 1 In phase k digraph G is k for i 1 to n i k do computed from Gk 1 for j 1 to n j i k do Running time O n3 if Gk 1 areAdjacent vi vk assuming areAdjacent is Gk 1 areAdjacent vk vj O 1 e g adjacency if Gk areAdjacent vi vj matrix Gk insertDirectedEdge vi vj k return Gn Directed Graphs 17 2010 Goodrich Tamassia Floyd Warshall Example v7 BOS ORD v4 JFK v2 v6 SFO LAX v1 DFW v3 MIA v5 2010 Goodrich Tamassia Directed Graphs 18 Floyd Warshall Iteration 1 v7 BOS ORD v4 JFK v2 v6 SFO LAX v1 DFW v3 MIA v5 2010 Goodrich Tamassia Directed Graphs 19 Floyd Warshall Iteration 2 v7 BOS ORD v4 JFK v2 v6 SFO LAX v1 DFW v3 MIA v5 2010 Goodrich Tamassia Directed Graphs 20 Floyd Warshall Iteration 3 v7 BOS ORD v4 JFK v2 v6 SFO LAX v1 DFW v3 MIA v5 2010 Goodrich Tamassia Directed Graphs 21 Floyd Warshall Iteration 4 v7 BOS ORD v4 JFK v2 v6 SFO LAX v1 DFW v3 MIA v5 2010 Goodrich Tamassia Directed Graphs 22 Floyd Warshall Iteration 5 v7 BOS ORD v4 JFK v2 v6 SFO LAX v1 DFW v3 MIA v5 2010 Goodrich Tamassia Directed Graphs 23 Floyd Warshall Iteration 6 v7 BOS ORD v4 JFK v2 v6 SFO LAX v1 DFW v3 MIA v5 2010 Goodrich Tamassia Directed Graphs 24 Floyd Warshall Conclusion v 7 BOS ORD v4 JFK v2 v6 SFO LAX v1 DFW v3 MIA v5 2010 Goodrich Tamassia Directed Graphs 25 Transitive closure 2010 Goodrich Tamassia Directed Graphs 26 Transitive closure 2010 Goodrich Tamassia Directed Graphs 27 Transitive closure 3 1 2 2010 Goodrich Tamassia Directed Graphs 4 28 Transitive closure 3 1 2 2010 Goodrich Tamassia Directed Graphs 4 29 DAGs and Topological Ordering D A directed acyclic graph DAG is a digraph that has no directed cycles A topological ordering of a digraph is a numbering v1 vn B C A of the vertices such that for every edge vi vj we have i j Example in a task scheduling digraph a topological ordering a task sequence that satisfies the precedence constraints Theorem A digraph admits a topological ordering if and only …
View Full Document
Unlocking...