DEV Community

Karhik Suryadevara
Karhik Suryadevara

Posted on

2 2

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
img
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
Enter fullscreen mode Exit fullscreen mode

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

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more