再帰を使わないオイラーツアーをスタックで実装する思考過程

AtCoderをしていた時、解法でオイラーツアーという単語が出てきた。

初めて聞いた単語だったため、以下のサイトを参考に実装して思考過程を整理してみた。

Euler Tour のお勉強
個人的に勉強したことを整理します。新規性とか強い主張とかは、特にありません。Euler Tour(1) DFS 順に探索して、通った頂点の列を記録する(,2,3,4,3,2,5,2,1,6,1$)。(2) 各頂点 $i$ について、最初
非再帰 Euler Tour を Python でやる - Qiita
非再帰 Euler Tour を書くEuler Tour に限らなくてもいいんですが、 DFS を非再帰で書くと若干大変ですよね。それの私なりの書き方です。先に方針を書くとこんな感じです。Pyt…

深さ優先探索(DFS)を行い、訪れた頂点の順番と時刻を記録するアルゴリズム。

オイラーツアーを使うことで、グラフの問題を配列の問題へと置き換えられるようになる。

Pythonは再帰を使うと遅いため、AtCoderでTLEにならないよう今回はスタックを使って実装してみた。

完成したコード


def EulerTour(n, graph, root):
    """
    (n: int, graph: List[List[int]], root: int) -> Tuple[List[int], List[int], List[int]]:

    :param n: the number of vertex points
    :param graph: 2D matrix of N vertices given by the edges
    :param root: start node index

    :return tour: order of visited vertex
    :return in_time: first visiting time of each vertex
    :return out_time: last visiting time of each vertex

    example:
    graph = [[] for _ in range(n)]
    for _ in range(n):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    tour, in_time, out_time = EulerTour(n, graph, 0)
    """

    parent = [-1] * n
    stack = [~root, root]  # postorder, preorder
    curr_time = -1
    tour = []
    in_time = [-1] * n
    out_time = [-1] * n
    while stack:
        curr_node = stack.pop()
        curr_time += 1
        if curr_node >= 0:  # preorder
            tour.append(curr_node)
            if in_time[curr_node] == -1:
                in_time[curr_node] = curr_time

            for next_node in graph[curr_node]:
                if next_node != parent[curr_node]:
                    parent[next_node] = curr_node
                    stack.append(~next_node)
                    stack.append(next_node)
        elif curr_node < 0:  # postorder
            out_time[~curr_node] = curr_time
            if parent[~curr_node] != -1:
                tour.append(parent[~curr_node])

    return tour, in_time, out_time

実装までの思考

グラフはどの頂点とどの頂点が繋がっているのかという辺の情報で与えられることとする。例えば、

input
0 3
1 0
1 4
2 1

graph = [[3, 1], 
         [0, 4, 2], 
         [1], 
         [0], 
         [1]]

まずは普通のDFSを理解し、スタックに置き換えることを考える。

行きがけ(preorder)、帰りがけ(postorder)、通りがけ(inorder)の練習には、LeetCodeの以下の問題がそのまんまで練習しやすかった。

Just a moment...
Just a moment...
- LeetCode
Can you solve this real interview question? - Level up your coding skills and quickly land a job. This is the best place...

オイラーツアーでは行けるところまで探索し(行きがけ)、最後のノードに着いたら元に戻る(帰りがけ)という処置を行う。

これを先入れ後出しのスタックで実現しようとすると、帰りがけ→行きがけの順で頂点スタックに入れればいい。

stack = [postorder, preorder]

ここで、行きがけなのか帰りがけなのかを識別するフラグも一緒に入れたくなる。

しかし、フラグを設定すると実装がタプルになって面倒になり、フラグの分のメモリ使用量が増えてしまう。

そこで、正負によって行きがけなのか帰りがけなのかを判定するようにした。

スタートする頂点をrootとすると、以下のようなスタックから開始出来る。

開始地点の帰りがけは必要ないように見えるが、時刻を記録するために必要となる。

stack = [-root, root]  # postorder, preorder

しかし、頂点0から開始する場合、0も-0も同じ値のため、正しくifで分岐されない。

そのため、notを使った符号の反転を考える。

https://megatenpa.com/python/base/bit-tilde/

これにより not 0 = -1 となり、ifで分岐されるようになる。

