无向图最长环问题代码优化：解决大图内存溢出难题

问题描述 #

现有代码能处理小规模无向图，但面对61个顶点、1741条边的大规模图时，因用字符串存储路径导致内存占用过高，出现堆溢出，需要优化方案找出图的最长环长度。

现有代码 #

class j20016 {
    public static void main(String[] args) {
        new j20016();
    }

    j20016() {
        // read();
        test();
        for(int i = 0; i < N; i++)
        {
            solve(i, 0, "");
        }
        System.out.println(ans);
        System.out.print(times);
    }

    void solve(int curNode, int len, String path) {
        times++;
        if(len == N-1) return;

        if(path.contains(String.valueOf(curNode)))
        {
            ans = Math.max(ans, len);
            return;
        }

        for (int i = 0; i < N; i++)
        {
            if(arr[curNode][i] == 1)
            {
                solve(i, len+1, path+ (i - 1));
            }
        }
    }

    void read()
    {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N][N];
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            arr[a-1][b-1] = 1;
            arr[b-1][a-1] = 1;
        }
    }
    void test()
    {
        String test =
                "6 10\n" +
                "1 2\n" +
                "1 3\n" +
                "1 5\n" +
                "2 3\n" +
                "2 5\n" +
                "2 6\n" +
                "3 4\n" +
                "3 5\n" +
                "3 6\n" +
                "4 6";
        Scanner sc = new Scanner(test);
        N = sc.nextInt();
        arr = new int[N][N];
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            arr[a-1][b-1] = 1;
            arr[b-1][a-1] = 1;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }

    }

    int[][] arr;
    int N; // 节点数
    int ans = 0;
    int times = 0;
}

测试数据 #

6 10  // 6为节点数，10为后续输入的边数行数
1 2 // 节点1与节点2相连
1 3
1 5
2 3
2 5
2 6
3 4
3 5
3 6
4 6

优化方案与思路 #

核心问题分析 #

原代码的致命问题：

1. 路径存储效率极低：用字符串拼接记录路径，每次递归都会生成新字符串，内存占用呈指数级增长，且contains判断是O(n)时间复杂度，双重拖慢性能。
2. 无向图重复遍历：没有规避无向图中"走回头路"的情况（比如从A到B后直接回A），导致大量无效递归。
3. 环判断逻辑错误：仅判断当前节点在路径中就终止，但只有当当前节点是路径起点时，才形成有效环，否则只是路径中的分支节点。
4. 无剪枝逻辑：即使当前路径长度加上剩余未访问节点数都无法超过已找到的最长环，仍继续递归，浪费资源。

具体优化措施 #

1. 用布尔数组/BitSet替代字符串存访问状态
   用boolean[]或BitSet记录已访问节点，判断是否访问过是O(1)操作，内存占用极低（61个节点的布尔数组仅需约8字节），且递归时可通过回溯复用状态，避免内存爆炸。

2. 避免无向图回头路
   递归时记录上一个访问的节点，遍历邻居时跳过该节点，减少一半无效递归。

3. 修正环判断逻辑
   只有当当前节点是本次DFS的起点时，才判定为有效环，此时路径长度就是环的长度，更新最大值。

4. 剪枝优化

   • 若当前路径长度 + 剩余未访问节点数 <= 已找到的最长环长度，直接终止递归。
   • 按邻居节点的度数从高到低遍历，优先探索更可能形成长环的路径，更早找到长环以触发更多剪枝。

5. 图存储优化
   将邻接矩阵改为邻接表，遍历邻居时只需处理实际相连的节点，减少循环次数，提升遍历效率。

优化后代码示例 #

import java.util.*;

class LongestCycleInUndirectedGraph {
    private List<List<Integer>> adj;
    private int N;
    private int maxCycleLength;
    private boolean[] visitedGlobal; // 标记已作为起点遍历过的节点，避免重复计算

    public static void main(String[] args) {
        new LongestCycleInUndirectedGraph();
    }

    LongestCycleInUndirectedGraph() {
        test();
        maxCycleLength = 0;
        visitedGlobal = new boolean[N];

        for (int start = 0; start < N; start++) {
            if (!visitedGlobal[start]) {
                boolean[] visitedPath = new boolean[N];
                dfs(start, start, -1, 0, visitedPath);
                visitedGlobal[start] = true;
            }
        }

        System.out.println("最长环长度: " + maxCycleLength);
    }

    // current: 当前节点, start: 本次DFS的起点, prev: 上一个节点, length: 当前路径长度
    private void dfs(int current, int start, int prev, int length, boolean[] visitedPath) {
        visitedPath[current] = true;

        for (int neighbor : adj.get(current)) {
            if (neighbor == prev) {
                continue; // 跳过回头路
            }
            if (neighbor == start) {
                // 回到起点，形成有效环
                maxCycleLength = Math.max(maxCycleLength, length + 1);
                continue;
            }
            if (!visitedPath[neighbor]) {
                // 剪枝：当前路径+剩余节点数 <= 已找到的最长环，直接返回
                int remaining = N - (length + 1);
                if (length + 1 + remaining <= maxCycleLength) {
                    continue;
                }
                dfs(neighbor, start, current, length + 1, visitedPath);
            }
        }

        visitedPath[current] = false; // 回溯，恢复状态
    }

    void read() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        adj = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            adj.add(new ArrayList<>());
        }
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            adj.get(a).add(b);
            adj.get(b).add(a);
        }
    }

    void test() {
        String test = "6 10\n" +
                "1 2\n" +
                "1 3\n" +
                "1 5\n" +
                "2 3\n" +
                "2 5\n" +
                "2 6\n" +
                "3 4\n" +
                "3 5\n" +
                "3 6\n" +
                "4 6";
        Scanner sc = new Scanner(test);
        N = sc.nextInt();
        adj = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            adj.add(new ArrayList<>());
        }
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            adj.get(a).add(b);
            adj.get(b).add(a);
        }
    }
}

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