TAILIEUCHUNG - Lecture Data structures and algorithms in Java (6th edition): Chapter 14.3 - Goodrich, Tamassia, Goldwasser

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 .

• Cơ sở dữ liệu
• Data structures
• Data structures and algorithms
• Computer science
• Design of data structures
• Algorithms in Java
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming