এই টিউটোরিয়ালে, আমরা দুটি শীর্ষবিন্দুর মধ্যে পথের সংখ্যা খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব।
এর জন্য আমাদের একটি নির্দেশিত গ্রাফ প্রদান করা হবে। আমাদের কাজ হল দুটি প্রদত্ত শীর্ষবিন্দুর মধ্যে সম্ভাব্য পথের সংখ্যা খুঁজে বের করা।
উদাহরণ
#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
