CSE332 Data Abstractions Lecture 16 Topological Sort Graph Traversals Tyler Robison Summer 2010 1 Topological Sort Problem Given a DAG G V E output all the vertices in order such that if no vertex appears before any other vertex that has an edge to it CSE 331 Example input CSE 440 CSE 332 CSE 142 MATH 126 CSE 143 CSE 311 CSE 341 CSE 312 CSE 351 CSE 333 CSE 352 Example output 142 126 143 311 331 332 312 341 351 333 440 352 2 Questions and comments Why do we perform topological sorts only on DAGs Is there always a unique answer No there can be 1 or more answers depends on the graph What DAGs have exactly 1 answer Because a cycle means there is no correct answer Lists Terminology A DAG represents a partial order and a topological sort produces a total order that is consistent with it 3 Uses Figuring out how to finish your degree Computing the order in which to recompute cells in a spreadsheet Determining the order to compile files using a Makefile In general taking a dependency graph and coming up with an order of execution 4 A first algorithm for topological sort 1 Label each vertex with its in degree 2 While there are vertices not yet output a b c 5 Labeling also called marking Think write in a field in the vertex though you could also do this with a data structure e g array on the side Choose a vertex v with labeled with in degree of 0 Output v and remove it conceptually 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 Example Output CSE 331 CSE 440 CSE 332 CSE 142 MATH 126 CSE 143 CSE 311 CSE 341 CSE 312 CSE 351 CSE 333 CSE 352 Node 126 142 143 311 312 331 332 333 341 351 352 440 Removed In degree 0 0 2 1 2 1 1 2 1 1 1 1 6 Example Output 126 CSE 331 CSE 440 CSE 332 CSE 142 MATH 126 CSE 143 CSE 311 CSE 341 CSE 312 CSE 351 CSE 333 CSE 352 Node 126 142 143 311 312 331 332 333 341 351 352 440 Removed x In degree 0 0 2 1 2 1 1 2 1 1 1 1 1 7 Example Output 126 142 CSE 331 CSE 440 CSE 332 CSE 142 MATH 126 CSE 143 CSE 311 CSE 341 CSE 312 CSE 351 CSE 333 CSE 352 Node 126 142 143 311 312 331 332 333 341 351 352 440 Removed x x In degree 0 0 2 1 2 1 1 2 1 1 1 1 1 0 8 Example Output 126 142 CSE 331 CSE 440 CSE 332 CSE 142 MATH 126 CSE 143 CSE 311 CSE 341 CSE 312 CSE 351 CSE 333 CSE 352 Node 126 142 143 311 312 331 332 333 341 351 352 440 Removed x x x In degree 0 0 2 1 2 1 1 2 1 1 1 1 1 0 0 0 0 0 9 143 Example Output 126 142 CSE 331 CSE 440 CSE 332 CSE 142 MATH 126 CSE 143 CSE 311 CSE 341 311 CSE 312 CSE 351 CSE 333 CSE 352 Node 126 142 143 311 312 331 332 333 341 351 352 440 Removed x x x x In degree 0 0 2 1 2 1 1 2 1 1 1 1 1 0 1 0 0 0 0 0 10 143 Example Output 126 142 CSE 331 CSE 440 CSE 332 CSE 142 MATH 126 CSE 143 CSE 311 CSE 341 311 CSE 312 CSE 351 CSE 333 CSE 352 Node 126 142 143 311 312 331 332 333 341 351 352 440 Removed x x x x x In degree 0 0 2 1 2 1 1 2 1 1 1 1 1 0 1 0 0 0 0 0 11 143 331 Example Output 126 142 CSE 331 CSE 440 CSE 332 CSE 142 MATH 126 CSE 143 CSE 311 CSE 341 311 CSE 333 CSE 352 Node 126 142 143 311 312 331 332 333 341 351 352 440 Removed x x x x x x In degree 0 0 2 1 2 1 1 2 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 12 331 332 CSE 312 CSE 351 143 Example Output 126 142 CSE 331 CSE 440 CSE 332 CSE 142 MATH 126 CSE 143 CSE 311 CSE 341 311 312 CSE 333 CSE 352 Node 126 142 143 311 312 331 332 333 341 351 352 440 Removed x x x x x x x In degree 0 0 2 1 2 1 1 2 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 13 331 332 CSE 312 CSE 351 143 Example Output 126 142 CSE 331 CSE 440 CSE 332 CSE 142 MATH 126 CSE 143 CSE 311 CSE 341 311 331 332 CSE 312 312 341 CSE 351 CSE 333 CSE 352 Node 126 142 143 311 312 331 332 333 341 351 352 440 Removed x x x x x x x x In degree 0 0 2 1 2 1 1 2 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 14 143 Example Output 126 142 CSE 331 CSE 440 CSE 332 CSE 142 MATH 126 CSE 143 CSE 311 CSE 341 311 331 332 CSE 312 312 341 CSE 351 CSE 333 CSE 352 Node 126 142 143 311 312 331 332 333 341 351 352 440 Removed x x x x x x x x x In degree 0 0 2 1 2 1 1 2 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 15 143 351 Example CSE 331 CSE 440 CSE 332 CSE 142 MATH 126 CSE 143 CSE 311 CSE 341 Output 126 142 143 311 331 CSE 312 CSE 351 CSE 333 CSE 352 Node 126 142 143 311 312 331 332 333 341 351 352 440 Removed x x x x x x x x x x x x In degree 0 0 2 1 2 1 1 2 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 16 332 312 341 351 333 352 440 A couple of things to note Needed a vertex with in degree of 0 to start No cycles Ties between vertices with in degrees of 0 can be broken arbitrarily 17 Potentially many different correct orders Running time labelEachVertexWithItsInDegree for ctr 0 ctr numVertices ctr v findNewVertexOfDegreeZero put v next in output for each w adjacent to v w indegree What is the worst case running time 18 Initialization O V Sum of all find new vertex O V 2 because each O V Sum of all decrements O E assuming adjacency list So total is O V 2 not good for a sparse graph …