Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm số đường đi giữa hai đỉnh.
Đối với điều này, chúng tôi sẽ được cung cấp với một đồ thị có hướng. Nhiệm vụ của chúng ta là tìm số đường đi có thể giữa hai đỉnh đã cho.
Ví dụ
#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;
} Đầu ra
3