Topological Sort Applications

Computer Science II Data Structures Topological Sort Topological Sort • A topological sort of a directed graph is to place all vertices in a list such that if there is a path from v to w, v comes before w in the list. • The graph must be acyclic (no cycles exist) Applications • A topological sort is useful in something like a course prerequisite system, where you know what classes you need to take before

you can take others. • Planning and scheduling. Graph Algorithms: Topological Sort The topological sorting problem: given a directed, acyclic graph G = (V, E) , find a linear ordering of the vertices such that for all (v, w) in E, v precedes w in the ordering. A B C F D E Graph Algorithms: Topological Sort The topological sorting problem: given a directed, acyclic graph G = (V, E) , find a linear ordering of the vertices such that for all (v, w)  E, v precedes w in the ordering. A B C F D EA D E FB C 2010/11/3 2 Graph Algorithms: Topological Sort The topological sorting problem: given a directed, acyclic graph G = (V, E) , find a linear ordering of the vertices such that for all (v, w)  E, v precedes w in the ordering. A B C F D EA D E FB C Any linear ordering in which all the arrows go to the right. Graph Algorithms: Topological Sort The topological sorting problem: given a directed, acyclic graph G = (V, E) , find a linear ordering of the vertices such that for all (v, w)  E, v precedes w in the ordering. A B C F D FA D E EB C Any linear ordering in which all the arrows go to the right. This is not a topological ordering. Graph Algorithms: Topological Sort The topological sorting algorithm: Identify the subset of vertices that have no incoming edge. A B C F D E Graph Algorithms: Topological Sort The topological sorting algorithm: Identify the subset of vertices that have no incoming edge. (In general, this subset must be nonempty—why?) A B C F D E Graph Algorithms: Topological Sort The topological sorting algorithm: Identify the subset of vertices that have no incoming edge. (In general, this subset must be nonempty—because the graph is acyclic.) A B C F D E Graph Algorithms: Topological Sort The topological sorting algorithm: Identify the subset of vertices that have no incoming edge. Select one of them. A B C F D E 2010/11/3 3 Graph Algorithms: Topological Sort The topological sorting algorithm: Remove it, and its outgoing edges, and add it to the output. A B C F D E Graph Algorithms: Topological Sort The topological sorting algorithm: Again, identify the subset of vertices that have no incoming edge, . . ....

Website: www.cs.uiowa.edu | Filesize: -
No of Page(s): 8
Download Topological Sort Applications.pdf