トポロジカルソート(Kahnのアルゴリズム)

2022年11月6日

説明

Kahnのアルゴリズムでトポロジカルソートする
参考

def solve(n,m,graph):
    '''
    ABC223-Dでの使用例
    n: 頂点数
    graph: 普通の隣接リスト
    '''
    in_deg = [0 for _ in range(n)]  # 各頂点の入次数を格納するリスト
    for i in range(n):
        for j in graph[i]:
            in_deg[j] += 1

    heap = [] # 辞書順で最も小さいトポロジカルソートにするため heapq を使っている。
              # そのような条件がなければ通常のキューでよい。
    order = [] # トポロジカルソートの結果を格納するリスト

    # 入次数が 0 の頂点をキューに入れる
    for i in range(n):
        if in_deg[i] == 0:
            heappush(heap, i)

    while len(heap) > 0:
        # 入次数 0 の頂点がキューに入っている。それらの頂点は現時点の order の後ろに任意の順序で並べることができる
        # ここでは最終結果が辞書順で最小となるために heapq で最小の頂点番号を選んでいる
        u = heappop(heap)
        order.append(u)
        # キューから取り除いた頂点 u から出ている各辺の端点 v の入次数を減らす
        for v in graph[u]:
            in_deg[v] -= 1
            # もし頂点 v の入次数が 0 になったら v をキューへ入れる
            if in_deg[v] == 0:
                heappush(heap, v)
    # この時点で入次数 > 0 の頂点が残っていたらグラフにサイクルがあったことを意味する
    if sum(in_deg) > 0:
        return [-1]
    else:
        return [x + 1 for x in order]