Summary - Topological sort
- Algorithms course
- Advanced
- Lesson 48/56
- 4 min
Print a topological order in a mini task.
Summary - Topological sort
In this group you learned topological sort, which finds the dependency order. Adjacency list, in-degree and Kahn algorithm combine into the solution.
Now you will write a function that brings all pieces together. This summary unites the group's concepts in a single piece of code.
Practice topological_order function
Write topological_order(graph). compute_indegree is given; sort with Kahn. Print [0, 1, 2, 3] with print(topological_order(init_graph())).
Starter code
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
def topological_order(graph):
# Find topological orderSample 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
def topological_order(graph):
# Find topological order
n = len(graph)
indegree = compute_indegree(graph)
queue = [i for i in range(n) if indegree[i] == 0]
order = []
while queue:
u = queue.pop(0)
order.append(u)
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return order
print(topological_order(init_graph()))Expected output
[0, 1, 2, 3]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 When is topological sort not possible?
- Graph is empty
- Graph is single-node
- Graph is undirected
- Graph has a cycle Correct answer
Explanation: Sort is not possible if there is a cycle.
2 Add to order
Question
order.____(u)
Answer
order.append(u)Explanation: append is right.
3 Summary - Topological sort: match the terms
| Term | Meaning |
|---|---|
init_graph |
Graph |
compute_indegree |
Degree |
kahn_sort |
Sort |
queue |
Queue |