我一直試圖讓這個程式保存在圖中形成回圈的頂點。但我是演算法的新手，在使用 BFS 時實作該功能似乎有點復雜。下面的代碼成功找到了回圈，但問題是如何修改此代碼以便我可以列印構成回圈的所有頂點？
#include <bits/stdc .h>
using namespace std;
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
bool isCyclicConntected(vector<int> adj[], int s,
int V, vector<bool>& visited)
{
// Set parent vertex for every vertex as -1.
vector<int> parent(V, -1);
// Create a queue for BFS
queue<int> q;
// Mark the current node as
// visited and enqueue it
visited[s] = true;
q.push(s);
while (!q.empty()) {
// Dequeue a vertex from queue and print it
int u = q.front();
q.pop();
// Get all adjacent vertices of the dequeued
// vertex u. If a adjacent has not been visited,
// then mark it visited and enqueue it. We also
// mark parent so that parent is not considered
// for cycle.
for (auto v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
parent[v] = u;
}
else if (parent[u] != v)
return true;
}
}
return false;
}
bool isCyclicDisconntected(vector<int> adj[], int V)
{
// Mark all the vertices as not visited
vector<bool> visited(V, false);
for (int i = 0; i < V; i )
if (!visited[i] && isCyclicConntected(adj, i,
V, visited))
return true;
return false;
}
// Driver program to test methods of graph class
int main()
{
int V = 4;
vector<int> adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 1, 2);
addEdge(adj, 2, 0);
addEdge(adj, 2, 3);
if (isCyclicDisconntected(adj, V))
cout << "Yes";
else
cout << "No";
return 0;
}
uj5u.com熱心網友回復：
您可以使用parent鏈接來重建回圈。
當兩條 BFS 路徑相遇時，這兩條路徑都可以通過parent串聯的鏈路重建，直到遇到一個公共節點。這兩條路徑的長度可以相等（回圈為偶數），也可以相差 1（回圈為奇數）。如果您parent以正確的方式通過相互鏈接進行串聯步行，您將始終遇到回圈的“頂部”。
當您使用雙端佇列時，回圈的節點將按自然順序列出：來自第一條路徑的節點可以推到前面，而另一條路徑的節點則推到后面。
您實際上并不需要單獨的visited向量：您也可以parent用于此目的。沒錯，您啟動 BFS 的第一個節點將不會被標記為已訪問，但無法將其作為回圈的終點進行訪問，因為 BFS 將通過該源節點的所有邊，并且不會允許使用任何這些邊來訪問源節點。因此parent，為此目的使用就足夠了。
這是您根據這些想法改編的代碼：
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
bool isCyclicConnectedHelper(vector<int> adj[], int s,
int V, vector<int>& parent,
deque<int> &cycle)
{
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : adj[u]) {
if (parent[v] == -1) { // Not yet visited
parent[v] = u;
q.push(v);
}
else if (parent[u] != v) { // Not the same edge
// Two paths meet: unwind both of them at both sides of a deque:
while (u != v) {
cycle.push_front(v);
v = parent[v];
if (u == v) break;
cycle.push_back(u);
u = parent[u];
}
cycle.push_front(u);
return true;
}
}
}
return false;
}
bool isCyclicConnected(vector<int> adj[], int V, deque<int> &cycle)
{
vector<int> parent(V, -1);
for (int i = 0; i < V; i ) {
if (parent[i] == -1) {
if (isCyclicConnectedHelper(adj, i, V, parent, cycle)) {
return true;
}
}
}
return false;
}
// Driver program to test methods of graph class
int main()
{
int V = 5;
vector<int> adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 1, 2);
addEdge(adj, 2, 4);
addEdge(adj, 3, 4);
addEdge(adj, 4, 1);
deque<int> cycle;
if (isCyclicConnected(adj, V, cycle)) {
cout << "The graph has a cycle:";
for (auto v : cycle) {
cout << " " << v;
}
} else {
cout << "The graph has no cycle.";
}
cout << "\n";
return 0;
}
注意：我建議定義adj為vector<vector<int>>并調整，addEdge以便根據需要擴展該向量。這樣你也擺脫了V.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/335900.html
上一篇：R-向前推進1直到達到另一個1
下一篇：如何散列哈希表中的鍵