dfs-トポロジカルソート

date: 2022-07-30 excerpt: dfs-トポロジカルソートについて

tag: algorithm dfs depth-first search トポロジカルソート

dfs-トポロジカルソートについて

概要

グラフの向きを左から右へのDAGを成立させた状態で、左のedgeを取り除いても、グラフとして破綻しないようにしたもの
ユースケース
- タスクのスケジューリング問題
- コンパイル時の依存などのリンク順序の解決
dfsを利用してトポロジカルソートを行うことができ、post-order(帰りがけの順)をノードを記録することでトポロジカルソートの結果を得ることができる

具体例

from typing import List
from collections import defaultdict
from collections import deque
def topological_sort(prerequisites: List[List[int]]):
    G = defaultdict(list)
    for to, frm in prerequisites:
        G[frm].append(to)
    que = deque()
    vis = defaultdict(lambda :0)

    for key_pos in list(G.keys()):
        dfs(G, key_pos, que, vis)
    return list(que)

def dfs(G, pos, que, vis):
    if vis[pos] == 1:
        return
    for npos in G[pos]:
        dfs(G, npos, que, vis)
    que.appendleft(pos)
    vis[pos] = 1

参考