オイラー路(Hierholzer’s Algorithm)

オイラー路(Hierholzer’s Algorithm)について

タグ オイラー路 一筆書き

概要

  • 有方向グラフが前提
  • 一筆書きの経路を求めたいとき
    • dfsでpostorderを記録する
  • /lca/を求めるとき
    • preorder, inorder, postorderすべてを参照する

具体例; 一筆書きの経路を求めたいとき

  • 概要
    • ノード同士のチケットのペアが与えられ、全てを巡回する経路を求めたいとき
      • 制約がいくつかあり、文字的に昇順のチケットを使用したい
  • 参考 
def solve(tickets):
    G = collections.defaultdict(lambda :[])
    for sn, en in tickets:
        G[sn].append(en)
    for key in G.keys():
        G[key].sort()
    r = []
    def dfs(edge):
        while nexts := G[edge]:
            next_edge = nexts.pop(0)
            dfs(next_edge)
        r.append(edge)
    dfs('JFK')
    return r[::-1]

参考