【C++】2つの特定のノード間にパスが存在するかどうかを確認するプログラム

グラフにおいて「ある頂点から別の頂点へ到達できるか」を判定する問題は、経路探索やネットワーク解析など、さまざまな場面で登場する基本的な課題です。本記事では、C++を用いて、指定した2つのノード（頂点）間にパス（経路）が存在するかどうかを確認するプログラムを紹介します。

アルゴリズム

このプログラムでは、幅優先探索（BFS）をベースとした関数 isReach() を使い、始点 s から終点 d への到達可能性を調べます。処理の手順は以下の通りです。

開始
　　isReach() は、d が s から到達可能かどうかを判定する再帰的な関数である：
　　A) すべての頂点を「未訪問」としてマークする。
　　B) 現在のノードを「訪問済み」としてマークし、キューに追加する。
　　　 キューは、ある頂点の隣接頂点をすべて取得するために使用される。
　　C) キューから頂点を1つ取り出す（デキュー）。
　　D) 取り出した頂点 s に隣接するすべての頂点を取得する。
　　E) 隣接頂点が未訪問であれば、「訪問済み」としてマークし、キューに追加する。
　　F) その隣接ノードが目的地のノードであれば true を返す。
　　　 そうでなければ BFS を継続する。
終了

C++による実装例

以下のコードでは、隣接リスト（adjacency list）形式でグラフを表現し、BFSによって2頂点間の到達可能性を判定しています。

#include <iostream>
#include <list>
using namespace std;
class G {
    int n;
    list<int> *adj;
    public:
        G(int n);
        void addEd(int x, int w);
        bool isReach(int s, int d);
};
G::G(int n) { //コンストラクタ
    this->n = n;
    adj = new list<int> [n];
}
void G::addEd(int x, int w) { //グラフに辺を追加する
    adj[x].push_back(w); //x のリストに w を追加する
}
bool G::isReach(int s, int d) {
    if (s == d)
    return true;
    bool *visited = new bool[n];
    //すべての頂点を未訪問としてマークする
    for (int i = 0; i < n; i++)
        visited[i] = false;
    list<int> queue;
    //現在のノードを訪問済みとしてマークし、キューに追加する
    visited[s] = true;
    queue.push_back(s);
    list<int>::iterator i;
    while (!queue.empty()) {
        s = queue.front();
        queue.pop_front(); //キューから頂点を取り出す
        //隣接頂点が未訪問の場合
        for (i = adj[s].begin(); i != adj[s].end(); ++i) {
            if (*i == d)
                return true;
            if (!visited[*i]) {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
    return false;
}
int main() {
    G g(4);
    g.addEd(1, 3);
    g.addEd(0, 1);
    g.addEd(2, 3);
    g.addEd(1, 0);
    g.addEd(2, 1);
    g.addEd(3, 1);
    cout << "始点と終点の頂点を入力してください：(0〜3)";
    int a, b;
    cin >> a >> b;
    if (g.isReach(a, b))
        cout << "\n" << a << " から " << b << " へのパスが存在します";
    else
        cout << "\n" << a << " から " << b << " へのパスは存在しません";
    int t;
    t = a;
    a = b;
    b = t;
    if (g.isReach(a, b))
        cout << "\n" << a << " から " << b << " へのパスが存在します";
    else
        cout << "\n" << a << " から " << b << " へのパスは存在しません";
    return 0;
}

コードのポイント

• クラス G：頂点数 n と、各頂点の隣接頂点を格納するリスト配列 adj をメンバとして持ちます。
• addEd()：頂点 x から頂点 w への有向辺をグラフに追加します。
• isReach()：始点 s と終点 d が一致していれば即座に true を返します。それ以外は BFS で探索を進め、d に到達できれば true、キューが空になっても到達できなければ false を返します。
• main()：4頂点のグラフを構築し、入力された始点・終点について双方向（a→b と b→a）の到達可能性をそれぞれチェックします。addEd() が有向辺を追加するため、片方向だけが到達可能なケースも正しく判定できます。

実行結果

始点と終点の頂点を入力してください：(0〜3)
3 から 1 へのパスが存在します
1 から 3 へのパスが存在します

計算量について

BFSでは各頂点と各辺を高々1回ずつ処理するため、時間計算量は O(V + E) です。また、訪問状態を記録する配列とキューが必要となるため、空間計算量は O(V) となります（V は頂点数、E は辺数）。大規模なグラフでも効率的に動作するため、到達可能性の判定には広く使われる手法です。