グラフ探索アルゴリズムとは？
ITの世界における「グラフ」とは、棒グラフや円グラフのことではありません。ノード（頂点）と、それらを結ぶエッジ（辺）で構成されるデータ構造のことを指します。 SNSの友達関係（人がノード、友達関係がエッジ）や、道路網（交差点がノード、道路がエッジ）などをイメージすると分かりやすいでしょう。
そしてグラフ探索アルゴリズムとは、このグラフの中の全てのノードを体系的に訪問したり、特定のノードを探したり、あるノードから別のノードへの最適な経路を見つけたりするための「手順」や「計算方法」の総称です。 私たちの身の回りにある便利なサービスの多くは、このグラフ探索アルゴリズムによって支えられています。
基本の2大探索アルゴリズム：BFSとDFS
グラフ探索には様々な種類がありますが、その中でも最も基本的で重要なのが「幅優先探索（BFS）」と「深さ優先探索（DFS）」です。 この2つの違いを理解することが、グラフ探索アルゴリズムを学ぶ第一歩となります。
幅優先探索 (BFS: Breadth-First Search)
幅優先探索は、スタート地点から近い順に、まるで水面に広がる波紋のように探索していく手法です。 まずスタート地点の隣にあるノードを全て調べ、次にその隣のノードを全て調べる、というように層を広げながら探索を進めます。 この特性から、重み（コスト）がないグラフにおける最短経路を見つけるのに非常に有効です。
深さ優先探索 (DFS: Depth-First Search)
深さ優先探索は、一つの道をとにかく行けるところまで深く進んでいく手法です。 行き止まりにぶつかったら、一つ前に戻って別の道を進みます。迷路を解くときに、まず一つの道を突き進んでみる感覚に似ています。 全てのノードを訪れる必要がある場合や、解が存在するかどうかだけを知りたい場合などに使われます。
BFSとDFSの比較
| 特徴 | 幅優先探索 (BFS) | 深さ優先探索 (DFS) |
|---|---|---|
| 探索のイメージ | 近くから順に、層を広げるように探索 | 行けるところまで深く、行き止まりまで進む |
| 得意なこと | 最短経路の発見（辺の重みが全て同じ場合） | 連結性の確認、全てのノードの訪問 |
| 使用するデータ構造 | キュー (Queue): 先入れ先出し | スタック (Stack) または 再帰関数: 後入れ先出し |
| メモリ消費 | 探索範囲が広がると大きくなる傾向がある | 比較的少ないメモリで済むことが多い |
Pythonによる簡単なコード例
以下は、隣接リストで表現されたグラフを探索する簡単なPythonコードの例です。
# グラフの例 (隣接リスト表現)
# 'A': ['B', 'C'] は、ノードAがBとCに繋がっていることを示す
graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']
}
# 幅優先探索 (BFS)
def bfs(graph, start_node): visited = [] # 訪問済みのノードを記録 queue = [start_node] # これから訪問するノードを格納するキュー visited.append(start_node) while queue: node = queue.pop(0) # キューの先頭からノードを取り出す print(node, end=" ") for neighbor in graph[node]: if neighbor not in visited: visited.append(neighbor) queue.append(neighbor)
# 深さ優先探索 (DFS) - 再帰を使った実装
def dfs(graph, node, visited=None): if visited is None: visited = set() # 訪問済みのノードを記録するセット visited.add(node) print(node, end=" ") for neighbor in graph[node]: if neighbor not in visited: dfs(graph, neighbor, visited)
print("幅優先探索 (BFS) の結果:")
bfs(graph, 'A') # 出力例: A B C D E F
print("\n\n深さ優先探索 (DFS) の結果:")
dfs(graph, 'A') # 出力例: A B D E F C 応用的なグラフ探索アルゴリズム
BFSやDFSは基本的な探索手法ですが、より複雑な問題に対応するために、これらを応用した多くのアルゴリズムが存在します。 特に有名なのが、辺に「重み（コストや距離）」が設定された重み付きグラフで最短経路を見つけるためのアルゴリズムです。
ダイクストラ法 (Dijkstra’s Algorithm)
ダイクストラ法は、重み付きグラフにおいて、ある一つのスタート地点から他の全てのノードへの最短経路を見つけるためのアルゴリズムです。 ただし、辺の重みは非負（0以上）でなければならないという制約があります。 カーナビゲーションシステムで、ある地点から目的地までの最短時間や最短距離を計算する際に利用される代表的なアルゴリズムです。
A* (A-star) アルゴリズム
A*アルゴリズムは、ダイクストラ法をさらに効率化したものです。 ダイクストラ法がスタート地点から全方位的に探索を広げるのに対し、A*はゴール地点への「推定距離（ヒューリスティック）」を利用して、よりゴールに近い方向を優先的に探索します。 これにより、無駄な探索を大幅に削減できる可能性があります。 ゲームのキャラクターが障害物を避けながら目的地まで移動する経路探索など、リアルタイム性が求められる場面で広く活用されています。
実世界での活用事例
グラフ探索アルゴリズムは、私たちの生活を支える様々な技術の裏側で活躍しています。
- 経路案内サービス: Googleマップなどの地図アプリは、ダイクストラ法やA*アルゴリズムを使って、現在地から目的地までの最適なルート（最短時間、最短距離、乗り換え回数が少ないなど）を計算しています。
- ソーシャルネットワーク (SNS): FacebookやX（旧Twitter）などで「友達の友達」を表示したり、共通の友人がいる人をおすすめしたりする機能は、BFSを使って実現されています。
- インターネットの検索エンジン: 検索エンジンがWebページを収集（クロール）する際、Webページをノード、リンクをエッジと見立てて、BFSやDFSの手法を用いて効率的に巡回しています。
- ネットワークルーティング: インターネット上でデータ（パケット）を送信する際、ルーターが最適な経路を選択するためにもグラフ理論に基づいたアルゴリズムが使われています。
- ゲームAI: ゲーム内のキャラクターがプレイヤーを追跡したり、目的地まで移動したりする際の賢い動きは、A*アルゴリズムなどによって制御されています。
まとめ
グラフ探索アルゴリズムは、点と線の関係で表される様々な問題を解決するための強力なツールです。 基本的なBFSとDFSから、最短経路を求めるダイクストラ法やA*アルゴリズムまで、その種類は多岐にわたります。 これらのアルゴリズムの基本的な考え方を理解することで、普段何気なく使っているサービスの仕組みがより深く分かり、プログラミングの世界がさらに面白くなるはずです。