计算C ++中两个顶点之间的所有可能路径
在本教程中，我们将讨论一个程序来查找两个顶点之间的路径数。
为此，我们将提供有向图。我们的任务是找到两个给定顶点之间可能的路径数。
示例
#include<bits/stdc++.h>
using namespace std;
//构造有向图
class Graph{
int V;
list<int> *adj;
void countPathsUtil(int, int, bool [],int &);
public:
//构造函数
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){
//标记所有顶点
//未被访问
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 (u == d)
pathCount++;
//如果当前顶点不是目标
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