使用 BFS 在无向图中查找循环

Question

我想仅使用 BFS（不是 DFS）在无向图中找到第一个循环。所有资源都使用 DFS 解决了这个问题，但我必须使用 BFS 找到它。我怎样才能找到它？提前致谢！

Answer 1

您将在下面找到使用 BFS 遍历图并找到其环的代码。

#include <stdio.h>
#include <queue>
using namespace std;

int nodes, edges, src;
int graph[100][100], color[100], prev[100];
const int WHITE = 0;
const int GRAY = 1;
const int BLACK = 2;
void print(int);

int main() {
    printf("Nodes, edges, source? ");
    scanf("%d %d %d ", &nodes, &edges, &src);
    for(int i = 1; i <= edges; i++) {
        printf("Edge %d: ", i);
        int x, y;
        scanf("%d %d", &x, &y);
        graph[x][y] = 1;
    }

    //run BFS
    queue<int> q;  //create a queue
    q.push(src);  //1. put root node on the queue
    do{
        int u = q.front();  //2. pull a node from the beginning of the queue
        q.pop();
        printf("%d ", u);  //print the node
        for(int i = 1; i <= nodes; i++) {  //4. get all the adjacent nodes
            if((graph[u][i] == 1)  //if an edge exists between these two nodes,
                && (color[i] == WHITE)) {  //and this adjacent node is still WHITE,
                q.push(i);  //4. push this node into the queue
                color[i] = GRAY;  //color this adjacent node with GRAY
            }
        }
        color[u] = BLACK;  //color the current node black to mark it as dequeued
    } while(!q.empty());  //5. if the queue is empty, then all the nodes havebeen visited

    //find and print cycle from source
    for(int i = 1; i <= nodes; i++) {
        if(graph[i][src] == 1) {
            print(i);
            printf("%d\n\n", src);
        }
    }

    return 0;
}

void print(int node) {
    if(node == 0)
        return;
    print(prev[node]);
    printf("%d -> ", node);
}

另外我推荐你看看这个brief and useful guide。

使用 BFS 在无向图中查找循环

Finding the cycle in an undirected graph using BFS

graph

breadth-first-search

cycle

undirected-graph