Topological Sort

  • A topological sort of a dag (directed acyclic graph) G=(V,E)G = (V, E) is a linear ordering of all its vertices such that ifif G contains an edge (v,w)(v, w), then vv appears before ww in the ordering. In other words, it is the ordering of the vertices that respects the direction of the edges. (If the graph contains a cycle, then no linear ordering is possible.)

  • For example, we can imagine using topological sort to plan a course schedule. (Although it would be difficult to graduate on time if we could only take one class at a time.)

  • The algorithm is quite simple and uses post-order depth-first search.

    We record the DFS postorder from every vertex with in-degree zero (i.e. has no incoming edges). If we reverse the post-order traversal, we will get the topological sort. It is indeed somewhat miraculous and amazing!

results matching ""

    No results matching ""