notはチルダ(~)で表現できるため、スタックは以下のように開始するよう変更する。

stack = [~root, root]  # postorder, preorder

スタックが空になるまで処理を繰り返すので、処理の骨子は以下のようになる。

グラフの頂点の数をnとして、オイラーツアーの結果を保存する配列と変数も設定する。

最初の頂点を時刻0としたいので、現在時刻current timeは-1で初期化する。

elifのところはelseでも良いのだが、理解しやすいよう条件を明示している。

stack = [~root, root]  # postorder, preorder
curr_time = -1
tour = []
in_time = [-1] * n
out_time = [-1] * n
while stack:
    curr_node = stack.pop()
    curr_time += 1
    if curr_node >= 0:  # preorder
        ...
    elif curr_node < 0:  # postorder
        ...

行きがけ

訪れた頂点を保存する。

オイラーツアーでは「初めてその頂点を訪れた時刻」を保存するため、初めて訪れたかどうか判定してから時刻を更新する。

if curr_node >= 0:  # preorder
    tour.append(curr_node)
    if in_time[curr_node] == -1:
        in_time[curr_node] = curr_time

その後、次の頂点に潜っていく。

スタックは先入れ後出しなので、帰りがけ→行きがけで積み込んでいく。

for next_node in graph[curr_node]:
    stack.append(~next_node)
    stack.append(next_node)

しかし、このままではcurr_nodeとnext_nodeで無限ループが起きてしまう。

同じ頂点を行き来しないようにifが必要となるが、どこから来たのかという「親の頂点」の情報が欲しくなる。

親の頂点を保存するための配列を新たに用意し、次のノードが自分の親じゃないなら探索を続けていく。

合わせて親の情報も更新する。

これで行きがけの完成。

parent = [-1] * n
stack = [~root, root]  # postorder, preorder
curr_time = -1
tour = []
in_time = [-1] * n
out_time = [-1] * n
while stack:
    curr_node = stack.pop()
    curr_time += 1
    if curr_node >= 0:  # preorder
        tour.append(curr_node)
        if in_time[curr_node] == -1:
            in_time[curr_node] = curr_time

        for next_node in graph[curr_node]:
            if next_node != parent[curr_node]:
                parent[next_node] = curr_node
                stack.append(~next_node)
                stack.append(next_node)

帰りがけ

帰りがけでは親頂点に戻るだけなので、行きがけで保存した親情報を参照する。

行きがけで現在の頂点を保存しているため、重複しないよう帰りがけでは頂点を保存しないようにする。

また、オイラーツアーでは「最後に頂点を出た時刻」を保存するため、行きがけと違って時刻の更新に条件判定は必要なく、常に最新の一番遅い時刻を記録し続ければ良い。

elif curr_node < 0:  # postorder
    # tour.append(curr_node) は不要
    out_time[~curr_node] = curr_time
    tour.append(parent[~curr_node])

最後に、オイラーツアーが終わってスタート地点に帰ってきた時の帰りがけを考える。

最後に訪れた時刻を更新するためにスタックを[~root, root]で初期化したが、この時にtour.append(parent[~curr_node])によりダミーの親 -1 が保存されてしまう。

スタート地点の親は当然存在しないため、ifを追加する。

elif curr_node < 0:  # postorder
    out_time[~curr_node] = curr_time
    if parent[~curr_node] != -1:
        tour.append(parent[~curr_node])

ifを追加せず、whileを抜けた後に -1 を除去しても良い。

この時、スライスを使うと遅いので注意する。

tour.pop() # 0(1)
tour = tour[:-1] # O(N)

whileの度にifするよりも、最後に一度だけpopする方が直感的に早そうだが、後で自分で見返した時に混乱しそうなので分かりやすいifを採用した。

以上で完成。AtCoderで使い回せるよう関数にしておく。

型ヒントをコメント内に書いたのは、コピペした時にAtCoderで import typing する手間を減らすため。

重み付きグラフなどが与えられた場合でも、重み用の配列を用意すれば別途対応可能。


