[Pattern&Template] Topological Sorting Pattern in Graph Problems

806

1. Basic Idea of Topological Sorting

Definition:

Topological sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u→vu \to v, vertex uu comes before vv in the ordering.

When to Use This Pattern:

Problems involving dependencies (e.g., course prerequisites, task scheduling).
Problems where the input is described as a directed graph, and you need to find:
- The order in which tasks or nodes should be processed.
- If it's possible to complete all tasks (cycle detection in a DAG).

How to Identify:

Look for keywords like:
- "Order of tasks"
- "Dependency resolution"
- "Prerequisites"
The problem typically involves:
- A directed graph with dependencies.
- Ensuring no cyclic dependencies exist.

2. Summary Table of Representative Questions

Question	Problem Description	Key Insight
LeetCode 207: Course Schedule	Determine if all courses can be completed given prerequisites.	Cycle detection in a DAG determines feasibility.
LeetCode 210: Course Schedule II	Return a valid course order if all courses can be completed.	A topological sort of the graph provides the course order.
LeetCode 310: Minimum Height Trees	Find the roots of Minimum Height Trees for an undirected graph.	Use a modified topological sort to iteratively trim the graph until roots are found.

3. Code Templates

Template 1: Topological Sort Using Kahn's Algorithm (BFS)

from collections import defaultdict, deque

def topological_sort_kahn(num_nodes: int, edges: List[List[int]]) -> List[int]:
	graph = defaultdict(list)
	indegree = [0] * num_nodes

	# Build the graph and calculate in-degrees
	for u, v in edges:
		graph[u].append(v)
		indegree[v] += 1

	# Start with nodes that have no incoming edges
	queue = deque([node for node in range(num_nodes) if indegree[node] == 0])
	result = []

	while queue:
		node = queue.popleft()
		result.append(node)

		for neighbor in graph[node]:
			indegree[neighbor] -= 1
			if indegree[neighbor] == 0:
				queue.append(neighbor)

	return result if len(result) == num_nodes else []  # Return empty list if there's a cycle

Template 2: Topological Sort Using DFS

from collections import defaultdict

def topological_sort_dfs(num_nodes: int, edges: List[List[int]]) -> List[int]:
	graph = defaultdict(list)
	for u, v in edges:
		graph[u].append(v)

	visited = [0] * num_nodes  # 0 = not visited, 1 = visiting, 2 = visited
	result = []
	has_cycle = False

	def dfs(node):
		nonlocal has_cycle
		if visited[node] == 1:  # Cycle detected
			has_cycle = True
			return
		if visited[node] == 2:  # Already processed
			return

		visited[node] = 1  # Mark as visiting
		for neighbor in graph[node]:
			dfs(neighbor)
		visited[node] = 2  # Mark as visited
		result.append(node)

	for node in range(num_nodes):
		if visited[node] == 0:
			dfs(node)

	return result[::-1] if not has_cycle else []  # Reverse the result for correct order

4. Detailed Explanation of Representative Questions

1. LeetCode 207: Course Schedule

Problem Description

You are given numCourses and an array prerequisites where prerequisites[i] = [ai, bi] indicates you must take course bi before course ai. Determine if you can complete all courses.

Input:

numCourses = 2
prerequisites = [[1, 0]]

Output:
```
True
```

Solution Using BFS (Kahn's Algorithm)

Build the graph and calculate in-degrees for all nodes.
Add nodes with in-degree 0 to the queue (starting points).
Process the queue:
- Remove a node, reduce the in-degree of its neighbors.
- If a neighbor's in-degree becomes 0, add it to the queue.
If all nodes are processed, return True (no cycle); otherwise, False.

Code

class Solution:
	def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
		graph = defaultdict(list)
		indegree = [0] * numCourses

		for a, b in prerequisites:
			graph[b].append(a)
			indegree[a] += 1

		queue = deque([node for node in range(numCourses) if indegree[node] == 0])
		count = 0

		while queue:
			node = queue.popleft()
			count += 1
			for neighbor in graph[node]:
				indegree[neighbor] -= 1
				if indegree[neighbor] == 0:
					queue.append(neighbor)

		return count == numCourses

2. LeetCode 210: Course Schedule II

Problem Description

Similar to 207, but instead of returning True or False, return a valid order of courses.

Input:

numCourses = 4
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]

Output:
```
[0, 1, 2, 3]
```

Solution Using BFS

This is an extension of 207:

Use the same graph and in-degree computation.
Track the order in which nodes are processed.

Code

class Solution:
	def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
		graph = defaultdict(list)
		indegree = [0] * numCourses

		for a, b in prerequisites:
			graph[b].append(a)
			indegree[a] += 1

		queue = deque([node for node in range(numCourses) if indegree[node] == 0])
		result = []

		while queue:
			node = queue.popleft()
			result.append(node)
			for neighbor in graph[node]:
				indegree[neighbor] -= 1
				if indegree[neighbor] == 0:
					queue.append(neighbor)

		return result if len(result) == numCourses else []

3. LeetCode 310: Minimum Height Trees

Problem Description

Given a tree with n nodes, return all the root nodes that can make the tree's height minimal.

Input:
```
n = 4
edges = [[1, 0], [1, 2], [1, 3]]
```
Output:
```
[1]
```

Solution Using Topological Sort

Treat the tree as an undirected graph.
Start with leaf nodes (nodes with 1 connection).
Iteratively remove leaf nodes and their edges until only 1-2 nodes remain.

Code

class Solution:
	def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
		if n == 1:
			return [0]

		graph = defaultdict(list)
		for u, v in edges:
			graph[u].append(v)
			graph[v].append(u)

		leaves = [node for node in range(n) if len(graph[node]) == 1]

		while n > 2:
			n -= len(leaves)
			new_leaves = []
			for leaf in leaves:
				neighbor = graph[leaf].pop()
				graph[neighbor].remove(leaf)
				if len(graph[neighbor]) == 1:
					new_leaves.append(neighbor)
			leaves = new_leaves

		return leaves

Comparison of Questions

Aspect	207: Course Schedule	210: Course Schedule II	310: Minimum Height Trees
Output	Feasibility (`True/False`).	Valid course order.	Minimal-height tree roots.
Graph Type	Directed Acyclic Graph (DAG).	Directed Acyclic Graph (DAG).	Undirected Tree.
Algorithm	Topological Sort (BFS).	Topological Sort (BFS).	Modified Topological Sort (BFS).

Comments (0)