拓扑排序是一种用于有向无环图(DAG, Directed Acyclic Graph)的线性排序,其中对于图中的每一条有向边 uvuvuv(从顶点 uuu 到顶点 vvv ),顶点 uuu 在排序中出现在 vvv 之前。
下面是使用Python实现拓扑排序的一种方法,使用Kahn's算法:
from collections import deque, defaultdict
def topological_sort(num_courses, prerequisites):
# Create an adjacency list
adj_list = defaultdict(list)
in_degree = {i: 0 for i in range(num_courses)}
# Populate the adjacency list and in-degree of each node
for dest, src in prerequisites:
adj_list[src].append(dest)
in_degree[dest] += 1
# Initialize a queue with all nodes having in-degree of 0
zero_in_degree_queue = deque([k for k in in_degree if in_degree[k] == 0])
topological_order = []
# Process until the queue becomes empty
while zero_in_degree_queue:
vertex = zero_in_degree_queue.popleft()
topological_order.append(vertex)
# For each neighbor, reduce its in-degree by 1
if vertex in adj_list:
for neighbor in adj_list[vertex]:
in_degree[neighbor] -= 1
# If in-degree becomes 0, add it to the queue
if in_degree[neighbor] == 0:
zero_in_degree_queue.append(neighbor)
# Check if topological sort is possible or not
if len(topological_order) == num_courses:
return topological_order
else:
return [] # Return an empty list if there is a cycle in the graph
# Example usage:
num_courses = 6
prerequisites = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
print(topological_sort(num_courses, prerequisites))
这个算法的步骤如下:
- 创建邻接表(
adj_list
)和入度表(in_degree
)。 - 遍历所有边,填充邻接表和入度表。
- 将所有入度为0的节点加入队列。
- 依次处理队列中的节点,更新其邻接节点的入度,并将新的入度为0的节点加入队列。
- 最终,如果排序结果中的节点数量等于图中的节点数,则返回拓扑排序结果;否则,说明图中有环,返回空列表。
这个实现假设输入是一个表示课程和先修课程的有向无环图(DAG),并返回一个可能的课程安排顺序。如果图中存在环,则返回空列表。
4o