Topological sort

• Topological sort


  An ordering of vertices in a directed acyclic graph, such that if there is a path from v to v, then v appears after v in the ordering
• A topological ordering is not possible if the graph has a cycle, since for two vertices v and w on the cycle, v precedes w and w precedes v
• The ordering is not necessarily unique; any legal ordering will do
• Simple algorithm to find a topological ordering


  1. Find any vertex with no incoming edges

  2. Print this vertex and remove it, along with its edges, from the graph

  3. Apply this same strategy to the rest of the graph
• Indegree of a vertex v


  The number of edges (u, v)
• Algorithm to generate a topological ordering


  1. Compute the indegrees of all vertices in the graph

  2. Find a vertex with indegree 0 that has not already been assigned a topological number

  3. Assign the vertex the next topological number

  4. Decrement the indegree of all vertices adjacent to the assigned vertex

  5. Repeat until all vertices have been assigned a topological number
• If the graph has a cycle, the algorithm will not be able to find a vertex with indegree 0, indicating that the graph has a cycle
• Improved algorithm to generate a topological ordering


  1. Compute the indegrees of all vertices in the graph

  2. Place all vertices with indegree 0 in a queue

  3. While the queue is not empty, remove a vertex v from the queue, assign it the next topological number, and decrement the indegree of all vertices adjacent to v. If a vertex's indegree falls to 0, enqueue it.

  4. If the number of vertices assigned a topological number is not equal to the total number of vertices, the graph has a cycle
• The time complexity of the improved algorithm is O(|E| + |V|) if adjacency lists are used