グラフデータ構造と走査（トラバーサル）アルゴリズムの基礎

この記事では、グラフデータ構造とは何か、そしてその走査（トラバーサル）アルゴリズムについて詳しく解説します。

グラフは非線形データ構造の一種であり、いくつかのノード（頂点）とそれらを結ぶ辺（エッジ）で構成されます。辺には有向と無向の2種類があります。グラフは一般に G(V, E) の形式で表現できます。ここで V は頂点の集合、E は辺の集合を表します。例えば、下図のグラフは G({A, B, C, D, E}, {(A, B), (B, D), (D, E), (B, C), (C, A)}) と表すことができます。

グラフの走査アルゴリズムには主に2種類あります。それが「幅優先探索（Breadth First Search：BFS）」と「深さ優先探索（Depth First Search：DFS）」です。

幅優先探索（BFS）とは

幅優先探索（BFS）は、与えられたグラフのすべてのノードを訪問するためのアルゴリズムです。この手法では、まず1つのノードを選択し、その隣接ノードを順番にすべて訪問します。隣接する頂点をすべて処理し終えたら、次の未訪問の頂点へ移動し、同様にその隣接頂点を調べていきます。キュー（Queue）を使用するのが特徴で、開始頂点から近い順に幅広く探索が進みます。

BFSのアルゴリズム

bfs(vertices, start)
入力: 頂点のリストと開始頂点
出力: グラフが連結であれば、すべてのノードを走査する
Begin
    空のキュー que を定義する
    最初にすべてのノードの状態を「未訪問」としてマークする
    開始頂点を que に追加する
    while que が空でない間、繰り返す:
        que から要素を取り出し、u に代入する
        頂点 u を表示する
        u に隣接するすべての頂点 i に対して:
            vertices[i] が未訪問であれば:
                vertices[i] を一時的に訪問済みとしてマークする
                v をキューに追加する
        u を完全に訪問済みとしてマークする
End

深さ優先探索（DFS）とは

深さ優先探索（DFS）もまた、グラフを走査するための代表的なアルゴリズムです。このアルゴリズムでは、まず開始頂点が与えられ、隣接頂点が見つかると、すぐにその頂点へ移動します。そして同じ方法でさらに奥へと探索を進めていきます。スタック（Stack）や再帰呼び出しを用いるのが一般的で、一本道を深く掘り進めるように探索を行う点がBFSとの大きな違いです。

DFSのアルゴリズム

dfs(vertices, start)
入力: すべての頂点のリストと開始ノード
出力: グラフ内のすべてのノードを走査する
Begin
    最初にすべてのノードの状態を「未訪問」に設定する
    開始ノードをスタックにプッシュする
    while スタックが空でない間、繰り返す:
        スタックから要素をポップし、u に代入する
        ノード u を表示する
        u が未訪問であれば:
            u を訪問済みとしてマークする
            u に接続されているすべてのノード i に対して:
                i 番目の頂点が未訪問であれば:
                    i 番目の頂点をスタックにプッシュする
                    i 番目の頂点を訪問済みとしてマークする
End