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

Trong bài toán này, chúng tôi đưa ra một biểu đồ có hướng và chúng tôi phải in tất cả các đường dẫn từ nguồn đến đích của biểu đồ.

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.

Để giải quyết vấn đề này, chúng tôi sẽ duyệt qua biểu đồ bằng cách sử dụng tìm kiếm theo chiều sâu kỹ thuật đi ngang. Bắt đầu từ nguồn, chúng ta sẽ duyệt qua từng đỉnh lưu trữ trong mảng đường dẫn của chúng ta và đánh dấu nó là đã thăm (để tránh nhiều lần truy cập vào cùng một đỉnh). Và in đường dẫn này, khi điểm đến đạt đến đỉnh.

Hãy xem chương trình thực hiện logic -

Ví dụ

#include<iostream>
#include <list>
using namespace std;
class Graph {
   int V;
   list<int> *adj;
   void findNewPath(int , int , bool [], int [], int &);
   public:
   Graph(int V);
   void addEdge(int u, int v);
   void printPaths(int s, int d);
};
Graph::Graph(int V) {
   this->V = V;
   adj = new list<int>[V];
}
void Graph::addEdge(int u, int v) {
   adj[u].push_back(v);
}
void Graph::printPaths(int s, int d) {
   bool *visited = new bool[V];
   int *path = new int[V];
   int path_index = 0;
   for (int i = 0; i < V; i++)
   visited[i] = false;
   findNewPath(s, d, visited, path, path_index);
}
void Graph::findNewPath(int u, int d, bool visited[],
int path[], int &path_index) {
   visited[u] = true;
   path[path_index] = u;
   path_index++;
   if (u == d) {
      for (int i = 0; i<path_index; i++)
      cout<<path[i]<<" ";
      cout << endl;
   } else {
      list<int>::iterator i;
      for (i = adj[u].begin(); i != adj[u].end(); ++i)
         if (!visited[*i])
            findNewPath(*i, d, visited, path, path_index);
   }
   path_index--;
   visited[u] = false;
}
int main() {
   Graph g(4);
   g.addEdge(0, 1);
   g.addEdge(0, 2);
   g.addEdge(0, 3);
   g.addEdge(2, 0);
   g.addEdge(2, 1);
   g.addEdge(1, 3);
   int s = 2, d = 3;
   cout<<"Following are all different paths from source to destination : \n";
   g.printPaths(s, d);
   return 0;
}

Đầu ra

Following are all different paths from source to destination :
2 0 1 3
2 0 3
2 1 3