查找在两个给定节点之间是否存在路径的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 51祝福语毕业文案简短
16 养生祝福语女生短句简短
17 六一互换礼物祝福语简短
18 新进单位敬酒祝福语简短