特定のソースから宛先までのすべてのパスをC++で出力します

この問題では、有向グラフが与えられ、グラフのソースから宛先までのすべてのパスを印刷する必要があります。

有向グラフ は、頂点aからbに向けられたエッジを持つグラフです。

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

ソース=K宛先=P

出力：

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

ここで、KからPへのパスを見つけました。パスをトラバースし、KからPに向かうすべてのパスを出力しました。

この問題を解決するために、深さ優先探索を使用してグラフをトラバースします。 トラバーサルテクニック。 ソースから開始 パス配列内の各頂点ストアをトラバースし、訪問済みとしてマークします（同じ頂点への複数の訪問を回避するため）。そして、宛先のときに、このパスを印刷します 頂点に到達しました。

ロジックを実装するプログラムを見てみましょう-

例

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

出力

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