如何实现有向图的环数量统计：基于DFS与图着色算法的实现调试

核心问题说明 #

你提供的两套代码都是有向图环存在性检测逻辑，无法直接用于计数，核心问题有两个：

• 逻辑只要检测到任意环就会立即终止遍历返回结果，不会继续统计其余环
• 全局标记节点已访问的逻辑，会跳过包含公共节点/边的其他环，导致漏算

调整后的实现方案 #

我们基于DFS回溯思路修改，检测到环时仅触发计数不终止遍历，回溯时恢复递归栈状态保证所有路径都能被遍历，调整后的可运行代码如下：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Graph 
{   
    static int cycleCount = 0;
    private final int nodeNum;
    private final List<List<Integer>> adj;

    public Graph(int nodeNum)
    {
        this.nodeNum = nodeNum;
        adj = new ArrayList<>(nodeNum);
        
        for (int i = 0; i < nodeNum; i++)
            adj.add(new LinkedList<>());
    }
    
    private void dfs(int current, boolean[] visited, boolean[] inRecStack)
    {
        // 检测到环，计数器+1
        if (inRecStack[current]) {
            cycleCount++;
            return;
        }
        // 当前节点已全量遍历完成，跳过
        if (visited[current]) {
            return;
        }

        visited[current] = true;
        inRecStack[current] = true;
        
        // 遍历所有邻接节点
        for (Integer next : adj.get(current)) {
            dfs(next, visited, inRecStack);
        }
        // 回溯恢复状态
        inRecStack[current] = false;
    }

    public void addEdge(int source, int dest) {
        adj.get(source).add(dest);
    }
    
    public int countCycles()
    {
        cycleCount = 0;
        boolean[] visited = new boolean[nodeNum];
        boolean[] inRecStack = new boolean[nodeNum];
        
        for (int i = 0; i < nodeNum; i++) {
            dfs(i, visited, inRecStack);
            // 每轮遍历完重置访问标记，统计所有起点的环
            for (int j = 0; j < nodeNum; j++) visited[j] = false;
        }
        return cycleCount;
    }
    
    public static void main(String[] args)
    {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);
        
        System.out.println("有向图中环的总数为：" + graph.countCycles());
    }
}

计数规则说明 #

上述代码默认统计所有简单环的不同遍历序列（如环0→1→2→0和1→2→0→1会各算一次），如果你需要统计不重复的简单环（同个环的不同旋转/遍历顺序仅算一次），可以在计数前增加判断：仅当触发环的节点是当前递归栈中编号最小的节点时，才执行计数，即可实现去重。
你给出的示例图共有3个不重复的简单环：0→2→0、0→1→2→0、3→3，去重后输出结果为3。

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