C++でグラフ内の2つのノード間の経路を探索するプログラム

本記事では、C++を使って、与えられたグラフ上であるノード（頂点）から別のノードへ到達可能かどうかを判定するプログラムを紹介します。グラフの探索には、キューを用いた幅優先探索（BFS）を活用します。

アルゴリズムの流れ

始点 s から終点 d への到達可能性を判定する関数 isReach() は、以下の手順で動作します。

1. すべての頂点を「未訪問」として初期化します。
2. 現在のノード（始点）を訪問済みとしてマークし、キューに追加します。このキューは、各頂点の隣接頂点を順に処理するために使用されます。
3. キューから頂点を取り出し（デキュー）、その隣接頂点をすべて取得します。
4. 隣接頂点がまだ訪問されていなければ、訪問済みとしてマークし、キューに追加します。
5. 隣接頂点が目的のノード（終点 d）と一致した場合、true を返して終了します。一致しなければBFSの探索を続行します。
6. キューが空になっても終点に到達できなかった場合は、false を返します。

C++による実装例

#include <iostream>
#include <list>
using namespace std;

class G {
    int n;
    list<int> *adj;
public:
    // 関数の宣言
    G(int n);
    void addEd(int v, int u);
    bool isReach(int s, int d);
};

// コンストラクタ：頂点数分の隣接リストを作成
G::G(int n) {
    this->n = n;
    adj = new list<int>[n];
}

// グラフに辺を追加
void G::addEd(int v, int u) {
    adj[v].push_back(u);
}

// s から d へ到達可能かを判定する関数
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) {
            // 隣接ノードが目的地なら true を返す
            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 << "Enter the source and destination vertices: (0-3)";
    int a, b;
    cin >> a >> b;

    // a → b の経路をチェック
    if (g.isReach(a, b))
        cout << "\nThere is a path from " << a << " to " << b;
    else
        cout << "\nThere is no path from " << a << " to " << b;

    // b → a の経路もチェック（有向グラフ対応）
    int t;
    t = a;
    a = b;
    b = t;

    if (g.isReach(a, b))
        cout << "\nThere is a path from " << a << " to " << b;
    else
        cout << "\nThere is no path from " << a << " to " << b;

    return 0;
}

実行結果

Enter the source and destination vertices: (0-3)
There is a path from 3 to 1
There is a path from 1 to 3

解説

このプログラムでは、隣接リスト形式でグラフを表現しています。isReach() 関数はBFS（幅優先探索）をベースにしており、始点から順に隣接する頂点をキューに格納しながら探索を広げていきます。探索中に目的地のノードが見つかれば即座に true を返し、すべての到達可能な頂点を調べても見つからなければ false を返します。

また、main関数内では始点と終点を入れ替えて双方向の到達可能性を確認しています。これは、このグラフが有向グラフとして扱われているためで、「A→B に行けるからといって B→A にも行けるとは限らない」ことを示す良い例になっています。

計算量は、頂点数を V、辺数を E とすると O(V + E) となり、効率的な経路探索が可能です。