def EulerTour(n, graph, root):
    """
    (n: int, graph: List[List[int]], root: int) -> Tuple[List[int], List[int], List[int]]:

    :param n: the number of vertex points
    :param graph: 2D matrix of N vertices given by the edges
    :param root: start node index

    :return tour: order of visited vertex
    :return in_time: first visiting time of each vertex
    :return out_time: last visiting time of each vertex

    example:
    graph = [[] for _ in range(n)]
    for _ in range(n):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    tour, in_time, out_time = EulerTour(n, graph, 0)
    """

    parent = [-1] * n
    stack = [~root, root]  # postorder, preorder
    curr_time = -1
    tour = []
    in_time = [-1] * n
    out_time = [-1] * n
    while stack:
        curr_node = stack.pop()
        curr_time += 1
        if curr_node >= 0:  # preorder
            tour.append(curr_node)
            if in_time[curr_node] == -1:
                in_time[curr_node] = curr_time

            for next_node in graph[curr_node]:
                if next_node != parent[curr_node]:
                    parent[next_node] = curr_node
                    stack.append(~next_node)
                    stack.append(next_node)
        elif curr_node < 0:  # postorder
            out_time[~curr_node] = curr_time
            if parent[~curr_node] != -1:
                tour.append(parent[~curr_node])

    return tour, in_time, out_time

試しに以下の問題を解いてみる。

D - Takahashi Tour
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

この問題では頂点が小さい順に訪れるという制約があるため、入力するグラフはソートしておく。

スタックは先入れ後出しのため、頂点の番号が小さい順に訪れるために、頂点の大きい番号からスタックに積み込めるようfor next_node in graph[curr_node][::-1]と反転させておく。

def EulerTour(n, graph, root):
    """
    (n: int, graph: List[List[int]], root: int) -> Tuple[List[int], List[int], List[int]]:

    :param n: the number of vertex points
    :param graph: 2D matrix of N vertices given by the edges
    :param root: start node index

    :return tour: order of visited vertex
    :return in_time: first visiting time of each vertex
    :return out_time: last visiting time of each vertex

    example:
    graph = [[] for _ in range(n)]
    for _ in range(n):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    tour, in_time, out_time = EulerTour(n, graph, 0)
    """

    parent = [-1] * n
    stack = [~root, root]  # postorder, preorder
    curr_time = -1
    tour = []
    in_time = [-1] * n
    out_time = [-1] * n
    while stack:
        curr_node = stack.pop()
        curr_time += 1
        if curr_node >= 0:  # preorder
            tour.append(curr_node)
            if in_time[curr_node] == -1:
                in_time[curr_node] = curr_time

            for next_node in graph[curr_node][::-1]:
                if next_node != parent[curr_node]:
                    parent[next_node] = curr_node
                    stack.append(~next_node)
                    stack.append(next_node)
        elif curr_node < 0:  # postorder
            out_time[~curr_node] = curr_time
            if parent[~curr_node] != -1:
                tour.append(parent[~curr_node])

    return tour, in_time, out_time


n = int(input())

graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

for i in range(n):
    graph[i] = sorted(graph[i])

tour, in_time, out_time = EulerTour(n, graph, 0)

tour = [i + 1 for i in tour]
print(*tour)

ほとんどコピペでAC。

Submission #29616126 - AtCoder Beginner Contest 213
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

whileのスタックを使ったことでpypyで高速化され、実行時間は0.6秒だった。

以下の再帰を使った例では1.5秒かかったため、約2倍早くなったことになる。

実務ではどうなのか分からないが、AtCoder的には有利。

Submission #24888537 - AtCoder Beginner Contest 213
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

ABC239のE – Subtree K-th Maxでは、オイラーツアーでグラフを配列の問題に落とし込み、セグメントツリーを使うことで解けた。

E - Subtree K-th Max
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

以下はAC例。

Submission #29616150 - Denso Create Programming Contest 2022(AtCoder Beginner Contest 239)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

この時のセグメントツリーは以下から拝借させて頂いた。

Pythonでアルゴリズム(セグメント木)(実践) - Qiita
#はじめに 普段はググってセグ木を貼るだけでしたが、コロナウイルスの影響で時間が出来たので原理を理解しながら実装してみました。 ネットを中心に様々な方の記事を参考にしながら構築していきました。最…

コメント

タイトルとURLをコピーしました