查找在两个给定节点之间是否存在路径的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 婆婆66岁祝福语简短
13 今天孩子高考祝福语简短
14 送彩票生日祝福语简短
15 分别祝福语简短情话英文
16 画室揭牌仪式祝福语简短
17 女友妈妈生日祝福语简短
18 离别赠言离职祝福语简短