C++で始点から終点までのすべての経路を出力する方法｜深さ優先探索（DFS）による実装

この記事では、有向グラフが与えられたときに、始点（ソース）から終点（デスティネーション）までのすべての経路を出力する問題を、C++で解く方法を解説します。

有向グラフとは？

有向グラフとは、各辺に向きが定められており、頂点Aから頂点Bへと一方向に進むことができるグラフのことです。逆向き（BからA）には、対応する逆向きの辺が存在しない限り移動できません。

問題の例

具体例を使って問題を理解しましょう。下図のようなグラフを考えます。

始点を「K」、終点を「P」とした場合の出力は次のようになります。

出力：

K -> T -> Y -> A -> P
K -> T -> Y -> P
K -> A -> P

このように、KからPへ至る経路をすべて探索し、見つかった順に出力します。

解き方：深さ優先探索（DFS）

この問題は、深さ優先探索（Depth-First Search：DFS）を使うことで解けます。基本的な考え方は以下の通りです。

• 始点から探索を開始し、訪れた頂点を順番に経路配列（パス配列）に記録していきます。
• 同時に、その頂点に訪問済みマークを付けます（同じ頂点を何度も訪れて無限ループになるのを防ぐため）。
• 隣接する未訪問の頂点があれば、再帰的に探索を続けます。
• 終点に到達したら、そこまでの経路を出力します。
• 探索を戻すとき（バックトラック時）には、訪問済みマークを解除し、経路配列から頂点を取り除きます。これにより、別の経路も正しく探索できるようになります。

C++での実装例

上記のロジックを実装したプログラムがこちらです。

#include<iostream>
#include <list>
using namespace std;
class Graph {
    int V;
    list<int> *adj;
    void findNewPath(int , int , bool [], int [], int &);
    public:
    Graph(int V);
    void addEdge(int u, int v);
    void printPaths(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);
}
void Graph::printPaths(int s, int d) {
    bool *visited = new bool[V];
    int *path = new int[V];
    int path_index = 0;
    for (int i = 0; i < V; i++)
    visited[i] = false;
    findNewPath(s, d, visited, path, path_index);
}
void Graph::findNewPath(int u, int d, bool visited[],
int path[], int &path_index) {
    visited[u] = true;
    path[path_index] = u;
    path_index++;
    if (u == d) {
        for (int i = 0; i<path_index; i++)
        cout<<path[i]<<" ";
        cout << endl;
    } else {
        list<int>::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
            if (!visited[*i])
                findNewPath(*i, d, visited, path, path_index);
    }
    path_index--;
    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<<"Following are all different paths from source to destination : \n";
    g.printPaths(s, d);
    return 0;
}

実行結果

Following are all different paths from source to destination :
2 0 1 3
2 0 3
2 1 3

コードのポイント

• visited[] 配列：各頂点が現在の経路内で既に使用されているかどうかを管理します。
• path[] 配列と path_index：現在探索中の経路を保持します。再帰呼び出しが深くなるほど、経路も伸びていきます。
• バックトラック処理：再帰関数の最後で path_index-- と visited[u] = false; を実行することで、状態を元に戻し、他の分岐の探索に備えています。

計算量について

グラフの構造によっては、始点から終点への経路の総数が爆発的に増える可能性があります。最悪の場合、計算量は頂点数に対して指数オーダーになり得るため、大規模なグラフに適用する際は注意が必要です。