Topological Sorting in a directed acyclic graph(DAG)

What is Topological Sort ?

It is an ordering of vertices in DAG, such that for every edge u to v, u comes before v.

Important point to note
1) It is not possible to do a topological sort if the graph has a cycle, since in a cycle it is impossible to know the order of vertices
2) There can be many possible orders of topological sorting

Example

Possible Topological Orders:

[1, 2, 3, 4, 5, 6, 7, 8]
[3, 2, 1, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 7, 6, 5, 8]

Uses of topological sorting

1) Managing tasks which are dependent on other tasks, suppose task B can only be completed if task A has been completed. So the graph would be:
A --> B
and the topological order would be [A, B].
2) Managing courses and prerequisite courses, for example we have an Algebra(Al) course which has a prerequisite of Basic-Math(BM) course, the graph would be:
BM --> Al
and the topological order would be [BM, Al] meaning a student should complete BM course before taking Al course.

Algorithm

We need a hash set to store the vertices we have visited and a stack to store the order.

1) Pick a vertex(v) let's name it current-vertex from the graph and

2) If the current-vertex is not in hash set

• add the current vertex to hash set
• get all the children of current-vertex and recursively call the step 2 for each child vertex
• add the current-vertex to stack

3) reverse the stack, and we get the topological order

Code

    def topological_sort(self, graph, seen, stk, current_vertex):
        # 2) if current_vertex not in hash set
        if current_vertex not in seen:
            seen.add(current_vertex)
            current_vertex_children = graph[current_vertex]
            for child in current_vertex_children:
                self.topological_sort(graph, seen, stk, child)
            stk.append(current_vertex)


    # *** Main function ***
    def topoSort(self, v, graph):
        # v = no of vertices in the graph
        # graph is represented using an adjacency list
        stk = []
        seen = set()
        # 1) pick a vertex
        for vertex in range(v):
            self.topological_sort(graph, seen, stk, vertex)
        # 3) reverse the stk
        stk.reverse()
        return stk

Problems which can be solved using topological sort

Implementing topological sort for a DAG: geeks-for-geeks-problem-link

Order of courses in topological order: leetcode-problem-link

Check if all the courses can be completed: leetcode-problem-link