Summary - Topological sort

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.

Exercise 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())).

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
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()))

Test yourself

When is topological sort not possible?
- Graph is empty
- Graph is single-node
- Graph is undirected
- Graph has a cycle
Show answer

Graph has a cycle — Sort is not possible if there is a cycle.
Add to order
```
order.____(u)
```
Show answer
```
order.append(u)
```
Summary - Topological sort: match the terms

init_graph

Graph
compute_indegree

Degree
kahn_sort

Sort
queue

Queue

Next lesson: Union-find

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies