Tìm đường dẫn từ một đỉnh đến phần còn lại bằng BFS trong C ++

Trong bài toán này, chúng ta đưa ra một đồ thị có hướng được biểu diễn dưới dạng danh sách kề. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm đường dẫn từ một đỉnh đến phần còn lại bằng cách sử dụng BFS .

BFS (Tìm kiếm đầu tiên theo chiều rộng) là một thuật toán duyệt qua đồ thị theo chuyển động theo chiều rộng và sử dụng một hàng đợi để ghi nhớ để có được đỉnh tiếp theo để bắt đầu tìm kiếm, khi một điểm cuối xảy ra trong bất kỳ lần lặp nào.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào -

Đầu ra

S

Đ <=S

B <=A <=S

C <=S

Đ <=C <=S

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng tôi sẽ thực hiện thuật toán tìm kiếm BFS trên mỗi phần tử của đồ thị. Để thực hiện nhiệm vụ, chúng tôi sẽ tạo một hàng đợi sẽ lưu trữ cờ cho các lượt truy cập vào bất kỳ nút nào. Sau đó, bằng cách sử dụng một mảng đã truy cập, chúng tôi sẽ kiểm tra xem phần tử có được truy cập hay không (các giá trị nhị phân 0 và 1 biểu thị lượt truy cập).

Bây giờ, chúng ta sẽ từng bước giải quyết ví dụ để hiểu hoạt động của giải pháp của chúng ta,

Bắt đầu từ nút S,

• Chúng tôi sẽ trực tiếp ghé thăm nút A.

• Để đến nút B, chúng ta sẽ truy cập nút A trước rồi đến nút B đi ngang qua nút A.

• Để đến nút C, chúng tôi sẽ trực tiếp đến C từ S.

• Để đến được nút D, chúng ta sẽ đến nút C trước rồi đến nút D.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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);
}

Đầu ra

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