计算C ++中两个顶点之间的所有可能路径

• Z时代
• 2024-01-10
• 分类：综合

在本教程中，我们将讨论一个程序来查找两个顶点之间的路径数。

为此，我们将提供有向图。我们的任务是找到两个给定顶点之间可能的路径数。

示例

#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

以上是 计算C ++中两个顶点之间的所有可能路径 的全部内容， 来源链接： utcz.com/z/353456.html