関連記事：
Algorithms & Data Structure Content List Algorithms #1 Sort
- ComputerScience
#SWE#ComputerScience
本ノートでは各種グラフアルゴリズムについて記述します。
グラフ
定義
グラフ（graph）については一連の複雑ではない定義があり、ここでは簡単に列挙します。
- グラフとは、一連の頂点（vertex）とそれらを結ぶ辺（edge）からなるデータモデルを指す。
- 平行辺とは、同一の頂点対を結ぶ複数の辺を指す。
- 自己ループとは、頂点が自分自身と結ばれる辺を指す。
- 平行辺と自己ループを含まないグラフを単純グラフ（simple graph）と呼ぶ。特に断りがない場合、グラフとは単純グラフを指す。
- 2つの頂点が1本の辺で結ばれている場合、それらは隣接（neighbor）である。
- 有向グラフとは、辺 ab と辺 ba を別の辺とみなすグラフである。無向グラフでは辺 ab と辺 ba は同じ辺とみなす。
- 無向グラフにおいて、頂点の次数（degree）とは、その頂点を一端とする辺の数である。
- 有向グラフにおいて、頂点の出次数とはそこから出る辺の数、入次数とはそこに入る辺の数である。
- パス（path）とは、順序的に連結された辺とそれらが通る頂点の集合である。単純パスは頂点の重複のないパスである。
- 環（cycle、loop）とは、少なくとも1本の辺を含み、始点と終点が同じパスである。単純環は、始点と終点が同じである必要がある以外、頂点と辺の重複のない環である。
- パスの長さとは、その中の辺の数である。
- 任意の頂点から任意の頂点へ少なくとも1本のパスが存在するグラフを連結グラフ（connected graph）と呼ぶ。
- 非連結グラフは複数の連結部分グラフからなり、それらを連結成分（connected components）と呼ぶ。
- 木（tree）とは、環のない連結グラフである。
ここまでで、本ノートの内容を議論するには十分です。
実装
実装の観点では、グラフは辺と頂点を維持すればよい。しかし、維持する必要のあるメソッドは複雑になる可能性があり、例えば任意のノードの次数を返す関数、頂点の隣接頂点を返す関数、最大次数、頂点から別の頂点へのパスが存在するか判定するメソッドなどが必要である。
様々なニーズに基づき、グラフには多くの異なるデータ構造表現がある。性能と機能の両面で満足のいく方法の一つが隣接リスト配列（adjacency array）である。vector<vector<int>> V を格納し、V[i] は i 番目の頂点の隣接頂点のインデックス配列を表す。以下の議論の便宜のため、この方式でグラフを記録する。
無向グラフアルゴリズム
DFS（深さ優先探索）
深さ優先探索（Depth First Search、DFS）は再帰アルゴリズムであり、以下の手順で説明できる：
- 探索の始点を選び、訪問済みとしてマークする。
- マークされていないすべての隣接頂点を再帰的に訪問する。
DFS を適用する最も古典的なタスクは、与えられたグラフが連結かどうかを調べることである。この問題は、グラフ G の頂点 u から別の頂点 v へのパスが存在するかどうかと等価である。これらはそれぞれ連結性問題と単一始点パス問題と呼ばれ、上述の通り等価である。
頂点数と同じ長さの marked 配列を維持し、訪問済みの頂点をマークする。連結性問題について、DFS で解決できるいくつかのサブ問題がある：
- 与えられたグラフが連結かどうか：DFS 終了後に marked 配列がすべてマークされているか判定し、そうであれば true、そうでなければ false を返す。
- 与えられたグラフの連結成分の数：marked 配列がすべてマークされるまで count を維持し、再帰呼び出しが底に達するたびに marked 配列がすべてマークされているか判定する。そうであれば count を返し、そうでなければ count++ する。
- 与えられたグラフの点 u と点 v が同じ連結成分にあるか：点 u から DFS を開始し、DFS 終了後に marked 配列で v が訪問済みであれば、同じ連結成分にあることを示す。
上記の3番目のサブ問題は、実は単一始点パス問題と完全に一致する。
何の機能も持たない DFS は以下のようになる：
上記の実装では、marked 配列のみを維持し、タスクは何も完了していない。サブ問題1（与えられたグラフが連結かどうか）を解決するには、DFS 終了時に判定すればよい。
抽象的な部分はここまでで十分である。現実の問題に反映する際は、様々な状況でグラフ、辺、頂点の変化を正確に識別する必要がある。以下は LeetCode における DFS のいくつかの典型的な表現形式である。
- Number of Islands（LC200）
BFS（幅優先探索）
連結成分
最短経路アルゴリズム
Dijkstra アルゴリズム
参考文献：
- アルゴリズム（第4版）、Robert Sedgewick 著、中国工信出版集团/人民邮电出版社、謝路雲訳