深さ優先探索を再帰関数を使わずにスタックを使って実装したい

Question

以下の問題において、深さ優先探索を再帰関数を使わずに実装する方法を教えてください。
再帰関数を使った実装で正解はできるのですが、再帰関数を使わない実装がうまくいきません。具体的には探索の順番が深さ優先探索ではないのです。

問題

多重辺・自己ループのない無向グラフを構成する 1 〜 N の番号がつけられた頂点とそれらを結ぶ M 本の辺の情報と、頂点番号 X が与えられます。
頂点 X から次のルールにしたがって深さ優先探索を行った時に訪れる頂点番号を順に出力してください。

• 現在の頂点に隣接する頂点のうち、未訪問かつ頂点番号が一番小さい頂点を探索する。

入力

N M X
a_1 b_1
...
a_M b_M

• 1 行目では、頂点の数 N と辺の本数 M, 頂点番号 X が半角スペース区切りで与えられます。
• 続く M 行では、M 個の辺の両端の頂点の番号 a_i, b_i (1 ≦ i ≦ M) が与えられます。

出力

頂点 X から深さ優先探索を行った時に訪れる頂点の番号を順に改行区切りで出力してください。

制限

• 1 ≦ N ≦ 5,000
• 1 ≦ M ≦ min(N*(N-1)/2, 100,000)
• 1 ≦ X ≦ N
• 1 ≦ a_i, b_i ≦ N (1 ≦ i ≦ M)
• a_i ≠ b_i (1 ≦ i ≦ M)

入力例1

5 6 1
1 2
2 3
2 4
3 5
4 5
1 5

出力例1

1
2
3
5
4

自分の解答

from collections import deque
n, m, x = map(int, input().split())
graph = [[] for _ in range(n)]

# 隣接リストの作成
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
# グラフの各ノードを昇順にする
graph = [sorted(g) for g in graph]

# 訪問済み確認リスト
x -= 1
visited = [False] * n
visited[x] = True

# スタックを使う
Q = deque([x])
while Q:
    now_node = Q.pop()
    print(now_node + 1)
    for next_node in graph[now_node]:
        if visited[next_node] is False:
            visited[next_node] = True
            Q.append(next_node)

自分の解答を使った入力と出力

入力

5 6 1
1 2
2 3
2 4
3 5
4 5
1 5

出力 (誤り)

1
5
4
3
2

Answer 1

深さ有線探索になっていないからです。
この処理では注目ノードの先のノードをスタックに積んでから、それを1つずつ取りだしてチェックしていきますので、全部積んでしまえば幅有線になってしまいます。

修正してみました。 後半部分です。

# グラフの各ノードを昇順にする
graph = [sorted(g) for g in graph]

# 訪問済み確認リスト
x -= 1

visited = [False] * n

# スタックを使う
Q = deque([x])

while Q:
    now_node = Q[0]
    if not visited[now_node]:
        print(now_node + 1)
        visited[now_node] = True
    for next_node in graph[now_node]:
        if visited[next_node] is False:
            Q.appendleft(next_node)
            break
    else:
        Q.popleft()

あれこれやっているうちにだいぶ変ってしまいました。
また、他の回答もついていますね。

こちらの考えかたではpopの場所が変っていますが、これはキューの中身が「訪問済みだが枝の残っているノードの管理」になているところがポイントです。
キューの中身をループ全般で表示してみるとどうなっているかわかると思います。

Comments

[k6happy]

ありがとうございます。スタックの中身を確認しながらループの処理を追うことで、内容をよく理解することができました。
`Q[0]`と`appendleft()`、`popleft()`での実装のほかに、`Q[-1]`と`append()`、`pop()`でもいけることも確認できました。
また、forループのelseの使用例も同時に知ることができて大変勉強になりました。
ありがとうございます。

Answer 2

# スタックを使う
Q = deque([x])
stack = []
while True:
    if len(graph[x]) > 0:
        next_node = graph[x].pop(0)
        if visited[next_node] is False:
            visited[next_node] = True
            Q.append(next_node)
            stack.append(x)
            x = next_node
            continue
    else:
        if len(stack) > 0:
            x = stack.pop()
        else:
            break

Comments

[k6happy]

ありがとうございます。いろいろな実装方法を試してみて、理解を深めようと思います！