C++에서 BFS를 사용하여 한 꼭짓점에서 나머지 지점까지의 경로 찾기

이 문제에서는 인접 목록으로 표시된 방향 그래프가 제공됩니다. 우리의 임무 BFS를 사용하여 한 정점에서 나머지 정점까지의 경로를 찾는 프로그램을 만드는 것 .

BFS (Breadth First Search)는 그래프를 더 넓은 방향으로 탐색하고 반복에서 막다른 골목이 발생할 때 다음 정점이 검색을 시작하도록 기억하기 위해 대기열을 사용하는 알고리즘입니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력 -

출력

S

A <=S

B <=A <=S

C <=S

D <=C <=S

해결 방법

이 문제를 해결하기 위해 그래프의 각 요소에 대해 BFS 검색 알고리즘을 수행합니다. 작업을 수행하기 위해 모든 노드에 대한 방문 플래그를 저장할 대기열을 생성합니다. 그런 다음 방문 배열을 사용하여 요소가 방문되었는지 여부를 확인합니다(방문을 나타내는 이진 값 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