每日算法 — 使用java实现树的直径：BFS两次遍历与树形DP最优解

算法背景

在无向树中，直径是指树中任意两点之间最长路径的边数（或边权和）。树的直径问题在计算机网络路由优化、聚类分析和游戏地图设计等领域有广泛应用。计算树直径的经典方法有两种：BFS两次遍历法和树形动态规划法。

核心思路

BFS两次遍历法基于一个重要性质：从树中任意一点出发进行BFS/DFS，找到的最远点一定是直径的某个端点。再从该端点出发进行一次BFS/DFS，找到的最远距离即为树的直径。

树形DP法则是对每个节点，维护经过该节点的最长路径（即以该节点为根的子树中的最长链），通过递归后序遍历计算。

Java实现

import java.util.*;

/**
 * 树的直径计算
 * 提供BFS两次遍历法和树形DP法两种实现
 */
public class TreeDiameter {

    // 邻接表表示树，存储(邻居, 边权)
    private List<int[]>[] graph;
    private int n;

    public TreeDiameter(int n) {
        this.n = n;
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    /**
     * 添加无向边
     */
    public void addEdge(int u, int v, int w) {
        graph[u].add(new int[]{v, w});
        graph[v].add(new int[]{u, w});
    }

    /**
     * BFS两次遍历法求直径
     * 时间复杂度：O(n)
     */
    public int bfsMethod() {
        // 第一次BFS：从任意点0出发，找到最远点
        int[] first = bfs(0);
        int farNode = first[0];

        // 第二次BFS：从最远点出发，其最远距离即为直径
        int[] second = bfs(farNode);
        return second[1]; // 返回最远距离
    }

    /**
     * 从start出发进行BFS，返回[最远节点, 最远距离]
     */
    private int[] bfs(int start) {
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[start] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);

        int farNode = start;
        int maxDist = 0;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int[] edge : graph[u]) {
                int v = edge[0], w = edge[1];
                if (dist[v] == -1) {
                    dist[v] = dist[u] + w;
                    queue.offer(v);
                    if (dist[v] > maxDist) {
                        maxDist = dist[v];
                        farNode = v;
                    }
                }
            }
        }
        return new int[]{farNode, maxDist};
    }

    // 树形DP相关变量
    private int diameter;

    /**
     * 树形DP法求直径
     * 时间复杂度：O(n)
     */
    public int treeDPMethod() {
        diameter = 0;
        dfs(0, -1);
        return diameter;
    }

    /**
     * DFS返回以u为根的子树中，u到叶子节点的最大距离
     */
    private int dfs(int u, int parent) {
        int max1 = 0, max2 = 0; // 最大和次大子树深度

        for (int[] edge : graph[u]) {
            int v = edge[0], w = edge[1];
            if (v == parent) continue;

            int childDepth = dfs(v, u) + w;

            // 更新最大和次大值
            if (childDepth > max1) {
                max2 = max1;
                max1 = childDepth;
            } else if (childDepth > max2) {
                max2 = childDepth;
            }
        }

        // 经过u的最长路径 = 最大深度 + 次大深度
        diameter = Math.max(diameter, max1 + max2);
        return max1;
    }

    /**
     * 主函数：测试与演示
     */
    public static void main(String[] args) {
        // 构建示例树
        //       0
        //      /|\
        //     1 2 3
        //    /     \
        //   4       5
        TreeDiameter tree = new TreeDiameter(6);
        tree.addEdge(0, 1, 1);
        tree.addEdge(0, 2, 1);
        tree.addEdge(0, 3, 1);
        tree.addEdge(1, 4, 1);
        tree.addEdge(3, 5, 1);

        System.out.println("BFS两次遍历法求得直径：" + tree.bfsMethod());
        System.out.println("树形DP法求得直径：" + tree.treeDPMethod());

        // 加权树测试
        TreeDiameter weightedTree = new TreeDiameter(5);
        weightedTree.addEdge(0, 1, 3);
        weightedTree.addEdge(1, 2, 4);
        weightedTree.addEdge(1, 3, 2);
        weightedTree.addEdge(2, 4, 5);

        System.out.println("\n加权树BFS法直径：" + weightedTree.bfsMethod());
        System.out.println("加权树DP法直径：" + weightedTree.treeDPMethod());
    }
}

复杂度分析

两种方法都是线性时间复杂度。BFS法直观易懂，而树形DP法更容易扩展到求”树中第k长路径”、”直径必经点”等变体问题。

应用场景

• 网络路由：寻找网络中延迟最大的路径以优化拓扑结构
• 地图设计：游戏中确定地图的最长通行距离
• 聚类分析：树状聚类结果中直径反映类内最大差异

总结

本文介绍了计算树直径的两种经典算法：BFS两次遍历法和树形DP法。BFS法利用”最远点必为直径端点”的性质，而DP法则通过后序遍历统计子树深度。两种方法时间复杂度均为O(n)，读者可根据具体场景选择合适方案。