【C++】有向グラフの2つの頂点間にあるすべての経路を数える方法

このチュートリアルでは、有向グラフにおいて指定された2つの頂点（始点と終点）をつなぐ経路（パス）が全部で何通り存在するかを求めるC++プログラムについて解説します。

入力として有向グラフが与えられ、その中から2つの頂点間に成立しうるすべての単純経路（同じ頂点を2度通らない経路）の本数を数えるのが課題です。

アルゴリズムの考え方：DFSとバックトラッキング

この問題は、深さ優先探索（DFS）にバックトラッキングを組み合わせることで解けます。手順は次の通りです。

1. 始点から探索を開始し、現在の頂点に「訪問済み」の印を付けます。
2. 現在の頂点が終点と一致していれば、経路数を1つ増やします。
3. 終点でなければ、隣接する未訪問の頂点に対して再帰的に同じ処理を行います。
4. 探索が終わったら現在の頂点の訪問済みの印を解除して戻ります（バックトラック）。これにより、別の経路で同じ頂点を再び利用できるようになります。

訪問済みフラグを解除して戻るのがポイントです。これを忘れると、一度通った頂点を他の経路で使えなくなり、正しい経路数を数えられません。

C++での実装例

#include<bits/stdc++.h>
using namespace std;

// 有向グラフの構築
class Graph {
    int V;
    list<int> *adj;
    void countPathsUtil(int, int, bool [], int &);
public:
    // コンストラクタ
    Graph(int V);
    void addEdge(int u, int v);
    int countPaths(int s, int d);
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int u, int v) {
    adj[u].push_back(v);
}

int Graph::countPaths(int s, int d) {
    // すべての頂点を未訪問として初期化
    bool *visited = new bool[V];
    memset(visited, false, V);
    int pathCount = 0;
    countPathsUtil(s, d, visited, pathCount);
    return pathCount;
}

void Graph::countPathsUtil(int u, int d, bool visited[], int &pathCount) {
    visited[u] = true;
    // 現在の頂点が終点と同じなら、経路数をカウントアップ
    if (u == d)
        pathCount++;
    // 終点でない場合は、隣接する未訪問の頂点を再帰的に探索
    else {
        list<int>::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
            if (!visited[*i])
                countPathsUtil(*i, d, visited, pathCount);
    }
    // バックトラック：訪問済みフラグを解除
    visited[u] = false;
}

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(2, 0);
    g.addEdge(2, 1);
    g.addEdge(1, 3);

    int s = 2, d = 3;
    cout << g.countPaths(s, d);
    return 0;
}

出力

3

コードの解説

上記の例では、4つの頂点を持つ有向グラフを作成し、頂点2から頂点3への経路を数えています。実際に存在する経路は次の3通りです。

• 2 → 0 → 3
• 2 → 1 → 3
• 2 → 0 → 1 → 3

したがって、出力は 3 となります。

countPaths() 関数は訪問管理用の配列を用意して補助関数 countPathsUtil() を呼び出す役割を担い、countPathsUtil() が実際の再帰的なDFSとバックトラッキングを行います。経路数は参照渡し（int&）の変数で共有されるため、再帰のどの深さで終点に到達しても正しくカウントされます。

計算量について

この手法はすべての単純経路を列挙するため、最悪の場合の時間計算量は頂点数の階乗オーダー（O(V!)）に近い指数時間になります。そのため、頂点数が非常に多いグラフには不向きですが、「経路の総数そのもの」が必要な場面ではシンプルで確実なアプローチです。単なる到達可能性の判定や最短経路が目的であれば、BFSやダイクストラ法など計算量の少ないアルゴリズムを選ぶべきでしょう。