排出来的拓扑序
用 Kahn 算法,每次从入度为 0 的点里取编号最小的。运行下面这段程序:
from collections import deque
def kahn(g):
d = {u: 0 for u in g}
for u in g:
for v in g[u]:
d[v] += 1
q = deque(sorted(u for u in g if d[u] == 0))
out = []
while q:
u = q.popleft()
out.append(u)
for v in g[u]:
d[v] -= 1
if d[v] == 0:
q.append(v)
return out
print("/".join(str(x) for x in kahn({0: [2], 1: [2], 2: [3, 4], 3: [5], 4: [5], 5: []})))
全部评论