DFS-based sort
- Algorithms course
- Advanced
- Lesson 46/56
- 4 min
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.
Practice compute_indegree function
Write compute_indegree(graph). Compute each node's in-degree, return the array. Print it with print(compute_indegree(init_graph())).
Starter code
def init_graph():
# Return adjacency list
return [[1, 2], [3], [3], []]
def compute_indegree(graph):
# Compute in-degreesSample 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()))Expected output
[0, 1, 1, 2]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 In-degree
indegree[____] += 1indegree[v] += 1Explanation: v is right.
2 What is the in-degree of node 3?
- 0
- 2 Correct answer
- 1
- 3
Explanation: Edges come from 1 and 2, so the in-degree is 2.
3 DFS-based sort: match the terms
| Term | Meaning |
|---|---|
0 |
independent |
1 |
0→1 |
2 |
0→2 |
3 |
1,2→3 |