Hello アルゴで学ぶグラフの走査幅優先探索BFSと深さ優先探索DFSの原理・実装・計算量【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo「Hello アルゴ」hello-algoは、アニメーションとコードを併用してデータ構造とアルゴリズムを学べるオープンソースのチュートリアルで、本書の日本語版ドキュメントはja/docs/に配置されています。本記事はその中核トピックのひとつである「グラフの走査graph traversal」に焦点を当て、木の走査を特殊ケースとして内包するグラフの幅優先走査BFSと深さ優先走査DFSを、アルゴリズムの考え方、実装コード、計算量分析の3点から体系的に解説します。読み終えると、Python・C・Cなど多言語で用意されたgraph_bfs/graph_dfsの実装を読み解き、訪問済み頂点の管理や走査順序の非一意性といったポイントを押さえた上で、自分の問題に合わせて走査アルゴリズムを選定・実装できるようになります。グラフの走査とは木の走査の一般化木は「一対多」の関係を表しますが、グラフは任意の「多対多」の関係を表現でき、より高い自由度を持ちます。したがって木はグラフの特殊なケースとみなせ、木の走査操作もグラフの走査操作の特殊なケースです。木の走査が「根から全てのノードを漏れなく訪れる」操作であるように、グラフの走査は「始点となる頂点から全ての頂点を漏れなく訪れる」操作です。グラフと木はいずれも走査を実現するために探索アルゴリズムを用います。グラフの代表的な走査方法は以下の2種類に分けられます対応コードは graph_bfs.c と graph_dfs.c などで確認できます。幅優先走査BFS: Breadth-First Search近い頂点から遠い頂点へ、層ごとに外側へ広がっていく走査。深さ優先走査DFS: Depth-First Search行けるところまで進み、行き止まりになったら戻る走査。本記事で繰り返し登場する前提知識として、グラフの表現方法である隣接リストgraph_adjacency_list.py、graph_adjacency_list.cと、グラフの基本操作頂点・辺の追加削除は graph_operations.md で解説されています。以降の走査コードは「指定した頂点の隣接頂点をすべて取得できる」この隣接リスト表現を前提としています。幅優先走査BFS「近いところから遠いところへ」の走査戦略幅優先走査は、ある頂点から出発し、常に最も近い頂点を優先して訪問し、層ごとに外側へ広がっていく走査方法です。下図のように左上の頂点から出発すると、まずその頂点のすべての隣接頂点第1層を走査し、続いて次の頂点のすべての隣接頂点第2層を走査します。これを繰り返し、すべての頂点を訪問し終えた時点で終了します。アルゴリズムの実装キューと訪問済みハッシュ集合BFS は通常キューを用いて実装します。キューは「先入れ先出しFIFO」の性質を持ち、これは BFS の「近いところから遠いところへ」という考え方と本質的に一致します。基本的な手順は次の3ステップです。走査の開始頂点startVetをキューに追加し、ループを開始します。ループの各反復で、キュー先頭の頂点を取り出してデキュー訪問を記録し、その後その頂点のすべての隣接頂点をキューの末尾に追加します。手順2.を繰り返し、すべての頂点が訪問されると終了します。頂点の重複走査を防ぐため、どの頂点が訪問済みかを記録するハッシュ集合visitedを用います。ヒントハッシュ集合とはハッシュ集合はvalueを持たずkeyだけを格納するハッシュテーブルとみなせます。$O(1)$ の時間計算量でkeyの追加・削除・検索・更新ができ、keyの一意性に基づいてデータの重複排除などの場面で広く使われます。BFS / DFS では「訪問済み頂点の重複排除」に最適なデータ構造です。本リポジトリの日本語版コードから、Python 実装の核心部分を見てみましょう全文は graph_bfs.py。def graph_bfs(graph: GraphAdjList, start_vet: Vertex) - list[Vertex]: 幅優先探索 # 頂点の走査順序 res [] # 訪問済み頂点を記録するためのハッシュ集合 visited setVertex # BFS の実装にキューを用いる que dequeVertex # 頂点 vet を起点に、すべての頂点を訪問し終えるまで繰り返す while len(que) 0: vet que.popleft() # 先頭の頂点をデキュー res.append(vet) # 訪問した頂点を記録 # この頂点のすべての隣接頂点を走査 for adj_vet in graph.adj_list[vet]: if adj_vet in visited: continue # 訪問済みの頂点をスキップ que.append(adj_vet) # 未訪問の頂点のみをキューに追加 visited.add(adj_vet) # この頂点を訪問済みにする # 頂点の走査順を返す return res実装上の重要なポイントは、頂点をキューに追加する時点でvisitedへ登録することです。仮に「デキューした時点」で訪問済みにする実装にすると、同じ頂点が複数回キューに積まれ、重複訪問が発生します。C 版graph_bfs.cppではunordered_setVertex *とqueueVertex *を用いて同じロジックを実現しています。また C 版の graph_bfs.c は、キューと訪問済み配列を自前実装しています。isVisited関数は配列を線形走査するため $O(n)$ となり、Python/C 版のハッシュ集合 $O(1)$ とは実装上の差がありますが、これは「C 言語に標準のハッシュ集合がない」という制約に合わせた教育的な代替実装です。言語機能の違いがアルゴリズムの本質FIFO キュー 訪問済み管理を変えないことを対比して学べる好例といえます。BFS のアルゴリズムの流れを、頂点ごとの状態遷移として下図シリーズで追うことができますgraph_traversal.assets に step1 〜 step11 が格納されています。1〜3始点をキューへ投入し、第1層の隣接頂点を順にキューへ追加。4〜7第2層、第3層へとキューから取り出して訪問を記録。8〜11すべての頂点を訪問し、キューが空になって終了。走査順序列は一意ではない!!! question 幅優先走査の順序列は一意ですか 一意ではありません。幅優先走査は「近いところから遠いところへ」の順で走査することだけを要求し、同じ距離同一層にある複数の頂点の走査順は任意に入れ替えて構いません。上図を例にすると、頂点 $1$ と $3$ の訪問順は交換でき、頂点 $2$、$4$、$6$ の訪問順も任意に入れ替えられます。つまり BFS は「層の順序だけ」を保証し、同一層内の順序はグラフの隣接リスト内の並びや実装に依存します。計算量の分析時間計算量すべての頂点は1回ずつキューに入り、1回ずつキューから出るため $O(|V|)$ です。隣接頂点を走査する過程では、無向グラフの場合すべての辺が2回訪問されるため $O(2|E|)$ となり、全体で$O(|V| |E|)$です。空間計算量結果リストres、ハッシュ集合visited、キューqueに含まれる頂点数はいずれも最大で $|V|$ であるため、$O(|V|)$です。深さ優先走査DFS「行き止まりまで進んで戻る」の走査戦略深さ優先走査は、まず行けるところまで進み、進めなくなったら戻る走査方法です。下図のように、左上の頂点から出発し、現在の頂点の隣接頂点のひとつを訪問して、行き止まりに達するまで進んだら一つ前の頂点へ戻り、再び別の方向へ進んで行き止まりまで進んで戻る、という操作を繰り返し、すべての頂点の走査が完了するまで続けます。アルゴリズムの実装再帰と訪問済みハッシュ集合この「行き止まりまで進んでから戻る」パターンは、通常再帰に基づいて実装されます。BFS と同様に、頂点の重複訪問を避けるために訪問済みハッシュ集合visitedを用います。Python 実装の核心部分は次のとおりです全文は graph_dfs.py。def dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex): 深さ優先走査の補助関数 res.append(vet) # 訪問した頂点を記録 visited.add(vet) # この頂点を訪問済みにする # この頂点のすべての隣接頂点を走査 for adjVet in graph.adj_list[vet]: if adjVet in visited: continue # 訪問済みの頂点をスキップ # 隣接頂点を再帰的に訪問 dfs(graph, visited, res, adjVet) def graph_dfs(graph: GraphAdjList, start_vet: Vertex) - list[Vertex]: 深さ優先探索 # 頂点の走査順序 res [] # 訪問済み頂点を記録するためのハッシュ集合 visited set[Vertex]() dfs(graph, visited, res, start_vet) return res補助関数dfsが「現在の頂点の訪問記録 → 各隣接頂点への再帰」を行い、visitedを引数で受け渡して共有する点がポイントです。再帰呼び出しのスタックがそのまま「探索経路の深さ」を担うため、明示的なスタックを用意する必要がありません。C 版graph_dfs.cppも同一の構造で、unordered_setVertex * visitedを参照渡ししています。C 版graph_dfs.cでは、訪問済み配列resそのものを探索済み判定に使う実装になっています。過程の追跡再帰の「下降」と「バックトラック」深さ優先走査のアルゴリズムの流れは、下図の step1 〜 step11graph_traversal.assetsで確認できます。直線の破線は下向きの再帰呼び出しを表し、新しい頂点を訪問するために新たな再帰メソッドが開始されたことを意味します。曲線の破線は上向きのバックトラックを表し、この再帰メソッドがすでに戻って、呼び出し元の位置までたどり着いたことを意味します。理解を深めるには、図とコードを結びつけて、各再帰メソッドがいつ開始し、いつ戻るかを頭の中であるいは紙に書き出してシミュレーションしてみるのが効果的です。走査順序列は一意ではない!!! question 深さ優先走査の順序列は一意ですか 幅優先走査と同様に、深さ優先走査の順序列も一意ではありません。ある頂点が与えられたとき、どの方向を先に探索してもよく、つまり隣接頂点の順序は任意に入れ替えられ、それでも深さ優先走査になります。この「順序の自由度」は木の走査と対応づけて考えるとわかりやすいです。木の走査を例にすると、「根 → 左 → 右」「左 → 根 → 右」「左 → 右 → 根」はそれぞれ先行順pre-order、中間順in-order、後行順post-order走査に対応します。これらは3種類の異なる走査優先順位を表していますが、いずれも「1本の経路を深く掘り下げてから戻る」という意味では深さ優先走査に属します。すなわち、DFS の順序列は「隣接頂点をどの順で試すか」の選択次第で変わりうるのです。計算量の分析時間計算量すべての頂点は1回ずつ訪問されるため $O(|V|)$、すべての辺は2回ずつ訪問されるため $O(2|E|)$、よって全体で$O(|V| |E|)$です。空間計算量結果リストresとハッシュ集合visitedに含まれる頂点数は最大で $|V|$ であり、再帰の深さも最大で $|V|$グラフが極端な直線状の場合であるため、$O(|V|)$です。なお、再帰実装の空間消費はコールスタック上に積まれるため、頂点数が非常に大きいグラフでは反復 明示的スタックへの置き換えを検討する場合もあります。BFS と DFS の比較と使い分けBFS と DFS はどちらもすべての頂点を $O(|V||E|)$ で走査しますが、訪問順の性質が異なります。観点幅優先走査BFS深さ優先走査DFS基本戦略近い頂点から遠い頂点へ、層ごとに拡張1本の経路を深く掘り下げ、行き止まりで戻る主要データ構造キューFIFO再帰コールスタック訪問順序の性質始点からの「距離層」が単調非減少経路の深さを優先代表的な用途最短経路無重み、層ごとの到達性調査連結成分の検出、トポロジカルソート、迷路探索など空間計算量$O(V)$$O(V)$再帰の深さ分時間計算量$O(VE)$$O(VE)$※ 代表用途はアルゴリズムの一般論としての整理であり、本リポジトリの当該章の範囲を超える内容です。動作確認リポジトリのコードを実行してみる本リポジトリでは各章のコードを言語ごとに実行できます。日本語版のグラフ走査コードは以下にあります。Pythongraph_bfs.py、graph_dfs.pyCgraph_bfs.cpp、graph_dfs.cppCgraph_bfs.c、graph_dfs.c各コード末尾の Driver Code では、次のような無向グラフを構築して走査結果を出力します。BFS 用グラフ頂点 $0$〜$9$頂点数 $|V|10$、辺数 $|E|12$。辺は $0$-$1$, $0$-$3$, $1$-$2$, $1$-$4$, $2$-$5$, $3$-$4$, $3$-$6$, $4$-$5$, $4$-$7$, $5$-$8$, $6$-$7$, $7$-$8$。DFS 用グラフ頂点 $0$〜$6$$|V|7$。辺は $0$-$1$, $0$-$3$, $1$-$2$, $2$-$5$, $4$-$5$, $5$-$6$。たとえば Python の BFS コードは、頂点 $0$ を始点として0 - 1 - 3 - 2 - 4 - 6 - 5 - 7 - 8同一層内の順序は実装依存で変わりうるのような走査列をvets_to_vals(res)で数値に変換して表示します。実行環境の構築方法や Docker による一括実行については installation.md を参照してください。まとめグラフの走査は木の走査の一般化であり、BFSキューによる層次拡張とDFS再帰による深掘りとバックトラックの2系統があります。どちらも訪問済み頂点を記録するハッシュ集合が必須であり、これがないと巡回グラフで無限ループに陥ります。BFS も DFS も時間計算量は $O(|V||E|)$、空間計算量は $O(|V|)$ ですが、訪問順の性質が異なるため用途に応じて使い分けます。両者の走査順序列はどちらも一意ではありません。木の先行順・中間順・後行順は DFS の3つの特殊ケースとみなせます。本記事で扱った走査の理解は、後続の グラフ探索の応用 や、経路探索・最短経路などのより高度なグラフアルゴリズムを学ぶ土台となります。図解ステップgraph_traversal.assetsとコードを突き合わせながら、ぜひ手を動かして確認してみてください。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello アルゴで学ぶグラフの走査：幅優先探索（BFS）と深さ優先探索（DFS）の原理・実装・計算量
Hello アルゴで学ぶグラフの走査幅優先探索BFSと深さ優先探索DFSの原理・実装・計算量【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo「Hello アルゴ」hello-algoは、アニメーションとコードを併用してデータ構造とアルゴリズムを学べるオープンソースのチュートリアルで、本書の日本語版ドキュメントはja/docs/に配置されています。本記事はその中核トピックのひとつである「グラフの走査graph traversal」に焦点を当て、木の走査を特殊ケースとして内包するグラフの幅優先走査BFSと深さ優先走査DFSを、アルゴリズムの考え方、実装コード、計算量分析の3点から体系的に解説します。読み終えると、Python・C・Cなど多言語で用意されたgraph_bfs/graph_dfsの実装を読み解き、訪問済み頂点の管理や走査順序の非一意性といったポイントを押さえた上で、自分の問題に合わせて走査アルゴリズムを選定・実装できるようになります。グラフの走査とは木の走査の一般化木は「一対多」の関係を表しますが、グラフは任意の「多対多」の関係を表現でき、より高い自由度を持ちます。したがって木はグラフの特殊なケースとみなせ、木の走査操作もグラフの走査操作の特殊なケースです。木の走査が「根から全てのノードを漏れなく訪れる」操作であるように、グラフの走査は「始点となる頂点から全ての頂点を漏れなく訪れる」操作です。グラフと木はいずれも走査を実現するために探索アルゴリズムを用います。グラフの代表的な走査方法は以下の2種類に分けられます対応コードは graph_bfs.c と graph_dfs.c などで確認できます。幅優先走査BFS: Breadth-First Search近い頂点から遠い頂点へ、層ごとに外側へ広がっていく走査。深さ優先走査DFS: Depth-First Search行けるところまで進み、行き止まりになったら戻る走査。本記事で繰り返し登場する前提知識として、グラフの表現方法である隣接リストgraph_adjacency_list.py、graph_adjacency_list.cと、グラフの基本操作頂点・辺の追加削除は graph_operations.md で解説されています。以降の走査コードは「指定した頂点の隣接頂点をすべて取得できる」この隣接リスト表現を前提としています。幅優先走査BFS「近いところから遠いところへ」の走査戦略幅優先走査は、ある頂点から出発し、常に最も近い頂点を優先して訪問し、層ごとに外側へ広がっていく走査方法です。下図のように左上の頂点から出発すると、まずその頂点のすべての隣接頂点第1層を走査し、続いて次の頂点のすべての隣接頂点第2層を走査します。これを繰り返し、すべての頂点を訪問し終えた時点で終了します。アルゴリズムの実装キューと訪問済みハッシュ集合BFS は通常キューを用いて実装します。キューは「先入れ先出しFIFO」の性質を持ち、これは BFS の「近いところから遠いところへ」という考え方と本質的に一致します。基本的な手順は次の3ステップです。走査の開始頂点startVetをキューに追加し、ループを開始します。ループの各反復で、キュー先頭の頂点を取り出してデキュー訪問を記録し、その後その頂点のすべての隣接頂点をキューの末尾に追加します。手順2.を繰り返し、すべての頂点が訪問されると終了します。頂点の重複走査を防ぐため、どの頂点が訪問済みかを記録するハッシュ集合visitedを用います。ヒントハッシュ集合とはハッシュ集合はvalueを持たずkeyだけを格納するハッシュテーブルとみなせます。$O(1)$ の時間計算量でkeyの追加・削除・検索・更新ができ、keyの一意性に基づいてデータの重複排除などの場面で広く使われます。BFS / DFS では「訪問済み頂点の重複排除」に最適なデータ構造です。本リポジトリの日本語版コードから、Python 実装の核心部分を見てみましょう全文は graph_bfs.py。def graph_bfs(graph: GraphAdjList, start_vet: Vertex) - list[Vertex]: 幅優先探索 # 頂点の走査順序 res [] # 訪問済み頂点を記録するためのハッシュ集合 visited setVertex # BFS の実装にキューを用いる que dequeVertex # 頂点 vet を起点に、すべての頂点を訪問し終えるまで繰り返す while len(que) 0: vet que.popleft() # 先頭の頂点をデキュー res.append(vet) # 訪問した頂点を記録 # この頂点のすべての隣接頂点を走査 for adj_vet in graph.adj_list[vet]: if adj_vet in visited: continue # 訪問済みの頂点をスキップ que.append(adj_vet) # 未訪問の頂点のみをキューに追加 visited.add(adj_vet) # この頂点を訪問済みにする # 頂点の走査順を返す return res実装上の重要なポイントは、頂点をキューに追加する時点でvisitedへ登録することです。仮に「デキューした時点」で訪問済みにする実装にすると、同じ頂点が複数回キューに積まれ、重複訪問が発生します。C 版graph_bfs.cppではunordered_setVertex *とqueueVertex *を用いて同じロジックを実現しています。また C 版の graph_bfs.c は、キューと訪問済み配列を自前実装しています。isVisited関数は配列を線形走査するため $O(n)$ となり、Python/C 版のハッシュ集合 $O(1)$ とは実装上の差がありますが、これは「C 言語に標準のハッシュ集合がない」という制約に合わせた教育的な代替実装です。言語機能の違いがアルゴリズムの本質FIFO キュー 訪問済み管理を変えないことを対比して学べる好例といえます。BFS のアルゴリズムの流れを、頂点ごとの状態遷移として下図シリーズで追うことができますgraph_traversal.assets に step1 〜 step11 が格納されています。1〜3始点をキューへ投入し、第1層の隣接頂点を順にキューへ追加。4〜7第2層、第3層へとキューから取り出して訪問を記録。8〜11すべての頂点を訪問し、キューが空になって終了。走査順序列は一意ではない!!! question 幅優先走査の順序列は一意ですか 一意ではありません。幅優先走査は「近いところから遠いところへ」の順で走査することだけを要求し、同じ距離同一層にある複数の頂点の走査順は任意に入れ替えて構いません。上図を例にすると、頂点 $1$ と $3$ の訪問順は交換でき、頂点 $2$、$4$、$6$ の訪問順も任意に入れ替えられます。つまり BFS は「層の順序だけ」を保証し、同一層内の順序はグラフの隣接リスト内の並びや実装に依存します。計算量の分析時間計算量すべての頂点は1回ずつキューに入り、1回ずつキューから出るため $O(|V|)$ です。隣接頂点を走査する過程では、無向グラフの場合すべての辺が2回訪問されるため $O(2|E|)$ となり、全体で$O(|V| |E|)$です。空間計算量結果リストres、ハッシュ集合visited、キューqueに含まれる頂点数はいずれも最大で $|V|$ であるため、$O(|V|)$です。深さ優先走査DFS「行き止まりまで進んで戻る」の走査戦略深さ優先走査は、まず行けるところまで進み、進めなくなったら戻る走査方法です。下図のように、左上の頂点から出発し、現在の頂点の隣接頂点のひとつを訪問して、行き止まりに達するまで進んだら一つ前の頂点へ戻り、再び別の方向へ進んで行き止まりまで進んで戻る、という操作を繰り返し、すべての頂点の走査が完了するまで続けます。アルゴリズムの実装再帰と訪問済みハッシュ集合この「行き止まりまで進んでから戻る」パターンは、通常再帰に基づいて実装されます。BFS と同様に、頂点の重複訪問を避けるために訪問済みハッシュ集合visitedを用います。Python 実装の核心部分は次のとおりです全文は graph_dfs.py。def dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex): 深さ優先走査の補助関数 res.append(vet) # 訪問した頂点を記録 visited.add(vet) # この頂点を訪問済みにする # この頂点のすべての隣接頂点を走査 for adjVet in graph.adj_list[vet]: if adjVet in visited: continue # 訪問済みの頂点をスキップ # 隣接頂点を再帰的に訪問 dfs(graph, visited, res, adjVet) def graph_dfs(graph: GraphAdjList, start_vet: Vertex) - list[Vertex]: 深さ優先探索 # 頂点の走査順序 res [] # 訪問済み頂点を記録するためのハッシュ集合 visited set[Vertex]() dfs(graph, visited, res, start_vet) return res補助関数dfsが「現在の頂点の訪問記録 → 各隣接頂点への再帰」を行い、visitedを引数で受け渡して共有する点がポイントです。再帰呼び出しのスタックがそのまま「探索経路の深さ」を担うため、明示的なスタックを用意する必要がありません。C 版graph_dfs.cppも同一の構造で、unordered_setVertex * visitedを参照渡ししています。C 版graph_dfs.cでは、訪問済み配列resそのものを探索済み判定に使う実装になっています。過程の追跡再帰の「下降」と「バックトラック」深さ優先走査のアルゴリズムの流れは、下図の step1 〜 step11graph_traversal.assetsで確認できます。直線の破線は下向きの再帰呼び出しを表し、新しい頂点を訪問するために新たな再帰メソッドが開始されたことを意味します。曲線の破線は上向きのバックトラックを表し、この再帰メソッドがすでに戻って、呼び出し元の位置までたどり着いたことを意味します。理解を深めるには、図とコードを結びつけて、各再帰メソッドがいつ開始し、いつ戻るかを頭の中であるいは紙に書き出してシミュレーションしてみるのが効果的です。走査順序列は一意ではない!!! question 深さ優先走査の順序列は一意ですか 幅優先走査と同様に、深さ優先走査の順序列も一意ではありません。ある頂点が与えられたとき、どの方向を先に探索してもよく、つまり隣接頂点の順序は任意に入れ替えられ、それでも深さ優先走査になります。この「順序の自由度」は木の走査と対応づけて考えるとわかりやすいです。木の走査を例にすると、「根 → 左 → 右」「左 → 根 → 右」「左 → 右 → 根」はそれぞれ先行順pre-order、中間順in-order、後行順post-order走査に対応します。これらは3種類の異なる走査優先順位を表していますが、いずれも「1本の経路を深く掘り下げてから戻る」という意味では深さ優先走査に属します。すなわち、DFS の順序列は「隣接頂点をどの順で試すか」の選択次第で変わりうるのです。計算量の分析時間計算量すべての頂点は1回ずつ訪問されるため $O(|V|)$、すべての辺は2回ずつ訪問されるため $O(2|E|)$、よって全体で$O(|V| |E|)$です。空間計算量結果リストresとハッシュ集合visitedに含まれる頂点数は最大で $|V|$ であり、再帰の深さも最大で $|V|$グラフが極端な直線状の場合であるため、$O(|V|)$です。なお、再帰実装の空間消費はコールスタック上に積まれるため、頂点数が非常に大きいグラフでは反復 明示的スタックへの置き換えを検討する場合もあります。BFS と DFS の比較と使い分けBFS と DFS はどちらもすべての頂点を $O(|V||E|)$ で走査しますが、訪問順の性質が異なります。観点幅優先走査BFS深さ優先走査DFS基本戦略近い頂点から遠い頂点へ、層ごとに拡張1本の経路を深く掘り下げ、行き止まりで戻る主要データ構造キューFIFO再帰コールスタック訪問順序の性質始点からの「距離層」が単調非減少経路の深さを優先代表的な用途最短経路無重み、層ごとの到達性調査連結成分の検出、トポロジカルソート、迷路探索など空間計算量$O(V)$$O(V)$再帰の深さ分時間計算量$O(VE)$$O(VE)$※ 代表用途はアルゴリズムの一般論としての整理であり、本リポジトリの当該章の範囲を超える内容です。動作確認リポジトリのコードを実行してみる本リポジトリでは各章のコードを言語ごとに実行できます。日本語版のグラフ走査コードは以下にあります。Pythongraph_bfs.py、graph_dfs.pyCgraph_bfs.cpp、graph_dfs.cppCgraph_bfs.c、graph_dfs.c各コード末尾の Driver Code では、次のような無向グラフを構築して走査結果を出力します。BFS 用グラフ頂点 $0$〜$9$頂点数 $|V|10$、辺数 $|E|12$。辺は $0$-$1$, $0$-$3$, $1$-$2$, $1$-$4$, $2$-$5$, $3$-$4$, $3$-$6$, $4$-$5$, $4$-$7$, $5$-$8$, $6$-$7$, $7$-$8$。DFS 用グラフ頂点 $0$〜$6$$|V|7$。辺は $0$-$1$, $0$-$3$, $1$-$2$, $2$-$5$, $4$-$5$, $5$-$6$。たとえば Python の BFS コードは、頂点 $0$ を始点として0 - 1 - 3 - 2 - 4 - 6 - 5 - 7 - 8同一層内の順序は実装依存で変わりうるのような走査列をvets_to_vals(res)で数値に変換して表示します。実行環境の構築方法や Docker による一括実行については installation.md を参照してください。まとめグラフの走査は木の走査の一般化であり、BFSキューによる層次拡張とDFS再帰による深掘りとバックトラックの2系統があります。どちらも訪問済み頂点を記録するハッシュ集合が必須であり、これがないと巡回グラフで無限ループに陥ります。BFS も DFS も時間計算量は $O(|V||E|)$、空間計算量は $O(|V|)$ ですが、訪問順の性質が異なるため用途に応じて使い分けます。両者の走査順序列はどちらも一意ではありません。木の先行順・中間順・後行順は DFS の3つの特殊ケースとみなせます。本記事で扱った走査の理解は、後続の グラフ探索の応用 や、経路探索・最短経路などのより高度なグラフアルゴリズムを学ぶ土台となります。図解ステップgraph_traversal.assetsとコードを突き合わせながら、ぜひ手を動かして確認してみてください。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考