基于字符串与双精度数值关系构建树结构的Java实现问询

嘿，我看你正在基于现有的Relationships类构建树结构，这里有几个实用的方案，你可以根据自己的业务需求来挑选：

方案1：最小生成树（MST） #

如果你的需求是把所有居民用最短的总距离连接成一棵无环树，最小生成树是绝佳选择。它能保证任意两个节点之间有且仅有一条路径，且所有边的距离总和最小。

实现思路 #

1. 从Relationships中提取居民列表和距离映射
2. 用Prim算法（适合稠密图，你的距离矩阵刚好符合）逐步扩展树：从一个起始节点出发，每次选择距离当前树最近的未加入节点，更新节点间的最小距离关系
3. 根据最终的父节点映射构建树结构

代码示例 #

public class TreeBuilder {
    // 定义树节点
    public static class TreeNode {
        private String residentName;
        private List<TreeNode> children;
        private Double distanceToParent;

        public TreeNode(String residentName) {
            this.residentName = residentName;
            this.children = new ArrayList<>();
        }

        // Getter和Setter
        public String getResidentName() { return residentName; }
        public List<TreeNode> getChildren() { return children; }
        public Double getDistanceToParent() { return distanceToParent; }
        public void setDistanceToParent(Double distance) { this.distanceToParent = distance; }
        public void addChild(TreeNode child) { children.add(child); }
    }

    public static TreeNode buildMinimumSpanningTree(Relationships relationships) {
        List<String> residents = relationships.getResidents();
        Map<String, Map<String, Double>> distanceMap = relationships.getDistances();

        if (residents.isEmpty()) return null;

        Set<String> visited = new HashSet<>();
        Map<String, Double> minDistance = new HashMap<>();
        Map<String, String> parentMap = new HashMap<>();

        // 初始化起始节点（选第一个居民）
        String startNode = residents.get(0);
        visited.add(startNode);
        for (String resident : residents) {
            minDistance.put(resident, distanceMap.get(startNode).get(resident));
            parentMap.put(resident, startNode);
        }

        // 逐步扩展树
        while (visited.size() < residents.size()) {
            // 找到距离当前树最近的未访问节点
            String closestNode = null;
            double smallestDist = Double.MAX_VALUE;
            for (String resident : residents) {
                if (!visited.contains(resident) && minDistance.get(resident) < smallestDist) {
                    smallestDist = minDistance.get(resident);
                    closestNode = resident;
                }
            }
            if (closestNode == null) break; // 理论上不会触发，因为距离矩阵是连通的

            visited.add(closestNode);
            // 更新其他节点到树的最小距离
            for (String resident : residents) {
                if (!visited.contains(resident)) {
                    double newDist = distanceMap.get(closestNode).get(resident);
                    if (newDist < minDistance.get(resident)) {
                        minDistance.put(resident, newDist);
                        parentMap.put(resident, closestNode);
                    }
                }
            }
        }

        // 构建树节点映射
        Map<String, TreeNode> nodeMap = new HashMap<>();
        for (String resident : residents) {
            nodeMap.put(resident, new TreeNode(resident));
        }

        TreeNode root = nodeMap.get(startNode);
        for (String resident : residents) {
            if (!resident.equals(startNode)) {
                TreeNode parent = nodeMap.get(parentMap.get(resident));
                TreeNode child = nodeMap.get(resident);
                child.setDistanceToParent(minDistance.get(resident));
                parent.addChild(child);
            }
        }
        return root;
    }
}

方案2：层次聚类树（系统树图） #

如果你的需求是把距离相近的居民归为一类，构建层次化的分组树，比如用于人群聚类、关系分层，那凝聚式层次聚类是合适的选择。

实现思路 #

1. 每个居民初始为独立的簇
2. 用优先队列存储所有簇对的距离，每次取出距离最近的两个簇合并成新簇
3. 重复合并直到只剩一个簇，最终形成一棵层次化的树

