# 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

## Top comments (0)