Скачать или смотреть Python – Course Schedule II via DFS Topological Sort (Reverse Postorder) 🚀

Determine a valid course order by performing a DFS on the directed graph of prerequisites and recording nodes in reverse postorder. If a cycle is detected, return an empty list.

Graph Construction:

Build an adjacency list graph[pre] → list of courses that depend on pre.

Visitation States:

Use visited[u] = 0 (unvisited), 1 (visiting), 2 (visited).

Entering a node sets it to visiting; encountering a visiting node signals a cycle.

DFS Routine:

For each unvisited course u, recursively visit all neighbors v.

After exploring u’s dependencies, mark it visited and append to order.

Result Assembly:

Reverse the order list (reverse postorder) to get a valid topological sort.

If any DFS call finds a cycle, return [].

When to Use:

Ideal when you need a simple recursive implementation and can afford O(V+E) stack space for large graphs.

#TopologicalSort #GraphDFS #CycleDetection #CodingInterview

Codes:

🔄 Approach 1: DFS Topological Sort (O(V+E) time, O(V+E) space)
def findOrder_dfs(numCourses, prerequisites):
from collections import defaultdict
graph = defaultdict(list)
for course, pre in prerequisites:
graph[pre].append(course)

visited = [0] * numCourses # 0=unvisited, 1=visiting, 2=visited
order = []
def dfs(u):
if visited[u] == 1:
return False # cycle
if visited[u] == 2:
return True
visited[u] = 1
for v in graph[u]:
if not dfs(v):
return False
visited[u] = 2
order.append(u)
return True

for i in range(numCourses):
if visited[i] == 0 and not dfs(i):
return []
return order[::-1] # reverse postorder


⚡ Approach 2: BFS Kahn’s Algorithm (O(V+E) time, O(V+E) space)
def findOrder_bfs(numCourses, prerequisites):
from collections import defaultdict, deque
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, pre in prerequisites:
graph[pre].append(course)
in_degree[course] += 1

queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)

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