拓扑排序是对有向无环图的一种排序，满足如下两个条件：
1.每个顶点出现且只出现一次；
2.若A在序列中排在B的前面，则在图中不存在从B到A的路径。
如上的无环有向图，v表示顶点：v=[‘a‘,‘b‘,‘c‘,‘d‘,‘e‘]，e表示有向边：e=[(‘a‘,‘b‘),(‘a‘,‘d‘),(‘b‘,‘c‘),(‘d‘,‘c‘),(‘d‘,‘e‘),(‘e‘,‘c‘)]，代码如下：
def indegree0(v,e): if v==[]: return None tmp=v[:] for i in e: if i[1] in tmp: tmp.remove(i[1]) if tmp==[]: return -1 for t in tmp: for i in range(len(e)): if t in e[i]: e[i]=‘toDel‘ #占位，之后删掉 if e: eset=set(e) eset.remove(‘toDel‘) e[:]=list(eset) if v: for t in tmp: v.remove(t) return tmp def topoSort(v,e): result=[] while True: nodes=indegree0(v,e) if nodes==None: break if nodes==-1: print(‘there\‘s a circle.‘) return None result.extend(nodes) return result v=[‘a‘,‘b‘,‘c‘,‘d‘,‘e‘] e=[(‘a‘,‘b‘),(‘a‘,‘d‘),(‘b‘,‘c‘),(‘d‘,‘c‘),(‘d‘,‘e‘),(‘e‘,‘c‘)] res=topoSort(v,e) print(res)
indegree0函数返回入度为0的顶点，并在v和e中删除它和它相邻的边，如果v列表中没有顶点了，就返回None，如果v列表中还有顶点但是找不到入度为0的顶点，说明有向图中有环，返回-1。topoSort函数不断取出有向图中入度为0的顶点，最后就是拓扑排序序列。输出如下：
[‘a‘, ‘b‘, ‘d‘, ‘e‘, ‘c‘]
考虑一种有环的情况，加上一条c->d的边，如下图所示：
输出如下：
there‘s a circle. None
转载请注明：转自http://blog.csdn.net/littlethunder/article/details/24113193