This post is completed by 2 users

  • 1
 Add to List
Medium

268. Topological Sort

Topological Sort: A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Source: wiki

Example:

As in the image above, the topological order is 7 6 5 4 3 2 1 0. There can be one or more topological order in any graph. Like in the example above 7 5 6 4 2 3 1 0 is also a topological order.

Approach:

Shall we use Depth First Search?

The DFS of the example above will be ‘7 6 4 3 1 0 5 2’ but in topological sort  2 should appear before 1 and 5 should appear before 4. So it might look like we can use DFS but we cannot use DFS as it is but yes we can modify DFS to get the topological sort.

Read about DFS if you need to brush up about it.

Modified DFS:

  1. Use temporary stack to store the vertex.
  2. Maintain a visited [] to keep track of already visited vertices.
  3. In DFS we print the vertex and make recursive call to the adjacent vertices but here we will make the recursive call to the adjacent vertices and then push the vertex to stack.
  4. Observe closely the previous step, it will ensure that vertex will be pushed to stack only when all of its adjacent vertices (descendants) are pushed into stack.
  5. Finally print the stack.
  6. For disconnected graph, Iterate through all the vertices, during iteration, at a time consider each vertex as source (if not already visited).

Time Complexity: O(V+E)

Output:

Topological Sort:
7 6 5 4 3 2 1 0

Related Problems: