Graph Traversals and Topological Sort

1 .CSE 373 : Data Structures & Algorithms Graph Traversals / Topological Sort Riley Porter Winter 2017 CSE373: Data Structures & Algorithms 1

2 .Course Logistics HW4 out  graphs! Midterms back in section tomorrow. Regrade policy on the website. 2 CSE373: Data Structures & Algorithms

3 .Graphs Review from last time What is some of the terminology for graphs and what do those terms mean? vertices and edges directed / undirected in-degree and out-degree connected and fully connected weighted / unweighted acyclic DAG: Directed Acyclic Graph 3 CSE373: Data Structures & Algorithms

4 .Graphs Applications Review For each of the following examples: what are the vertices and what are the edges ? would you use directed edges ? Would they have self-edges ? Are there 0 -degree nodes ? Is it strongly or weakly connected? Does it have weights? Do negative weights make sense ? Does it have cycles? Is it a DAG? Web pages with links Facebook friends Methods in a program that call each other Road maps (e.g., Google maps) Airline routes Family trees Course pre-requisites Political donations to candidates CSE373: Data Structures & Algorithms 4

5 .Graph Traversals 5 CSE373: Data Structures & Algorithms

6 .Graph Traversals For an arbitrary graph and a starting node v , find all nodes reachable from v (i.e., there exists a path from v ) Possibly “do something” for each node Examples: print to output, set a field, etc. Also solves : Is an undirected graph connected? Related but different problem : Is a directed graph strongly connected? Basic idea of traversal: Keep following nodes But “mark” nodes after visiting them, so the traversal terminates and processes each reachable node exactly once 6 CSE373: Data Structures & Algorithms

7 .Abstract Idea in Pseudocode 7 CSE373: Data Structures & Algorithms void traverseGraph (Node start ) { Set pending = emptySet () pending.add ( start ) mark start as visited while ( pending is not empty) { next = pending.remove () for each node u adjacent to next if ( u is not marked visited ) { mark u pending .add ( u ) } } }

8 .Running Time and Options Assuming add and remove for pending set are O (1), entire traversal is O (|E| ) using an adjacency list representation The order we traverse depends entirely on add and remove Popular choice: a stack “depth-first graph search”  DFS Popular choice: a queue “breadth-first graph search”  BFS DFS and BFS are “big ideas” in computer science Depth: recursively explore one part before going back to the other parts not yet explored Breadth: explore areas closer to the start node first Cool visualization: http://visualgo.net/dfsbfs.html CSE373: Data Structures & Algorithms 8

9 .Example: trees A tree is a graph and make DFS and BFS are easier to “ see” 9 CSE373: Data Structures & Algorithms A B D E C F H G DFS (Node start) { mark and process start for each node u adjacent to start if u is not marked DFS(u) } A, B, D, E, C, F, G, H Exactly what we called a “pre-order traversal” for trees The marking is because we support arbitrary graphs and we want to process each node exactly once

