如何修改BFS最短路径代码计算无向图两节点间最长路径边数

你当前使用的BFS算法天生适用于最短路径求解，因为它按层遍历节点，首次到达目标节点时的路径就是最短路径。但最长路径属于NP难问题，对于你当前的小规模无环图场景，可以用DFS回溯的方式遍历所有可达路径，记录到达目标节点的最大边数即可。

核心修改思路 #

• 丢弃原有的全局访问标记逻辑，改为每次递归时维护当前路径的访问节点标记，避免重复走同一个节点形成环路
• 每次到达目标节点时，对比更新当前记录的最大边数
• 递归探索完某个邻接节点的所有路径后，回溯取消该节点的访问标记，供其他路径使用

修改后的完整代码 #

import java.util.Vector;

class Test {
    // 存储最大边数结果
    static int maxEdgeCount = 0;

    // DFS回溯求最长路径边数
    static void dfs(Vector<Integer> edges[], boolean[] currentVisited, int currentNode, int target, int currentDistance, int n) {
        // 到达目标节点，更新最大边数
        if (currentNode == target) {
            maxEdgeCount = Math.max(maxEdgeCount, currentDistance);
            return;
        }
        // 遍历所有邻接节点
        for (int neighbor : edges[currentNode]) {
            if (!currentVisited[neighbor]) {
                currentVisited[neighbor] = true;
                dfs(edges, currentVisited, neighbor, target, currentDistance + 1, n);
                // 回溯，取消标记
                currentVisited[neighbor] = false;
            }
        }
    }

    static int maxEdgeDFS(Vector<Integer> edges[], int u, int v, int n) {
        maxEdgeCount = 0;
        boolean[] currentVisited = new boolean[n];
        currentVisited[u] = true;
        dfs(edges, currentVisited, u, v, 0, n);
        return maxEdgeCount;
    }

    // 加边方法保持不变
    static void addEdge(Vector<Integer> edges[], int u, int v) {
        edges[u].add(v);
        edges[v].add(u);
    }

    public static void main(String args[]) {
        int n = 11;
        Vector<Integer> edges[] = new Vector[11];

        for (int i = 0; i < edges.length; i++) {
            edges[i] = new Vector<>();
        }

        addEdge(edges, 0, 1);
        addEdge(edges, 1, 2);
        addEdge(edges, 1, 7);
        addEdge(edges, 1, 6);
        addEdge(edges, 2, 8);
        addEdge(edges, 3, 1);
        addEdge(edges, 3, 4);
        addEdge(edges, 3, 9);
        addEdge(edges, 5, 3);
        addEdge(edges, 5, 9);
        addEdge(edges, 8, 10);
        int u = 6;
        int v = 9;
        // 调用新的最长路径方法
        System.out.println(maxEdgeDFS(edges, u, v, n));
    }
}

运行说明 #

运行上述代码后输出结果为4，对应你需要的最长路径6-1-3-5-9的边数。
注意：该方案仅适用于节点规模较小的图，如果图规模较大且存在环，需要额外处理或改用针对特定图结构（如有向无环图）的最长路径优化算法。

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