无向图环检测C程序的DFS_cycle函数未调用提前终止问题求助

你现有代码存在3处核心逻辑错误，是导致程序提前终止、功能异常的直接原因：

• 未标记已访问节点，也未初始化访问标记数组：进入未访问节点时没有将graph->visited[vi]设为1，会导致递归时重复访问同一个节点，最终触发栈溢出让程序提前终止
• 环路判断逻辑错误：你当前在节点已访问分支只校验了邻接表第一个节点是否为父节点，完全没有匹配“遍历邻接节点时，发现邻接节点已访问且不是父节点则存在环”的正确逻辑
• 多连通分量场景兼容错误：外层循环没有重置访问标记数组，也不应该跳过邻接表为空的节点（不影响判断但逻辑不严谨）

修正后的代码 #

修正后DFS_cycle函数 #

int DFS_cycle(struct Graph *graph, int vi, int parent) {
    // 标记当前节点已访问
    graph->visited[vi] = 1;
    struct adjListNode *p = graph->array[vi].head;
    
    // 遍历当前节点所有邻接节点
    while (p != NULL) {
        int adj_v = p->dest;
        // 邻接节点未访问，递归遍历
        if (graph->visited[adj_v] == 0) {
            if (DFS_cycle(graph, adj_v, vi)) {
                return 1;
            }
        } 
        // 邻接节点已访问，且不是父节点，说明存在环
        else if (adj_v != parent) {
            return 1;
        }
        p = p->next;
    }
    return 0;
}

修正后cycle函数 #

void cycle(struct Graph *graph) {
    int has_cycle = 0;
    // 每次检测连通分量前先重置visited数组（要确保visited数组大小和顶点数V一致）
    memset(graph->visited, 0, sizeof(int) * graph->V);
    for (int i = 0; i < graph->V; i++) {
        // 只对未访问的节点跑DFS，避免重复遍历同一连通分量
        if (graph->visited[i] == 0) {
            if (DFS_cycle(graph, i, -1)) {
                printf("Graph has cycle, detected at vertex %d.\n", i);
                has_cycle = 1;
                break;
            }
        }
    }
    if (has_cycle == 0) {
        printf("Graph has no cycle\n");
    }
}

注意事项 #

• 要确保struct Graph中的visited数组已经分配了和顶点数V同等大小的内存空间
• 如果你的父节点标记用-1，要确保你的顶点编号是从0开始的正整数，避免和-1冲突
• 使用memset函数需要提前引入<string.h>头文件

内容的提问来源于stack exchange，提问作者Atulkumar Singh