0Pricing
Coding Interview Prep · レッスン

DFS、再帰、反復スタック

深く探索し、再帰制限を回避します

「DFS、再帰、反復スタック」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

DFSの動作

DFSは1つの経路を進めるだけ深く進み、その後戻って次の経路を試します。迷路を通路ごとに探索するイメージです。🧭

DFSとBFSの違い

BFSが同心円状に広がるのに対し、DFSはまず深く進みます。どちらも到達可能なすべてのノードを訪れますが、順序が大きく異なります。

再帰の形

再帰的なDFSでは、ノードをvisitedにしてから、未訪問の各隣接ノードに対して自分自身を呼び出します。コールスタックが戻る場所を記憶します。

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

再帰する前にマークする

隣接ノードを探索する前、ノードに入った時点でvisitedを設定します。そうしないと、サイクルによってDFSが無限再帰に陥ります。

再帰制限の罠

Pythonの再帰呼び出しは約1000回に制限されています。深いグラフではRecursionErrorが発生し、実行時エラーと判定されます。

制限を引き上げる

手早い対処法の1つは、setrecursionlimitで上限を引き上げることです。DFSを実行する前に、最悪の場合の深さより大きな値を設定してください。

import sys
sys.setrecursionlimit(300000)

代わりに反復処理を使う

最も安全な対処法は、自分で用意したスタックを使う反復的なDFSです。呼び出しの深さがなくなるため、再帰によるクラッシュも起きません。

stack = [start]

スタックから取り出す

各ステップでスタックの一番上から取り出します。後入れ先出しによって、直近の経路を優先して深く進めます。

u = stack.pop()

隣接ノードを追加する

uを取り出した後、未訪問の各隣接ノードをスタックに追加します。再び追加しないよう、追加時にマークします。

for v in adj[u]:
    if not visited[v]:
        visited[v] = True
        stack.append(v)

反復処理の完全なループ

スタックにノードがある間、取り出しと追加を繰り返します。空になったとき、到達可能なすべてのノードを訪問したことになります。

while stack:
    u = stack.pop()
    for v in adj[u]:
        if not visited[v]:
            visited[v] = True
            stack.append(v)

BFSと同じ計算量

BFSと同様に、DFSも各ノードと各エッジを1回ずつ訪れるため、計算量はO(n + m)です。問題に適した探索順序で選んでください。

確認問題

深いグラフで再帰的なDFSがクラッシュしました。なぜでしょうか。

復習

DFSは再帰または自分で用意したスタックを使って実行できます。入った時点で訪問済みにし、グラフが深い場合は反復処理に切り替えます。🎉

よくある質問

「DFS、再帰、反復スタック」レッスンは無料ですか？

はい。「DFS、再帰、反復スタック」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「DFS、再帰、反復スタック」で何を学びますか？

深く探索し、再帰制限を回避します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「DFS、再帰、反復スタック」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 入力から隣接リストを作る
  2. 重みなし最短経路のための BFS
  3. DFS、再帰、反復スタック
  4. 連結成分と Flood Fill
← Coding Interview Prepに戻る