Topological Sorting

The figure on the left is a directed acyclic graph (DAG) representation for the following table, which contains information of dependencies between cources.

No.	Course Name	Prerequisites	Number of Prerequisites
1	Calculus	-	0
2	Linear Algebra	-	0
3	Probability Theory	Calculus	1
4	Information Theory	Probability Theory	1
5	Vector Calculus	Calculus, Linear Algebra	2
6	Mathematical Statistics	Probability Theory, Information Theory, Vector Calculus	3

Our goal is to find the topological order for all nodes.

• Arrange all nodes in a linear order while preserving their original dependencies.

Process

Initialize the result list and indegree table for each node:

• result = []
• indegree = [0, 0, 1, 1, 2, 3], where each value represents the number of prerequisites for the corresponding node.

Find nodes with 0 indegree: Nodes 1 and 2.

• Insert them into the result list: result = [1, 2]
• Remove them along with any outgoing edges.
• Update the indegree table: indegree = [0, 0, 0, 1, 0, 3]

Find the next nodes with 0 indegree: Nodes 3 and 5.

• Insert them into the result list: result = [1, 2, 3, 5]
• Remove them along with any outgoing edges.
• Update the indegree table: indegree = [0, 0, 0, 0, 0, 1]

Find the next node with 0 indegree: Node 4.

• Insert it into the result list: result = [1, 2, 3, 5, 4]
• Remove it along with any outgoing edges.
• Update the indegree table: indegree = [0, 0, 0, 0, 0, 0]

Find the next node with 0 in-degree: Node 6.

• Insert it into the result list: result = [1, 2, 3, 5, 4, 6]
• Since all nodes have been inserted, the process is complete.
• The final result list is the answer.

Code

from collections import deque

v = 6

# edges[x].append(y): x -> y
edges = [[], # Node 0: not used.
         [3, 5], 
         [5],
         [4, 6],
         [6],
         [6],
         [] # Node 6: there is no outgoing edge.
]

# indegree = [0] * (v + 1)
# indegree[y] += 1
indegree = [0, 0, 0, 1, 1, 2, 3]

# Use a queue to process nodes in correct order
queue = deque()
result = []

# Step 1: Find initial nodes with in-degree 0
for i in range(1, v + 1):  # Ignore node 0
    if indegree[i] == 0:
        queue.append(i)

# Step 2: Process nodes in topological order
while queue:
    node = queue.popleft()
    result.append(node)

    # Reduce in-degree for neighbors
    for neighbor in edges[node]:
        indegree[neighbor] -= 1
        if indegree[neighbor] == 0:  # If in-degree becomes 0, add to queue for processing
            queue.append(neighbor)

print(result)