C++でBFS（幅優先探索）を用いて1つの頂点から他の全頂点への経路を求める方法

問題概要

この問題では、隣接リストとして表現された有向グラフが与えられます。課題は、BFS（幅優先探索）を使って、ある始点の頂点から他のすべての頂点への経路を見つけるプログラムを作成することです。

BFS（Breadth First Search：幅優先探索）とは、グラフを幅方向に広げながら頂点を巡回していくアルゴリズムです。探索が行き止まりに達したときに、次に探索を開始すべき頂点を覚えておくためにキューを使用するのが特徴です。

具体例を使って問題を確認してみましょう。

入力 −

出力

S
A <= S
B <= A <= S
C <= S
D <= C <= S

解決アプローチ

この問題を解くには、グラフ全体に対してBFS（幅優先探索）を実行します。そのために、ノードの訪問状態を管理するためのキューを作成します。あわせて訪問済み配列（visited array）を用意し、各頂点が既に訪問済みかどうかを0と1の2値で判定していきます。

それでは、解法の動作を理解するために、先ほどの例を順を追って見ていきましょう。

始点Sから出発した場合：

• ノードAへは、Sから直接アクセスできます。

• ノードBへ到達するには、まずノードAを訪問し、Aを経由してBへ進みます。

• ノードCへは、Sから直接アクセスできます。

• ノードDへ到達するには、まずノードCを訪問し、そこからDへ進みます。

このように、parent（親）配列に各頂点の一つ前の頂点を記録していくことで、任意の頂点から始点までの経路を辿れるようになります。BFSの計算量はO(V+E)（Vは頂点数、Eは辺数）であり、非常に効率的な手法です。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
void printPath(vector<int> parent, int initial, int node){
   while (initial != node){
      cout<<node<<" <= ";
      node = parent[node];
   }
   cout<<node<<endl;
}
void findPathBFS(vector<vector<int> > graphAdjList, int initial, int graphSize){
   vector<int> parent(graphSize, 0);
   vector<int> queue(graphSize, 0);
   int front = -1, rear = -1;
   vector<int> isVisited(graphSize, 0);
   isVisited[0] = 1;
   parent[0] = initial;
   queue[++rear] = initial;
   int k;
   while (front != rear)
   {
      k = queue[++front];
      for (int j:graphAdjList[k]){
         if (isVisited[j] == 0){
            queue[++rear] = j;
            isVisited[j] = 1;
            parent[j] = k;
         }
      }
   }
   for (k = 0; k < graphSize; k++)
      printPath(parent, initial, k);
}
int main(){
   vector<vector<int> > graphAdjList;
   graphAdjList.push_back({1, 3});
   graphAdjList.push_back({0, 2});
   graphAdjList.push_back({1});
   graphAdjList.push_back({4});
   graphAdjList.push_back({0});
   int graphSize = graphAdjList.size();
   int initial = 0;
   cout<<"The Path from vertex '0' to all other vertex in the graph is : \n";
   findPathBFS(graphAdjList, initial, graphSize);
}

出力結果

The Path from vertex '0' to all other vertex in the graph is :
0
1 <= 0
2 <= 1 <= 0
3 <= 0
4 <= 3 <= 0

このプログラムでは、findPathBFS関数がBFSを実行しながらparent配列を構築し、printPath関数が親を辿ることで各頂点への経路を出力しています。始点自身の出力は「0」のみとなり、その他の頂点については「<=」で結ばれた経路が表示されます。