如何在JavaScript中对二维数组的关联整数进行连通分组

给定一个由三元组组成的二维数组，需要将所有通过三元组关联的整数归为同一数组，最终得到若干个互不相交的整数数组。

输入示例：

[[2,3,9], [1,4,7], [3,6,9], [1,7,5], [7,5,8], [9,6,10], [3,6,10], [1,8,5]]

输出示例：

[[2,3,6,9,10],[1,4,5,7,8]]

这个问题本质是寻找连通分量：每个三元组内的整数属于同一个连通集合，所有通过三元组间接关联的整数也需要归为一组。最适合的解决方法是使用**并查集（Union-Find）**数据结构，它能高效处理元素的合并与集合查找操作。

代码实现 #

// 并查集实现，带路径压缩优化
class UnionFind {
  constructor() {
    this.parent = new Map();
  }

  find(x) {
    if (!this.parent.has(x)) this.parent.set(x, x);
    if (this.parent.get(x) !== x) {
      this.parent.set(x, this.find(this.parent.get(x)));
    }
    return this.parent.get(x);
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) this.parent.set(rootY, rootX);
  }
}

function groupConnectedNumbers(triangles) {
  const uf = new UnionFind();

  // 合并每个三元组内的所有元素
  triangles.forEach(tri => {
    uf.union(tri[0], tri[1]);
    uf.union(tri[1], tri[2]);
  });

  // 按根节点分组
  const groups = new Map();
  triangles.flat().forEach(num => {
    const root = uf.find(num);
    if (!groups.has(root)) groups.set(root, new Set());
    groups.get(root).add(num);
  });

  // 转换为目标格式的数组
  return Array.from(groups.values()).map(set => Array.from(set));
}

// 测试
const input = [[2,3,9], [1,4,7], [3,6,9], [1,7,5], [7,5,8], [9,6,10], [3,6,10], [1,8,5]];
console.log(groupConnectedNumbers(input));

代码说明 #

1. UnionFind类：提供find（查找元素根节点，带路径压缩优化）和union（合并两个元素所在集合）方法，确保集合操作的高效性。
2. groupConnectedNumbers函数：
   • 遍历所有三元组，将每个三元组内的三个元素合并到同一集合；
   • 收集所有出现过的整数，按其根节点分组，用Set自动去重；
   • 将每个分组的Set转换为数组，得到最终的连通分量结果。

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