Python实现拓扑排序：原理、算法与代码详解

拓扑排序

在各类项目及日常生活中，不同任务间往往存在依赖关系，这些依赖构成了执行顺序的部分约束。针对此类依赖，可将其建模为有向无环图（Directed Acyclic Graph，简称DAG），其中“无环”是核心前提。寻找满足依赖关系的执行顺序的过程，即为拓扑排序（topological sorting）。

拓扑排序需满足以下两个核心条件：

• 图中每个顶点在排序结果中仅出现一次。
• 若顶点A在序列中位于顶点B之前，则图中不能存在从B指向A的路径。

拓扑排序算法逻辑

对于任意不含回路的顶点活动网（AOV网）N，均可构造出对应的拓扑序列。具体步骤如下：

• 从当前网络N中选取一个入度为0的顶点，将其加入序列作为下一个元素。
• 将该顶点从网络N中移除，并删除其所有出边（即指向的其他顶点）。
• 重复执行上述两步，直至选出图中所有顶点，或无法再找到入度为0的顶点时算法终止。

若算法结束时仍有顶点入度非0，表明网络N中存在回路，此时无法进行拓扑排序。

回路的存在意味着某些活动的开始依赖于自身完成的先决条件，这种现象称为活动间的死锁。典型的AOV网实例是大学课程的先修关系：课程知识具有前后衔接性，选修某门课需已修完所有先修课。若课程依赖中存在回路，将导致循环依赖，学生无法完成学业。

因此，拓扑排序算法旨在生成满足特定制约关系的工作安排序列。

以下通过一个具体实例进行操作演示，该实例为一个有向无环图：

使用字典结构表示该图：G = { 'a':'bce', 'b':'d','c':'d','d':'','e':'cd'}

Python代码实现如下：

def toposort(graph):
 in_degrees = dict((u,0) for u in graph) #初始化所有顶点入度为0
 vertex_num = len(in_degrees)
 for u in graph:
  for v in graph[u]:
   in_degrees[v] += 1  #计算每个顶点的入度
 Q = [u for u in in_degrees if in_degrees[u] == 0] # 筛选入度为0的顶点
 Seq = []
 while Q:
  u = Q.pop()  #默认从最后一个删除
  Seq.append(u)
  for v in graph[u]:
   in_degrees[v] -= 1  #移除其所有指向
   if in_degrees[v] == 0:
    Q.append(v)   #再次筛选入度为0的顶点
 if len(Seq) == vertex_num:  #如果循环结束后存在非0入度的顶点说明图中有环，不存在拓扑排序
  return Seq
 else:
  print("there's a circle.")
G = {
 'a':'bce',
 'b':'d',
 'c':'d',
 'd':'',
 'e':'cd'
}
print(toposort(G))

程序输出结果：

['a', 'e', 'c', 'b', 'd']

当图中存在回路的情况：

G = { 'a':'bce', 'b':'d','c':'d','d':'e','e':'cd'}

程序输出结果：

there's a circle.
None

总结

以上内容涵盖了拓扑排序的核心概念与Python实现。希望本文对读者的学习或工作有所帮助，如有疑问欢迎留言交流，感谢支持。