C ++程序在图中找到两个节点之间的路径
在此程序中，我们可以通过在给定图上使用DFS来找出两个节点之间是否存在路径。
算法
Begin function isReach() is a recursive function to check whether d is reachable to s : A) 将所有顶点标记为未访问。 B) 将当前节点标记为已访问并使其入队，它将用于获取顶点的所有相邻顶点 C) Dequeue a vertex from queue and print it D) Get all adjacent vertices of the dequeued vertex s E) 如果尚未访问相邻对象，则将其标记为已访问并排队 F)如果此相邻节点是目标节点，则返回true，否则继续执行BFS- End
示例
#include <iostream>
#include <list>
using namespace std;
class G {
int n;
list<int> *adj;
public:
//功能声明
G(int n);
void addEd(int v, int u);
bool isReach(int s, int d);
};
G::G(int n) {
this->n = n;
adj = new list<int> [n];
}
void G::addEd(int v, int u) //add edges to the graph {
adj[v].push_back(u);
}
bool G::isReach(int s, int d) {
if (s == d)
return true;
//将所有顶点标记为未访问。
bool *visited = new bool[n];
for (int i = 0; i < n; i++)
visited[i] = false;
list<int> queue;
//将当前节点标记为已访问并使其入队，它将用于获取顶点的所有相邻顶点
visited[s] = true;
queue.push_back(s);
list<int>::iterator i;
while (!queue.empty()) {
s = queue.front();
queue.pop_front(); //Dequeue a vertex from queue and print it
//如果尚未访问相邻对象，则将其标记为已访问并排队
for (i = adj[s].begin(); i != adj[s].end(); ++i) {
if (*i == d)
return true;
//如果此相邻节点是目标节点，则返回true，否则继续执行BFS-
if (!visited[*i]) {
visited[*i] = true;
queue.push_back(*i);
}
}
}
return false;
}
int main() {
G g(4);
g.addEd(1, 3);
g.addEd(0, 1);
g.addEd(2, 3);
g.addEd(1, 0);
g.addEd(2, 1);
g.addEd(3, 1);
cout << "Enter the source and destination vertices: (0-3)";
int a, b;
cin >> a >> b;
if (g.isReach(a, b))
cout << "\nThere is a path from " << a << " to " << b;
else
cout << "\nThere is no path from " << a << " to " << b;
int t;
t = a;
a = b;
b = t;
if (g.isReach(a, b))
cout << "\nThere is a path from " << a << " to " << b;
else
cout << "\nThere is no path from " << a << " to " << b;
return 0;
}输出结果
Enter the source and destination vertices: (0-3) There is a path from 3 to 1 There is a path from 1 to 3