数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究在图中寻找两个结点之间路径的 C++ 程序
通过对给定图执行深度优先搜索，此程序可以找出两个节点之间是否存在路径。
算法
Begin function isReach() is a recursive function to check whether d is reachable to s : A) Mark all the vertices as unvisited. B) Mark the current node as visited and enqueue it and it will be used to get all adjacent vertices of a vertex 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:
//declaration of functions
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;
//Mark all the vertices as unvisited.
bool *visited = new bool[n];
for (int i = 0; i < n; i++)
visited[i] = false;
list<int> queue;
//Mark the current node as visited and enqueue it and it will be used to get all adjacent vertices of a vertex
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
//If an adjacent has not been visited, then mark it visited and enqueue it
for (i = adj[s].begin(); i != adj[s].end(); ++i) {
if (*i == d)
return true;
// If this adjacent node is the destination node, then return true else continue to 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
更新于: 2019-7-30
695 次浏览
广告