实现UPGMA算法时，适合采用何种数据结构？

嘿，我完全懂你的困扰——用std::vector<std::vector<int>>来实现UPGMA的聚类合并，确实会在嵌套聚类出现时卡壳，因为这个结构只能处理单层的元素集合，没法递归容纳已经是聚类的子集合。UPGMA本质是要构建一棵层次聚类树，所以我们需要能表达这种递归嵌套关系的数据结构，下面给你两个实用的方案：

方案1：自定义树节点结构体（最推荐） #

这是最贴合UPGMA算法逻辑的方式，因为每个聚类要么是叶子节点（对应你初始的整数标识），要么是内部节点（包含两个子聚类，还可以存储UPGMA需要的距离信息）。

首先定义树节点结构：

#include <memory>

struct TreeNode {
    // 叶子节点专属：存储你的整数标识（代表特定字符串）
    int leaf_id = -1;
    // 内部节点专属：两个子聚类节点
    std::unique_ptr<TreeNode> left_child;
    std::unique_ptr<TreeNode> right_child;
    // UPGMA需要：记录该聚类的距离值（可选但实用）
    double cluster_distance = 0.0;

    // 构造叶子节点
    TreeNode(int id) : leaf_id(id) {}
    // 构造内部节点（合并两个子聚类）
    TreeNode(std::unique_ptr<TreeNode> left, std::unique_ptr<TreeNode> right, double dist)
        : left_child(std::move(left)), right_child(std::move(right)), cluster_distance(dist) {}
};

接下来用一个向量维护当前活跃的聚类节点：

// 初始化所有叶子节点
std::vector<std::unique_ptr<TreeNode>> active_clusters;
active_clusters.emplace_back(std::make_unique<TreeNode>(0));
active_clusters.emplace_back(std::make_unique<TreeNode>(1));
active_clusters.emplace_back(std::make_unique<TreeNode>(2));
active_clusters.emplace_back(std::make_unique<TreeNode>(3));
active_clusters.emplace_back(std::make_unique<TreeNode>(4));
active_clusters.emplace_back(std::make_unique<TreeNode>(5));

合并操作示例（比如合并索引0和3的聚类）：

int x = 0;
int y = 3;
// 先计算UPGMA要求的聚类距离（这里用示例值，你需要替换成算法计算的结果）
double merge_distance = 1.0;

// 创建新的内部节点，把两个子节点移进去
auto merged_cluster = std::make_unique<TreeNode>(
    std::move(active_clusters[x]),
    std::move(active_clusters[y]),
    merge_distance
);

// 注意先删除索引大的元素，避免移位导致索引错误
active_clusters.erase(active_clusters.begin() + y);
active_clusters.erase(active_clusters.begin() + x);
// 添加新的合并聚类
active_clusters.push_back(std::move(merged_cluster));

这种方式的优势在于：

• 完全支持任意层级的嵌套聚类，完美匹配UPGMA的树状结构
• 方便后续的树遍历、距离计算、结果输出等扩展操作
• 代码逻辑清晰，每个节点的职责明确

方案2：用std::variant实现轻量递归结构（快速原型用） #

如果你不想写自定义结构体，C++17及以上的std::variant可以实现轻量的递归类型，让一个变量既可以是叶子整数，也可以是两个聚类的组合：

#include <variant>
#include <utility>

// 定义Cluster类型：要么是int（叶子），要么是两个Cluster的pair（合并聚类）
using Cluster = std::variant<int, std::pair<Cluster, Cluster>>;

初始化和合并操作示例：

std::vector<Cluster> active_clusters = {0, 1, 2, 3, 4, 5};

// 合并索引0和3的聚类
int x = 0;
int y = 3;
Cluster merged = std::make_pair(active_clusters[x], active_clusters[y]);
// 同样先删大索引
active_clusters.erase(active_clusters.begin() + y);
active_clusters.erase(active_clusters.begin() + x);
active_clusters.push_back(merged);

// 后续合并索引1和4的聚类（此时4是之前合并的嵌套聚类）
x = 1;
y = 3; // 因为删除后原索引4变成了3
merged = std::make_pair(active_clusters[x], active_clusters[y]);
active_clusters.erase(active_clusters.begin() + y);
active_clusters.erase(active_clusters.begin() + x);
active_clusters.push_back(merged);

这个方案的优点是代码简洁，不需要自定义类，但缺点是访问聚类内容时需要用std::visit来处理两种类型的情况，对于后续的算法扩展（比如计算距离、打印树结构）不如树节点方案直观。

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