排出来的拓扑序

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

用 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: []})))
提交你的答案
请登录后提交答案。
去登录
代码编辑器
Ctrl + Enter 运行
本次输入:
输出:

                        
👩‍🏫
AI
💬 题目评论

全部评论