代码示例（简化版） #

public class HierarchicalTreeBuilder {
    public static class TreeNode {
        private String nodeName;
        private List<TreeNode> children;
        private Double distanceToParent;

        public TreeNode(String nodeName) {
            this.nodeName = nodeName;
            this.children = new ArrayList<>();
        }

        // Getter和Setter
        public String getNodeName() { return nodeName; }
        public List<TreeNode> getChildren() { return children; }
        public Double getDistanceToParent() { return distanceToParent; }
        public void setDistanceToParent(Double distance) { this.distanceToParent = distance; }
        public void addChild(TreeNode child) { children.add(child); }
    }

    // 辅助类：存储簇信息
    private static class Cluster {
        TreeNode treeNode;
        Set<String> members;

        Cluster(String resident) {
            this.treeNode = new TreeNode(resident);
            this.members = new HashSet<>();
            members.add(resident);
        }

        Cluster(TreeNode mergedNode, Set<String> members) {
            this.treeNode = mergedNode;
            this.members = members;
        }
    }

    // 辅助类：存储簇对和距离
    private static class ClusterPair {
        String clusterKeyA;
        String clusterKeyB;
        double distance;

        ClusterPair(String a, String b, double distance) {
            this.clusterKeyA = a;
            this.clusterKeyB = b;
            this.distance = distance;
        }
    }

    public static TreeNode buildHierarchicalTree(Relationships relationships) {
        List<String> residents = relationships.getResidents();
        Map<String, Map<String, Double>> distanceMap = relationships.getDistances();

        if (residents.isEmpty()) return null;

        Map<String, Cluster> clusterMap = new HashMap<>();
        PriorityQueue<ClusterPair> queue = new PriorityQueue<>(Comparator.comparingDouble(p -> p.distance));

        // 初始化所有单节点簇
        for (String resident : residents) {
            clusterMap.put(resident, new Cluster(resident));
        }

        // 填充所有簇对的距离
        for (int i = 0; i < residents.size(); i++) {
            for (int j = i + 1; j < residents.size(); j++) {
                String a = residents.get(i);
                String b = residents.get(j);
                queue.add(new ClusterPair(a, b, distanceMap.get(a).get(b)));
            }
        }

        Set<String> mergedClusters = new HashSet<>();

        while (clusterMap.size() > 1 && !queue.isEmpty()) {
            ClusterPair pair = queue.poll();
            String keyA = pair.clusterKeyA;
            String keyB = pair.clusterKeyB;

            // 跳过已合并的簇
            if (mergedClusters.contains(keyA) || mergedClusters.contains(keyB)) continue;

            Cluster clusterA = clusterMap.get(keyA);
            Cluster clusterB = clusterMap.get(keyB);

            // 创建合并后的虚拟节点
            String mergedName = "Cluster[" + keyA + "+" + keyB + "]";
            TreeNode mergedNode = new TreeNode(mergedName);
            mergedNode.addChild(clusterA.treeNode);
            mergedNode.addChild(clusterB.treeNode);
            // 设置子节点到父节点的距离（取簇间距离的一半）
            clusterA.treeNode.setDistanceToParent(pair.distance / 2);
            clusterB.treeNode.setDistanceToParent(pair.distance / 2);

            // 合并成员集合
            Set<String> mergedMembers = new HashSet<>(clusterA.members);
            mergedMembers.addAll(clusterB.members);
            String mergedKey = keyA + "_" + keyB;
            clusterMap.put(mergedKey, new Cluster(mergedNode, mergedMembers));

            // 标记旧簇为已合并
            mergedClusters.add(keyA);
            mergedClusters.add(keyB);

            // 计算新簇与其他未合并簇的平均距离
            for (Map.Entry<String, Cluster> entry : clusterMap.entrySet()) {
                String otherKey = entry.getKey();
                if (!mergedClusters.contains(otherKey) && !otherKey.equals(mergedKey)) {
                    Cluster otherCluster = entry.getValue();
                    double totalDist = 0;
                    int count = 0;
                    for (String memberA : mergedMembers) {
                        for (String memberB : otherCluster.members) {
                            totalDist += distanceMap.get(memberA).get(memberB);
                            count++;
                        }
                    }
                    double avgDist = totalDist / count;
                    queue.add(new ClusterPair(mergedKey, otherKey, avgDist));
                }
            }
        }

        return clusterMap.values().iterator().next().treeNode;
    }
}

