In tất cả các đường dẫn từ một nguồn nhất định đến đích bằng BFS trong C ++

Trong bài toán này, chúng ta được cung cấp một biểu đồ có hướng và chúng ta phải in tất cả các đường dẫn từ nguồn đến đích của biểu đồ bằng cách sử dụng Breadth first Search (BFS).

Biểu đồ có hướng là một đồ thị có các cạnh hướng từ đỉnh a đến b.

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

Nguồn =K đích =P

Đầu ra

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

Ở đây, chúng tôi đã tìm thấy các đường dẫn từ K đến P. Chúng tôi đã đi qua các đường dẫn và in tất cả các đường đi từ K hướng chúng ta đến P.

Để in tất cả các đường dẫn từ nguồn đến đích, chúng tôi sẽ phải duyệt qua biểu đồ và lưu trữ các đường dẫn, sau đó in các đường dẫn hợp lệ.

Trong trường hợp sử dụng DFS, quá trình này dễ dàng nhưng trong trường hợp này, nó hơi khó thực hiện.

Để giải quyết vấn đề này, chúng ta sẽ cần một hàng đợi lưu trữ các đường dẫn. Bắt đầu từ nút nguồn, chúng ta sẽ bắt đầu duyệt qua mảng bằng BFS. đi ngang qua

cây và sau đó kiểm tra trong hàng đợi. Nếu đạt đến đỉnh đích thì hãy in các phần tử của hàng đợi, nếu không hãy bỏ qua nó.

Ví dụ

Chương trình dưới đây sẽ giúp giải pháp rõ ràng hơn -

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

Đầu ra

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