用C语言实现判断DFS环路代码

在C语言中，使用DFS（深度优先搜索）检测环路需要一些额外的数据结构来跟踪路径以及访问状态。这里是一个简单的例子，利用栈和布尔数组来实现：

#include <stdbool.h>
#include <stdio.h>

bool visited[1000]; // 假设我们有最多1000个节点
stack_t nodes; // 自定义栈结构

// 假设有getNeighbors()函数获取给定节点的所有邻居
void dfs(int node) {
    visited[node] = true;
    push(nodes, node);

    for (int neighbor : getNeighbors(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor);
        } else if (visited[neighbor] && top(nodes) != neighbor) { // 遇到环
            printf("Found cycle starting from %d\n", top(nodes));
            return;
        }
    }

    pop(nodes); // 出栈，继续下一个节点
}

bool hasCycleDFS(int start) {
    visited[start] = true;
    push(nodes, start);
    dfs(start);
    return isEmpty(nodes); // 如果栈空，说明没有环
}

int main() {
    int start_node = ...; // 从哪个节点开始dfs
    if (hasCycleDFS(start_node)) {
        printf("No cycle detected.\n");
    } else {
        printf("A cycle exists!\n");
    }
    return 0;
}

在这个代码中，`visited[]`数组记录了节点是否已经被访问过，`nodes`栈用于存储节点及其遍历顺序。`dfs()`函数递归地遍历所有节点，如果遇到未访问过的节点就继续探索，如果遇到已访问过的节点则检查是否存在环。如果有环，则会打印环路起点，并结束搜索。`hasCycleDFS()`函数则是入口点，它首先初始化访问数组，然后调用`dfs()`并检查最后是否有剩余的节点。