方案3：最短路径根节点树 #

如果需要指定某个居民作为树的根，展示所有其他居民到根节点的最短路径关系，比如构建以某人为中心的社交关系树，这个方案很合适。

实现思路 #

1. 用Dijkstra算法计算根节点到所有其他节点的最短路径
2. 根据路径中的父节点关系，构建以根为中心的树

代码示例 #

public class ShortestPathTreeBuilder {
    public static class TreeNode {
        private String residentName;
        private List<TreeNode> children;
        private Double distanceToParent;

        public TreeNode(String residentName) {
            this.residentName = residentName;
            this.children = new ArrayList<>();
        }

        // Getter和Setter
        public String getResidentName() { return residentName; }
        public List<TreeNode> getChildren() { return children; }
        public Double getDistanceToParent() { return distanceToParent; }
        public void setDistanceToParent(Double distance) { this.distanceToParent = distance; }
        public void addChild(TreeNode child) { children.add(child); }
    }

    public static TreeNode buildShortestPathTree(Relationships relationships, String rootName) {
        List<String> residents = relationships.getResidents();
        Map<String, Map<String, Double>> distanceMap = relationships.getDistances();

        if (!residents.contains(rootName)) return null;

        Map<String, Double> shortestDist = new HashMap<>();
        Map<String, String> parentMap = new HashMap<>();
        Set<String> visited = new HashSet<>();

        // 初始化距离和父节点
        for (String resident : residents) {
            shortestDist.put(resident, Double.MAX_VALUE);
            parentMap.put(resident, null);
        }
        shortestDist.put(rootName, 0.0);

        // Dijkstra算法计算最短路径
        while (visited.size() < residents.size()) {
            String current = null;
            double minDist = Double.MAX_VALUE;
            for (String resident : residents) {
                if (!visited.contains(resident) && shortestDist.get(resident) < minDist) {
                    minDist = shortestDist.get(resident);
                    current = resident;
                }
            }
            if (current == null) break;

            visited.add(current);
            // 更新邻居节点的最短距离
            for (Map.Entry<String, Double> neighborEntry : distanceMap.get(current).entrySet()) {
                String neighbor = neighborEntry.getKey();
                double newDist = shortestDist.get(current) + neighborEntry.getValue();
                if (newDist < shortestDist.get(neighbor)) {
                    shortestDist.put(neighbor, newDist);
                    parentMap.put(neighbor, current);
                }
            }
        }

        // 构建树
        Map<String, TreeNode> nodeMap = new HashMap<>();
        for (String resident : residents) {
            nodeMap.put(resident, new TreeNode(resident));
        }

        TreeNode root = nodeMap.get(rootName);
        for (String resident : residents) {
            if (!resident.equals(rootName)) {
                String parentName = parentMap.get(resident);
                if (parentName != null) {
                    TreeNode parent = nodeMap.get(parentName);
                    TreeNode child = nodeMap.get(resident);
                    child.setDistanceToParent(shortestDist.get(resident) - shortestDist.get(parentName));
                    parent.addChild(child);
                }
            }
        }
        return root;
    }
}

方案选择建议 #

• 最小生成树：适合需要连通所有节点且总距离最小的场景，比如规划路线、网络拓扑
• 层次聚类树：适合需要分层分组的场景，比如用户画像聚类、关系层级划分
• 最短路径树：适合以特定节点为中心，展示最短路径关系的场景，比如社交网络中心节点分析

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