C++에서 두 정점 사이의 가능한 모든 경로 계산

이 튜토리얼에서는 두 정점 사이의 경로 수를 찾는 프로그램에 대해 논의할 것입니다.

이를 위해 방향 그래프가 제공됩니다. 우리의 임무는 주어진 두 정점 사이에 가능한 경로의 수를 찾는 것입니다.

예시

#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