Topological Sort

4 min readOct 17, 2022

A topological ordering is only possible in directed acyclic graph(DAG). Any DAG can have more than one topological orderings. In this story, we use Kahn’s Algorithm and DFS with White-Grey-Black Cycle Detection to perform topological sort.

Table of Contents· Topological Sort/Ordering
· Degree of Vertex in a Graph
· Method1: Kahn’s Algorithm
  ∘ Graphical Explanation
  ∘ Code Implementation
    ∘ Complexity
    ∘ Golang
    ∘ Python
· Method2: Depth First Search(DFS) + White-Grey-Black Cycle Detection
  ∘ Graphical Explanation
  ∘ Code Implementation
    ∘ Complexity
    ∘ Golang
    ∘ Python

Topological Sort/Ordering

Topological sort is a graph traversal that every node in the graph is visited until all of its dependencies are visited. Only directed acyclic graph(DAG) can have topological orderings which can align all the nodes in a linear line. A directed graph without cycles can have multiple topological orderings.

Degree of Vertex in a Graph

Indegree: the number of edges coming to the vertex
Outdegree: the number of edges coming out the vertex

Method1: Kahn’s Algorithm

Kahn’s algorithm is used to perform a topological sort by keeping track of the indegree of each node in the graph. It repeatedly removes nodes with zero indegree from the graph and add them to the topological ordering until no nodes with zero indegree can be found.

Graphical Explanation

step1: initialize a indegree hash map with all values 0, sources queue and order array.

indegree: a hash map stores the current indegree of each node
sources: a queue contains nodes with zero indegree
order: an array stores nodes in topological ordering

step2: count the indegree of each node
step3: add nodes with zero indegree to sources

step4: sources is not empty
- 4.a: remove a node from the front of sources and add the node to order
- 4.b: decrement the indegree by one for all neighbors
- 4.c: If any neighbor has zero indegree after 4.b operation, add it to sources
step5: repeat step4 until sources is empty
step6: check if the number of nodes in order equals to the number of nodes in the graph

equal: a topological sorted result
non-equal: a cycle is detected in the graph

Code Implementation

Complexity

Time: O(v + e)
Space: O(v), auxiliary data structure: hash map and queue
v: the total number of vertices in the graph
e: the total number of edges in the graph

Golang

Python

Method2: Depth First Search(DFS) + White-Grey-Black Cycle Detection

This approach incorporates DFS traversal and white-grey-black cycle detection technique. This is quite similar to the process of Detect Cycle in a Directed Graph except we need to store the topological sort result. You can check my story, Detect Cycle in a Graph, to get more details.