Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
This chapter provides knowledge of digraphs. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Directed Graphs 3/29/14 21:36 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Directed Graphs BOS ORD JFK SFO LAX DFW MIA © 2014 Goodrich, Tamassia, Goldwasser Directed Graphs 1 Digraphs q A digraph is a graph whose edges are all directed n q n n D Short for “directed graph” Applications n E C one-way streets flights task scheduling © 2014 Goodrich, Tamassia, Goldwasser B A Directed Graphs 2 1 Directed Graphs 3/29/14 21:36 E Digraph Properties D C q n n q q 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 © 2014 Goodrich, Tamassia, Goldwasser Directed Graphs 3 Digraph Application q Scheduling: edge (a,b) means task a must be completed before b can be started cs21 cs22 cs46 cs51 cs53 cs52 cs161 cs131 cs141 cs121 The good life cs151 © 2014 Goodrich, Tamassia, Goldwasser cs171 Directed Graphs 4 2 Directed Graphs 3/29/14 21:36 Directed DFS q q 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 n n n n q E D discovery edges back edges forward edges cross edges C B A directed DFS starting at a vertex s determines the vertices reachable from s © 2014 Goodrich, Tamassia, Goldwasser A Directed Graphs 5 Reachability q DFS tree rooted at v: vertices reachable from v via directed paths E E D C A C F A E B D C A © 2014 Goodrich, Tamassia, Goldwasser D Directed Graphs F B 6 3 Directed Graphs 3/29/14 21:36 Strong Connectivity q Each vertex can reach all other .
