怎么用C语言判断一个图是否有环路

在C语言中，检测图（特别是有向图）是否存在环路可以使用深度优先搜索（Depth First Search, DFS）或者广度优先搜索（Breadth First Search, BFS）。这里我们以DFS为例讲解：

**使用深度优先搜索（DFS）判断环路：**
1. **邻接表表示图**：假设图已存储在一个邻接表中，每个节点包含一个指向其相邻节点的数组。

2. **递归实现DFS**：
a. 对于图中的每一个未访问节点v，从v开始进行递归遍历。
b. 记录当前节点v的前驱节点，通常称为`prev[v]`。
c. 如果发现当前节点v的某个邻居u已经被访问，并且`prev[u]`等于v（说明存在从u到v的一条路径），那么就找到了环路。
d. 否则，继续递归访问u的所有未访问邻居。
e. 遍历结束后，如果所有节点都被检查过且都没有找到环路，则说明图无环。

**示例代码片段（简化版）**：

void dfs(int node, int prev[], bool visited[], bool graph[]) {
    visited[node] = true;
    for (int i = 0; i < num_nodes; i++) {
        if (graph[node][i] && !visited[i]) {
            if (prev[i] == node) { // 找到了环路
                return;
            }
            dfs(i, prev, visited, graph);
        }
    }
}

// 主函数部分
bool hasCycle() {
    int prev[num_nodes]; // 存储前驱节点
    bool visited[num_nodes]; // 标记节点是否已访问
    // 初始化...
    for (int i = 0; i < num_nodes; ++i) {
        if (!visited[i]) {
            if (dfs(i, prev, visited, graph)) {
                return true; // 图有环
            }
        }
    }
    return false; // 图无环
}