c语言如何判断图是否有环

在C语言中，判断无向图是否存在环（也称为环路）通常使用深度优先搜索（Depth-First Search, DFS）或广度优先搜索（Breadth-First Search, BFS）。这里我将简述DFS方法：

**使用深度优先搜索（DFS）判断环：**
1. **邻接表表示法：**
- 对每个未访问过的节点进行递归探索。
- 使用一个数组或链表标记已访问的节点，避免重复访问。
- 如果在遍历过程中发现一个节点已经被标记为已访问（并且它不是当前节点），则说明存在环。
- 如果对所有节点都完成了递归探索，且没有发现环，那么可以确定图无环。

void dfs(int node, int visited[], bool graph[]) {
    visited[node] = 1; // 标记为已访问
    for (int i = 0; i < num_nodes; i++) {
        if (graph[node][i] && !visited[i]) { // 遍历邻居
            if (dfs(i, visited, graph)) return true; // 如果找到环，返回true
        } else if (graph[node][i] && visited[i] == 1) { // 如果邻居已经访问过且有边相连
            return true;
        }
    }
    visited[node] = 0; // 搜索结束，恢复节点状态
    return false;
}

bool hasCycle(int graph[]) {
    int visited[num_nodes];
    for (int i = 0; i < num_nodes; i++) {
        if (!visited[i] && dfs(i, visited, graph)) {
            return true;
        }
    }
    return false; // 图中无环
}

**使用BFS判断环：**
BFS同样可以检测环，通过检查是否所有的节点都能在固定时间内被访问到。如果发现某个节点两次出现在队列中，就表明存在环。

bool hasCycle_bfs(int graph[][num_nodes]) {
    queue<int> q;
    for (int i = 0; i < num_nodes; i++) {
        if (!visited[i])
            q.push(i);
        while (!q.empty()) {
            int top = q.front();
            q.pop();
            visited[top] = 1;
            for (int j = 0; j < num_nodes; j++) {
                if (graph[top][j] && !visited[j]) {
                    q.push(j);
                }
            }
            if (q.size() > num_nodes) // 如果节点数超过节点总数，说明存在环
                return true;
        }
    }
    return false;
}