資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究查詢兩個給定節點之間是否存在路徑的 C++ 程式
這是一個 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:
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];
//Mark all the vertices as unvisited.
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 a adjacent has not been visited,
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
更新於： 2019 年 7 月 30 日
250 次瀏覽
廣告