ネットワーク・経路探索の基礎となるグラフアルゴリズム。BFS・DFS・最短経路を理解しましょう。
日野 こむぎ
グラフって、あのネットワークの図みたいなやつ?
藤森 さやか 先生
グラフは頂点 (ノード) と辺 (エッジ) で表すデータ構造よ。
SNSの友達関係、地図の道路網、Webページのリンク構造などはすべてグラフでモデル化できるの。
青木 澪
代表的な走査アルゴリズムは2種類: 幅優先探索 (BFS) と深さ優先探索 (DFS)。
桃井 すみれ
違いはなんですかぁ?
青木 澪
BFSは近い順 (層ごと) に探索して、キューを使うの。
DFSは深く潜って戻る方式で、スタック (再帰) を使うのよ。
最短経路はBFSで求まるわ。
藤森 さやか 先生
重み付き (距離付き) グラフの最短経路にはダイクストラ法が定番。
地図ナビの「最短ルート計算」もこれに基づいているわ。
青木 澪
他にも、最小全域木を求める{kw('プリム法', 'Prim法。
最小全域木 (MST) を頂点ごとに成長させて求めるアルゴリズム')}や{kw('クラスカル法', 'Kruskal法。
最小全域木を辺の小さい順にUnion-Findで構築するアルゴリズム')}、全点間最短経路の{kw('フロイド法', 'Floyd-Warshall法。
全点間最短経路を動的計画法で求めるアルゴリズム')}など、グラフ問題は奥が深いんです。
日野 こむぎ
じゃあGoogleマップも、結局はグラフアルゴリズムなんだ!
確認クイズ
重み付きグラフで、ある始点から他の全頂点への最短経路を求めるアルゴリズムはどれか。
- BFS
- DFS
- ダイクストラ法
- クイックソート
こたえを見る
正解: 3. ダイクストラ法
ダイクストラ法 (Dijkstra法) は重み付きグラフで単一始点最短経路を求める標準アルゴリズム。地図ナビなどで広く使われています。BFSは重みなしの場合の最短経路に使えます。