C ++でBFSを使用して、1つの頂点から残りの頂点までのパスを見つける

この問題では、隣接リストとして表される有向グラフが与えられます。 私たちの仕事 BFSを使用して1つの頂点から残りの頂点までのパスを見つけるためのプログラムを作成する 。

BFS （幅優先探索）は、グラフを横方向に移動し、キューを使用して、反復で行き止まりが発生したときに、次の頂点を取得して検索を開始することを忘れないようにするアルゴリズムです。

問題を理解するために例を見てみましょう

入力 −

出力

S

A <=S

B <=A <=S

C <=S

D <=C <=S

ソリューションアプローチ

この問題を解決するために、グラフの各要素に対してBFS検索アルゴリズムを実行します。タスクを実行するために、任意のノードへの訪問のフラグを格納するキューを作成します。次に、visited配列を使用して、要素が訪問されているかどうかを確認します（バイナリ値0および1は訪問を示します）。

ここで、ソリューションの動作を理解するために、例を段階的に解決します。

ノードSから開始

• ノードAに直接アクセスします。

• ノードBに到達するには、最初にノードAにアクセスし、次にノードAを通過するノードBに到達します。

• ノードCに到達するには、SからCに直接アクセスします。

• ノードDに到達するには、最初にノードCにアクセスし、次にノードDにアクセスします。

例

ソリューションの動作を説明するプログラム

#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