C++のBFS（幅優先探索）で始点から終点までのすべての経路を出力する方法

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

有向グラフとは

有向グラフとは、各辺に向きがあり、頂点Aから頂点Bへの一方向だけを結ぶグラフのことです。無向グラフと異なり、辺は一方通行と考えることができます。

問題を理解するための例

具体的な例を見てみましょう。始点を K、終点を P とした場合、出力は次のようになります。

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

この例では、グラフを辿りながら K から P に至るすべての経路を探索し、出力しています。つまり、始点から終点へ到達できる経路をすべて見つけることが目的です。

解決のアプローチ

始点から終点までのすべての経路を出力するには、グラフを探索しながら経路を保存し、有効な経路だけを出力する必要があります。

DFS（深さ優先探索）を使えばこの処理は比較的簡単ですが、BFSを使う場合は実装に少し工夫が必要です。

この問題を解くには、経路そのものを保存できるキューを用意します。処理の流れは以下のとおりです。

1. 始点ノードだけを含む経路をキューに追加し、BFSによる探索を開始します。
2. キューから経路を取り出し、その経路の末尾にある頂点を確認します。
3. 末尾の頂点が終点であれば、その経路を出力します。
4. 終点でなければ、末尾の頂点に隣接する頂点のうち、まだ経路に含まれていないものを経路に追加してキューに戻します。
5. キューが空になるまでこの処理を繰り返します。

すでに経路内に存在する頂点を追加しないことで、同じ頂点を何度も通るループを防ぐことができます。

サンプルプログラム

以下のC++プログラムで、解法がより明確になります。

#include <bits/stdc++.h>
using namespace std;
void printPath(vector<char>& path) {
   int size = path.size();
   for (int i = 0; i < size; i++)
   cout<<path[i]<<" ";
   cout<<endl;
}
int isVertexVisited(char x, vector<char>& path) {
   int size = path.size();
   for (int i = 0; i< size; i++)
   if (path[i] == x)
   return 1;
   return 0;
}
void pathSourceToDestination(vector<vector<char> >&g, char src, char dst, int v) {
   queue<vector<char> > q;
   vector<char> path;
   path.push_back(src);
   q.push(path);
   while (!q.empty()) {
      path = q.front();
      q.pop();
      char last = path[path.size() - 1];
      if (last == dst)
      printPath(path);
      for (int i = 0; i < g[last].size(); i++) {
         if (!isVertexVisited(g[last][i], path)) {
            vector<char> newpath(path);
            newpath.push_back(g[last][i]);
            q.push(newpath);
         }
      }
   }
}
int main() {
   vector<vector<char> > g;
   int v = 4;
   g.resize(4);
   g['X'].push_back('S');
   g['X'].push_back('A');
   g['X'].push_back('N');
   g['A'].push_back('S');
   g['N'].push_back('X');
   g['N'].push_back('A');
   char src = 'N', dst = 'S';
   cout<<"path from src "<<src<<" to dst "<<dst<<" are \n";
   pathSourceToDestination(g, src, dst, v);
   return 0;
}

出力

path from src N to dst S are
N X S
N A S
N X A S

このように、キューに経路を格納しながらBFSを実行することで、始点 N から終点 S までのすべての経路（N X S、N A S、N X A S）を出力できています。経路ごとに頂点の重複チェックを行うことで、無限ループを回避しつつ、すべての有効な経路を網羅的に列挙できるのがこの手法のポイントです。