C++でちょうどk個の辺を持つ始点から終点へのウォーク（経路）の総数を求める方法

このチュートリアルでは、グラフ上において始点（ソース）から終点（デスティネーション）まで、ちょうどk本の辺を使って到達できるウォーク（歩行経路）の総数を求めるC++プログラムについて解説します。

前提として、グラフ（隣接行列）と始点・終点の値が与えられます。私たちのタスクは、始点から出発して終点に至るまでの経路のうち、正確にk本の辺を通るものをすべて数え上げることです。

アルゴリズムの考え方

ここでは再帰を用いたシンプルなアプローチを採用します。基本的な考え方は次のとおりです。

• k = 0 のとき：現在位置が終点と一致していれば、経路は1つと数えます。
• k = 1 のとき：現在位置から終点へ直接移動できる辺が存在すれば、1と数えます。
• k <= 0 の場合：それ以外は経路として成立しないため0を返します。
• それ以外の場合：現在のノードから隣接するすべてのノードへ移動し、残りのステップ数を1減らして再帰的に呼び出し、結果を合計します。

C++での実装例

#include <iostream>
using namespace std;
#define V 4

// 再帰を用いてウォークの数を数える
int countwalks(int graph[][V], int u, int v, int k){
    if (k == 0 && u == v)
       return 1;
    if (k == 1 && graph[u][v])
       return 1;
    if (k <= 0)
       return 0;
    int count = 0;
    // 隣接ノードへ移動する
    for (int i = 0; i < V; i++)
       if (graph[u][i] == 1)
          count += countwalks(graph, i, v, k-1);
    return count;
}

int main(){
    int graph[V][V] = {
       {0, 1, 1, 1},
       {0, 0, 0, 1},
       {0, 0, 0, 1},
       {0, 0, 0, 0}
    };
    int u = 0, v = 3, k = 2;
    cout << countwalks(graph, u, v, k);
    return 0;
}

実行結果

2

実行結果の解説

この例では、頂点0（始点）から頂点3（終点）へ、ちょうど2本の辺を通る経路を数えています。該当する経路は以下の2つです。

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

そのため、出力は「2」となります。

計算量について

この再帰的な手法は直感的で理解しやすい反面、各ノードから最大V個のノードへ分岐するため、時間計算量はO(V^k)となります。kや頂点数が大きくなると非効率になるため、その場合は動的計画法（DP）や隣接行列のべき乗を利用することで、O(V^3 × log k) 程度まで高速化できます。これらの最適化手法については、別の記事で詳しく解説する予定です。