Graphs
Topological Sort
Count: 10
Pre-Requisite: Depth-First Search, Breadth-First Search
When working with graphs, make sure you first practice using Depth-First Search (DFS) and Breadth-First Search (BFS) to solve coding interview questions, as they are the most common graph algorithms you'll encounter.
This section covers Topological Sort, an important but less common graph algorithm.
Topological sort takes a directed acyclic graph (DAG) and turns it into a linear ordering of nodes such that the directed edges only point forward, from left-to-right:
In more formal terms, a topological sort is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before vertex v in the ordering.
A given graph may have more than one valid topological sorts. We'll look at one algorithm for finding a topological sort - Kahn's Algorithm, which uses the concept of indegrees.
Indegrees
Each node in a graph has an indegree, which is the number of incoming edges to that node.
Calculate Indegrees
List of Edges
If our graph is given to us as list of edges, we can calculate the indegree of each node by iterating through the edges and incrementing the indegree of the destination node.
DESCRIPTION
You are given a graph with n nodes, where each node has an integer value from 0 to n - 1.
The graph is represent by a list of edges, where edges[i] = [u, v] is a directed edge from node u to node v. Write a function to calculate the indegree of each node in the graph.
Example
Input:
edges = [(0, 1), (1, 2), (1, 3), (3, 2), (3, 4)]
n = 5
Output:
[0, 1, 2, 1, 1]
Note that we can output the indegrees as an array because the nodes are numbered from 0 to n - 1. (We can look up the indegree of node i at index i in the array.) If the nodes were numbered differently, we would need a dictionary to map each node to its indegree.
Solution
def indegree(n, edges):indegree = [0] * nfor u, v in edges:indegree[v] += 1return indegree
Adjacency List
If our graph is given to us as an adjacency list, we can calculate the indegree of each node by iterating through the neighbors of each node and incrementing their indegree.
DESCRIPTION
You are given a graph with n nodes, where each node has an integer value from 0 to n - 1.
The graph is represent by an adjacency list, where each node i is mapped to a list of nodes that have a directed edge from node i to them. Write a function to calculate the indegree of each node in the graph.
Example
Input:
edges = {0: [1], 1: [2, 3], 2: [], 3: [2, 4], 4: []}
n = 5Output:
[0, 1, 2, 1, 1]
Solution
def indegree(adj_list, n):indegree = [0] * nfor u in adj_list:# increment the indegree of each neighbor of ufor v in adj_list[u]:indegree[v] += 1
Kahn's Algorithm
Kahn's algorithm is a form of Breadth-First Search in which nodes with lower indegrees are placed on the queue before nodes with higher indegrees.
The algorithm is as follows:
- Calculate the indegree of each node.
- Add all nodes with an indegree of 0 to a queue.
- While the queue is not empty:
- Dequeue the first node from the queue and add it to the topological order.
- For each neighbor of the node, decrement its indegree by 1. If the neighbor's indegree is now 0, add it to the queue.
- Return the topological order.
Walkthrough
We'll walkthrough how the algorithm works for the graph given by the adjacency list below:
adjList = {0: [1, 3],1: [2],2: [],3: [1, 4, 5],4: [5],5: []}
Step 1:
Calculate the indegree of each node.
Step 2:
Add all nodes with an indegree of 0 to the queue.
Step 3:
While the queue is not empty:
- Deque the first node from the queue and add it to the topological sort.
Visualization
enqueue nodes with indegree 0
0 / 1
- Decrement the indegree of each neighbor of the node. If this results in a neighbor having an indegree of 0, add it to the queue.
Visualization
dequeue and add node 0 to topological sort
0 / 1
- We have fully processed node 1, so now repeat the process of dequeuing and decrementing indegrees for the next node in the queue until the queue is empty.
Visualization
decrement indegree of neighbors
0 / 8
Step 4:
Return the topological order.
Visualization
dequeue and add node 5 to topological sort
0 / 1
Solution
Solution
from collections import dequedef topological_sort(adj_list, n):# calculate indegree of each nodeindegree = [0] * nfor u in adj_list:for v in adj_list[u]:indegree[v] += 1# enqueue nodes with indegree 0queue = deque([u for u in range(n) if indegree[u] == 0])order = []while queue:u = queue.popleft()order.append(u)for v in adj_list.get(u, []):indegree[v] -= 1if indegree[v] == 0:queue.append(v)return order if len(order) == n else []
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges in the graph. We visit each vertex once and each edge twice (once when calculating indegrees, and once when processing vertices in the BFS). This gives us O(V + 2E), which simplifies to O(V + E).
Space Complexity: O(V) where V is the number of vertices in the graph. This is due to the data structure we use to store the indegrees of each vertex, and the queue we use to store vertices with an indegree of 0, both of which store up to V elements.
Mark as read
Your account is free and you can post anonymously if you choose.