数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究用 C++ 计算两个顶点之间所有可能的路径
在本教程中，我们将讨论如何查找两个顶点之间路径数量的程序。
为此，我们将提供一个有向图。我们的任务是找到两个给定顶点之间可能存在的路径数量。
示例
#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
更新于: 10-Feb-2020
315 次浏览
广告