AからBへの最短ルートは？この問いは、カーナビから配送最適化、ネットワーク通信まで、あらゆる場所に現れる。グラフの探索アルゴリズムは、この問題を効率的に解く。深さ優先、幅優先、ダイクストラ。基本を知れば応用は広がる。

最短経路 DFS BFS ダイクストラ トポロジカルソート

グラフ探索

深さ優先探索（DFS）

DFS（Depth-First Search）

行けるところまで深く進み、行き止まりで戻る。

実装：再帰 or スタック

用途：連結性判定、サイクル検出、迷路探索

幅優先探索（BFS）

BFS（Breadth-First Search）

近いところから順に探索。

実装：キュー

用途：最短経路（重みなし）、レベル順走査

最短経路アルゴリズム

アルゴリズム 条件 計算量 用途
BFS 重みなし O(V+E) 単純な最短経路
ダイクストラ 非負の重み O((V+E)logV) ナビゲーション
ベルマンフォード 負の重みあり O(VE) 為替レート計算
A* ヒューリスティック 状況依存 ゲームAI、地図

トポロジカルソート

トポロジカルソート

DAG（有向非巡回グラフ）の頂点を、すべての辺が前から後ろを向くように並べる。

用途：タスクスケジューリング、依存関係の解決

実務での応用

WEB開発での応用

パッケージ管理：依存関係のトポロジカルソートでインストール順を決定。

ビルドシステム：ファイルの依存関係に基づくビルド順序。

ルーティング：ネットワーク経路の最適化。

クローラー：Webページの探索にBFS/DFS。

AI/MLでの応用

計算グラフ：ニューラルネットワークの順伝播・逆伝播。

強化学習：状態空間の探索、モンテカルロ木探索。

知識グラフ推論：エンティティ間の経路ベースの推論。

GNN：k-hopの近傍情報を集約（BFS的な考え方）。

深掘りリンク