无环无向图次节点索引求和：现有BFS解法出错，求正确方案

这是一道基于树结构的面试题：给定一个包含1~n编号节点的无环无向图（即树），定义树中最长路径为直径（max距离）。若节点存在于至少一条直径的路径上，则为主节点；其余为次节点，需要计算所有次节点的索引之和。

核心解决思路 #

树的直径是解题的关键，后续所有判断都围绕直径展开，步骤如下：

1. 确定树的直径端点：通过两次BFS/DFS找到直径的两个端点u和v：
   • 第一次从任意节点出发，找到距离它最远的节点u；
   • 第二次从u出发，找到距离u最远的节点v，此时u-v的路径即为一条直径，长度为max。
2. 识别所有主节点：计算每个节点到u的距离distU、到v的距离distV，若distU[x] + distV[x] == max，则节点x必然在某条直径上（属于主节点）。
3. 计算次节点索引和：遍历所有节点，将不在主节点集合中的节点索引相加。

Java实现代码 #

import java.util.*;

public class SecondaryNodeSum {
    public static void main(String[] args) {
        // 测试用例3验证
        int n = 5;
        int[] from = {1,1,2,2};
        int[] to = {2,3,4,5};
        System.out.println(calculateSecondarySum(n, from, to)); // 输出0，符合预期
    }

    public static int calculateSecondarySum(int n, int[] from, int[] to) {
        // 构建邻接表（节点编号1~n）
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 0; i < from.length; i++) {
            int u = from[i];
            int v = to[i];
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        // 第一次BFS找最远节点u
        int[] dist1 = bfs(1, adj, n);
        int u = 1;
        for (int i = 1; i <= n; i++) {
            if (dist1[i] > dist1[u]) {
                u = i;
            }
        }

        // 第二次BFS找最远节点v，同时记录u到所有节点的距离
        int[] distU = bfs(u, adj, n);
        int v = u;
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (distU[i] > maxDist) {
                maxDist = distU[i];
                v = i;
            }
        }

        // 第三次BFS记录v到所有节点的距离
        int[] distV = bfs(v, adj, n);

        // 筛选主节点
        Set<Integer> primaryNodes = new HashSet<>();
        for (int x = 1; x <= n; x++) {
            if (distU[x] + distV[x] == maxDist) {
                primaryNodes.add(x);
            }
        }

        // 计算次节点索引和
        int sum = 0;
        for (int x = 1; x <= n; x++) {
            if (!primaryNodes.contains(x)) {
                sum += x;
            }
        }
        return sum;
    }

    // BFS计算从start节点到所有节点的距离，返回距离数组（索引0未使用）
    private static int[] bfs(int start, List<List<Integer>> adj, int n) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        dist[start] = 0;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int neighbor : adj.get(curr)) {
                if (dist[neighbor] == -1) {
                    dist[neighbor] = dist[curr] + 1;
                    queue.add(neighbor);
                }
            }
        }
        return dist;
    }
}

测试用例验证 #

1. 测试用例1：n=4，from=[1,1,2]，to=[2,3,4]
   • 直径为3-1-2-4（长度3），所有节点的distU+distV均等于3，次节点和为0，符合预期。
2. 测试用例2：n=6，from=[1,1,1,2,3]，to=[2,3,4,5,6]
   • 直径为5-2-1-3-6（长度4），节点4的distU+distV=5≠4，属于次节点，和为4，符合预期。
3. 测试用例3：n=5，from=[1,1,2,2]，to=[2,3,4,5]
   • 直径长度为3（如3-1-2-4、3-1-2-5），所有节点的distU+distV均等于3，次节点和为0，符合预期。

原代码错误原因 #

原代码错误返回5，大概率是仅判断了某一条固定直径的路径，未考虑树中存在多条直径的情况，导致漏判了节点5这类属于其他直径的主节点。

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