DFS-based sort

Reverse DFS finish times for a topological order.

In-degree

A node's in-degree is the number of edges coming into it. Nodes with zero in-degree come first in the order.

Kahn's algorithm adds zero in-degree nodes to a queue and removes them one by one to build the order.

Degree array

The in-degrees of all nodes are collected in a single array. This array defines the initial state of Kahn's algorithm.

The degree array summarizes dependencies. Zero-degree nodes are independent and processed first.

Exercise compute_indegree function

Write compute_indegree(graph). Compute each node's in-degree, return the array. Print it with print(compute_indegree(init_graph())).

Show example solution

def init_graph():
    # Return adjacency list
    return [[1, 2], [3], [3], []]
def compute_indegree(graph):
    # Compute in-degrees
    n = len(graph)
    indegree = [0] * n
    for u in range(n):
        for v in graph[u]:
            indegree[v] += 1
    return indegree
print(compute_indegree(init_graph()))

Test yourself

In-degree
```
indegree[____] += 1
```
Show answer
```
indegree[v] += 1
```
What is the in-degree of node 3?
- 0
- 2
- 1
- 3
Show answer

2 — Edges come from 1 and 2, so the in-degree is 2.
DFS-based sort: match the terms

0

independent
1

0→1
2

0→2
3

1,2→3

Next lesson: Kahn algorithm

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies