python 拓扑排序
对一个有向无环图(directed acyclic graph简称dag)g进行拓扑排序，是将g中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈e(g)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(topological order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：topological sorting）：
- 每个顶点出现且只出现一次；
- 若a在序列中排在b的前面，则在图中不存在从b到a的路径。
实例
from collections import defaultdict
class graph:
def __init__(self,vertices):
self.graph = defaultdict(list)
self.v = vertices
def addedge(self,u,v):
self.graph[u].append(v)
def topologicalsortutil(self,v,visited,stack):
visited[v] = true
for i in self.graph[v]:
if visited[i] == false:
self.topologicalsortutil(i,visited,stack)
stack.insert(0,v)
def topologicalsort(self):
visited = [false]*self.v
stack =[]
for i in range(self.v):
if visited[i] == false:
self.topologicalsortutil(i,visited,stack)
print (stack)
g= graph(6) g.addedge(5, 2); g.addedge(5, 0); g.addedge(4, 0); g.addedge(4, 1); g.addedge(2, 3); g.addedge(3, 1);
print ("拓扑排序结果：") g.topologicalsort()
执行以上代码输出结果为：
拓扑排序结果： [5, 4, 2, 3, 1, 0]
【说明】：本文章由站长整理发布，文章内容不代表本站观点，如文中有侵权行为，请与本站客服联系(QQ:254677821)！