查找在两个给定节点之间是否存在路径的C ++程序
这是一个C++程序，用于查找2个给定节点之间是否存在路径
算法
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) If an adjacent has not been visited, then mark it visited and enqueue it. F) If this adjacent node is the destination node, then return true else continue to BFS. End
示例
#include <iostream>
#include <list>
using namespace std;
class G {
int n;
list<int> *adj;
public:
G(int n);
void addEd(int x, int w);
bool isReach(int s, int d);
};
G::G(int n) { //constructor
this->n = n;
adj = new list<int> [n];
}
void G::addEd(int x, int w) { //adding edge to the graph
adj[x].push_back(w); //ad w to x’s list
}
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;
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
热门推荐
10 朋友新年祝福语大全 简短
11 新年祝福语简短大方兔年
12 搬新家礼物祝福语简短
13 同学见面花束祝福语简短
14 五一假期祝福语幽默简短
15 离职欢送敬酒祝福语简短
16 对学弟的祝福语简短
17 考老师辞职祝福语简短
18 祝福语驱散霉运的话简短