データ構造におけるグラフ探索の基本：BFSとDFSの違いをわかりやすく解説

グラフは代表的な非線形データ構造の一つです。このデータ構造では、値（データ）を「ノード（頂点）」に格納し、ノード同士を「エッジ（辺）」で結びつけて表現します。グラフにデータを格納できるように、目的の要素を探して取り出すためには、探索（サーチ）の仕組みが必要になります。

グラフの探索には、主に次の2つの手法が用いられます。

• 幅優先探索（Breadth First Search / BFS）
• 深さ優先探索（Depth First Search / DFS）

幅優先探索（BFS）とは

幅優先探索（BFS）は、与えられたグラフのすべてのノードを巡回するためのアルゴリズムです。まず1つのノードを選択し、その隣接ノードを一つずつ順番に訪問していきます。隣接する頂点をすべて処理し終えたら、次の頂点へ移動し、再びその隣接頂点を確認します。

BFSを実装する際には、キュー（Queue）というデータ構造を使用します。処理対象の隣接頂点はすべてキューに追加され、ある頂点の隣接頂点への訪問が完了すると、キューから先頭の要素を1つ取り出し、その頂点から再び探索を続けます。この「近いノードから順に広げていく」性質により、BFSは最短経路問題などにも応用されます。

深さ優先探索（DFS）とは

深さ優先探索（DFS）もまた、グラフを巡回するためのアルゴリズムです。開始頂点が与えられると、隣接する頂点が見つかった時点でそちらへ即座に移動し、同じ要領でさらに奥へと進んでいきます。つまり、進める限りグラフの深い方向へ一気に到達し、それ以上進めなくなった時点で直前の頂点へバックトラック（後戻り）して、未探索の新しい経路を探します。

DFSを反復処理（イテレーティブ）で実装する場合は、スタック（Stack）というデータ構造が必要です。一方、再帰呼び出しを使って実装すれば、外部のスタックは不要となり、関数呼び出しの内部スタック（コールスタック）が自動的にその役割を果たします。

BFSとDFSの使い分けのポイント

両者は同じグラフを探索しますが、挙動が大きく異なります。BFSは「近くから順に」探索するため最短距離の計算に向き、DFSは「とことん深くまで」探索するため経路の列挙やサイクル検出、トポロジカルソートなどに適しています。用途に応じて適切な手法を選択することが重要です。