10 .Example: trees 10 CSE373: Data Structures & Algorithms A B D E C F H G DFS2 ( Node start) { initialize stack s to hold start mark start as visited while(s is not empty) { next = s.pop () // and “process” for each node u adjacent to next if(u is not marked) mark u and push onto s } } A, C, F , H, G, B, E, D A different but perfectly fine depth traversal

11 .Example: trees 11 CSE373: Data Structures & Algorithms A B D E C F H G BFS (Node start) { initialize queue q to hold start mark start as visited while(q is not empty) { next = q.dequeue () // and “process” for each node u adjacent to next if(u is not marked) mark u and enqueue onto q } } A, B, C, D, E, F, G, H A “level-order” traversal

12 .Comparison Breadth-first always finds shortest length paths , i.e., “optimal solutions” Better for “what is the shortest path from x to y ” But depth-first can use less space in finding a path If longest path in the graph is p and highest out-degree is d then DFS stack never has more than d*p elements But a queue for BFS may hold O (|V|) nodes A third approach (useful in Artificial Intelligence) Iterative deepening (IDFS) : Try DFS but disallow recursion more than K levels deep If that fails, increment K and start the entire search over Like BFS, finds shortest paths. Like DFS, less space. 12 CSE373: Data Structures & Algorithms

13 .Saving the Path Our graph traversals can answer the reachability question: “Is there a path from node x to node y?” But what if we want to actually output the path? Like getting driving directions rather than just knowing it’s possible to get there! How to do it: Instead of just “marking” a node, store the previous node along the path (when processing u causes us to add v to the search, set v .path field to be u ) When you reach the goal, follow path fields back to where you started (and then reverse the answer) If just wanted path length , could put the integer distance at each node instead 13 CSE373: Data Structures & Algorithms

14 .Example using BFS 14 CSE373: Data Structures & Algorithms Seattle San Francisco Dallas Salt Lake City What is a path from Seattle to Atlanta Remember marked nodes are not re- enqueued Note shortest paths may not be unique Chicago Atlanta 1 1 1 2 3 0

15 .Topological Sort 15 CSE373: Data Structures & Algorithms

16 .Topological Sort Problem : Given a DAG G=(V,E) , output all vertices in an order such that no vertex appears before another vertex that has an edge to it Example input: One example output: 126, 142, 143, 374, 373, 417, 410, 413, XYZ, 415 16 CSE373: Data Structures & Algorithms Disclaimer: Don ’ t base your course schedules on this Material . Please… CSE 142 CSE 143 CSE 374 CSE 373 CSE 410 MATH 126 CSE 417 CSE 415 CSE 413 XYZ

17 .Questions and comments Why do we perform topological sorts only on DAGs? Because a cycle means there is no correct answer Is there always a unique answer? No, there can be 1 or more answers; depends on the graph Graph with 5 topological orders: Do some DAGs have exactly 1 answer? Yes, including all lists Terminology: A DAG represents a partial order and a topological sort produces a total order that is consistent with it 17 CSE373: Data Structures & Algorithms 0 1 3 2 4

18 .Uses of Topological Sort Figuring out how to graduate Computing an order in which to recompute cells in a spreadsheet Determining an order to compile files using a Makefile In general, taking a dependency graph and finding an order of execution … 18 CSE373: Data Structures & Algorithms

19 .A First Algorithm for Topological Sort Label (“mark”) each vertex with its in-degree Think “write in a field in the vertex” Could also do this via a data structure (e.g., array) on the side While there are vertices not yet output: Choose a vertex v with labeled with in-degree of 0 Output v and conceptually remove it from the graph For each vertex u adjacent to v (i.e. u such that ( v , u ) in E ), decrement the in-degree of u 19 CSE373: Data Structures & Algorithms

20 .Example Output: 20 CSE373: Data Structures & Algorithms Node: 126 142 143 374 373 410 413 415 417 XYZ Removed? In-degree: 0 0 2 1 1 1 1 1 1 3 CSE 142 CSE 143 CSE 374 CSE 373 CSE 410 MATH 126 CSE 417 CSE 415 CSE 413 XYZ

21 .Example Output: 126 21 CSE373: Data Structures & Algorithms Node: 126 142 143 374 373 410 413 415 417 XYZ Removed? x In-degree: 0 0 2 1 1 1 1 1 1 3 1 CSE 142 CSE 143 CSE 374 CSE 373 CSE 410 MATH 126 CSE 417 CSE 415 CSE 413 XYZ

22 .Example Output: 126 142 22 CSE373: Data Structures & Algorithms Node: 126 142 143 374 373 410 413 415 417 XYZ Removed? x x In-degree: 0 0 2 1 1 1 1 1 1 3 1 0 CSE 142 CSE 143 CSE 374 CSE 373 CSE 410 MATH 126 CSE 417 CSE 415 CSE 413 XYZ

23 .Example Output: 126 142 143 23 CSE373: Data Structures & Algorithms Node: 126 142 143 374 373 410 413 415 417 XYZ Removed? x x x In-degree: 0 0 2 1 1 1 1 1 1 3 1 0 0 0 CSE 142 CSE 143 CSE 374 CSE 373 CSE 410 MATH 126 CSE 417 CSE 415 CSE 413 XYZ

24 .Example Output: 126 142 143 374 24 CSE373: Data Structures & Algorithms Node: 126 142 143 374 373 410 413 415 417 XYZ Removed? x x x x In-degree: 0 0 2 1 1 1 1 1 1 3 1 0 0 2 0 CSE 142 CSE 143 CSE 374 CSE 373 CSE 410 MATH 126 CSE 417 CSE 415 CSE 413 XYZ

25 .Example Output: 126 142 143 374 373 25 CSE373: Data Structures & Algorithms Node: 126 142 143 374 373 410 413 415 417 XYZ Removed? x x x x x In-degree: 0 0 2 1 1 1 1 1 1 3 1 0 0 0 0 0 0 2 0 CSE 142 CSE 143 CSE 374 CSE 373 CSE 410 MATH 126 CSE 417 CSE 415 CSE 413 XYZ

26 .Example Output: 126 142 143 374 373 417 26 CSE373: Data Structures & Algorithms Node: 126 142 143 374 373 410 413 415 417 XYZ Removed? x x x x x x In-degree: 0 0 2 1 1 1 1 1 1 3 1 0 0 0 0 0 0 2 0 CSE 142 CSE 143 CSE 374 CSE 373 CSE 410 MATH 126 CSE 417 CSE 415 CSE 413 XYZ

27 .Example Output: 126 142 143 374 373 417 410 27 CSE373: Data Structures & Algorithms Node: 126 142 143 374 373 410 413 415 417 XYZ Removed? x x x x x x x In-degree: 0 0 2 1 1 1 1 1 1 3 1 0 0 0 0 0 0 2 0 1 CSE 142 CSE 143 CSE 374 CSE 373 CSE 410 MATH 126 CSE 417 CSE 415 CSE 413 XYZ

28 .Example Output: 126 142 143 374 373 417 410 413 28 CSE373: Data Structures & Algorithms Node: 126 142 143 374 373 410 413 415 417 XYZ Removed? x x x x x x x x In-degree: 0 0 2 1 1 1 1 1 1 3 1 0 0 0 0 0 0 2 0 1 0 CSE 142 CSE 143 CSE 374 CSE 373 CSE 410 MATH 126 CSE 417 CSE 415 CSE 413 XYZ

29 .Example Output: 126 142 143 374 373 417 410 413 XYZ 29 CSE373: Data Structures & Algorithms Node: 126 142 143 374 373 410 413 415 417 XYZ Removed? x x x x x x x x x In-degree: 0 0 2 1 1 1 1 1 1 3 1 0 0 0 0 0 0 2 0 1 0 CSE 142 CSE 143 CSE 374 CSE 373 CSE 410 MATH 126 CSE 417 CSE 415 CSE 413 XYZ