सी ++ में दो शिखरों के बीच सभी संभावित पथों की गणना करें

इस ट्यूटोरियल में, हम दो शीर्षों के बीच पथों की संख्या ज्ञात करने के लिए एक प्रोग्राम पर चर्चा करेंगे।

इसके लिए हमें एक निर्देशित ग्राफ प्रदान किया जाएगा। हमारा कार्य दो दिए गए शीर्षों के बीच संभावित पथों की संख्या ज्ञात करना है।

उदाहरण

#include<bits/stdc++.h>
using namespace std;
//constructing a directed graph
class Graph{
   int V;
   list<int> *adj;
   void countPathsUtil(int, int, bool [],int &);
   public:
      //constructor
      Graph(int V);
      void addEdge(int u, int v);
      int countPaths(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);
}
int Graph::countPaths(int s, int d){
   //marking all the vertices
   // as not visited
   bool *visited = new bool[V];
   memset(visited, false, sizeof(visited));
   int pathCount = 0;
   countPathsUtil(s, d, visited, pathCount);
   return pathCount;
}
void Graph::countPathsUtil(int u, int d, bool visited[],
int &pathCount){
   visited[u] = true;
   //if current vertex is same as destination,
   // then increment count
   if (u == d)
      pathCount++;
      //if current vertex is not destination
   else {
      list<int>::iterator i;
      for (i = adj[u].begin(); i != adj[u].end(); ++i)
         if (!visited[*i])
            countPathsUtil(*i, d, visited,pathCount);
   }
   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 << g.countPaths(s, d);
   return 0;
}

आउटपुट

3