【GD】拓扑排序 python实现
拓扑排序是指在有向无环图中，把所有结点按照一定的排序排成一列，使得左边的点都指向右边的点。
一般有两种方法做拓扑排序http://cdn.u1.huluxia.com/g4/M01/23/25/rBAAdl66dbeAHqMsAAKiGusY31I501.jpg
Kahn算法
用一个一维数组存每个结点的入度。用一个数据结构（随意都可以，数组，栈，列表等等）存储所有入度为0的结点。每次从入度为0的结点出发，记录路径，删除该结点，把该结点指向的点的入度减1，再找入度为0的结点，存进数据结构。再循环操作，直到找不到入度为0的结点就停止，如果还剩结点或者路径长度不够，说明该图不是有向无环图。
注意：如果是要打印字典序排序，就用优先列表存入度为0的结点
DFS深搜
从任意未被访问的结点出发做深搜。回溯的时候记录记录路径，得到的路径再倒序一下就是正确的拓扑排序。直到所有结点都被访问完，每次深搜的倒序路径拼接在一起就是答案。
样例图片http://cdn.u1.huluxia.com/g4/M01/23/25/rBAAdl66dbeABd-xAAA-rDvulzw768.jpg
python代码：
from queue import PriorityQueue as pQueue
import sys
sys.setrecursionlimit(100000)
# 这是最常见的拓扑排序，0入度集合可以用队列，栈等等，只要能存储0入度的点就行
# 这里用了队列，其实就是跟广搜bfs差不多，入度为0的才入队
def ts_bfs(inDegrees, graph):
n = len(graph)
result = ''
q = []
vis = * n
for i, inDegree in enumerate(inDegrees):
if inDegree == 0:
q.append(i)
vis = True
while q:
s = q.pop(0)
result += str(s)
for sub in graph:
if not vis:
inDegrees -= 1
if inDegrees == 0:
q.append(sub)
return result if len(result) == n else 'The graph is not DAG'
# 满足拓扑排序下，序号从小到大排序或字典序排序
def ts_bfs_pq(inDegrees, graph):
n = len(graph)
result = ''
q = pQueue()
vis = * n
for i, inDegree in enumerate(inDegrees):
if inDegree == 0:
q.put(i)
vis = True
while not q.empty():
s = q.get()
result += str(s)
http://cdn.u1.huluxia.com/g4/M01/23/25/rBAAdl66dbiAKlQFAAFZwnKzc9Q298.jpg
来自于互联网!http://cdn.u1.huluxia.com/g4/M01/23/25/rBAAdl66dbiACHgHAAEn8pW9Yu8572.jpg
页:
[1]