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