使用 BFS 查找循环并将其顶点保存在无向、未加权的图中

Question

我一直在尝试让这个程序保存图中构成循环的顶点。但我是算法方面的新手，在使用 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;
}

Answer 1

您可以使用 parent link 来重建循环。

当两条BFS路径相遇时，这两条路径都可以通过parent link串联重构，直到遇到公共节点。这两条路径的长度可以相等（周期为偶数），也可以相差 1（周期为奇数）。如果您以正确的方式通过相互 parent link 进行双人步行，您总会遇到循环的“顶部”。

使用双端队列时，循环的节点将按自然顺序排列：来自第一条路径的节点可以推到前面，而另一条路径的节点可以推到后面。

您实际上不需要单独的 visited 向量：您也可以使用 parent 来达到此目的。确实，您启动 BFS 的第一个节点将不会被标记为已访问，但是无法将其作为循环的终点进行访问，因为 BFS 将经过 all 来自该源节点的边缘，并且不允许使用任何这些边缘来访问源节点。因此使用 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.

使用 BFS 查找循环并将其顶点保存在无向、未加权的图中

Finding a cycle and saving its vertices in an undirected, unweighted graph using BFS

c++

algorithm

graph

breadth-first-search

graph-algorithm