Posted on

# 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:
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