JavaScript实现有向边数组顶点按独立连通图分组的问题

需求说明 #

将任意长度的有向边数组中的顶点按连通性分组，存在关联的顶点归为同一分组，不关心分组内顶点的排序。

示例输入1 #

let pairs = [[9, 6], [10, 2], [2, 1], [7, 1], [5, 6], [1, 10], [8, 11], [10, 4], [9, 0], [12, 0], [3, 9], [0, 6]];

示例输出1 #

let output = [
    [0, 3, 5, 6, 9, 12],
    [1, 2, 4, 7, 10],
    [8, 11] 
];

原有代码问题 #

原有实现没有处理「后续边关联到两个独立分组需要合并」的场景，连通分量归属判断逻辑有缺陷，复杂输入下会出现分组拆分错误、顶点错误归类的问题。
比如输入如下测试用例时结果不符合预期：

复杂测试用例输入 #

let pairs = [[25, 15], [22, 6], [6, 15], [15, 9], [9, 6], [16, 9], [7, 29], [2, 5], [26, 24], [24, 29], [5, 24], [29, 5], [1, 18], [13, 12], [19, 30], [30, 18], [12, 30], [18, 12], [8, 20], [11, 3], [28, 23], [20, 3], [3, 23], [23, 20], [4, 10], [14, 27], [21, 17], [10, 17], [17, 27], [27, 10], [0, 31]];

该用例预期输出 #

output =   [
    [25, 15, 22, 6, 9, 16],
    [26, 24, 29, 5, 2, 7],
    [19, 30, 18, 12, 1, 13], 
    [28, 23, 3, 20, 8, 11],
    [21, 17, 10, 27, 4, 14], 
    [0, 31]
  ];

正确实现方案 #

使用并查集（Union-Find）数据结构实现，天然适配连通分量分组场景，逻辑清晰、处理效率高：

function groupConnectedVertices(pairs) {
    const parent = new Map();
    
    // 查找顶点根节点，带路径压缩优化
    function find(node) {
        if (!parent.has(node)) {
            parent.set(node, node);
        }
        if (parent.get(node) !== node) {
            parent.set(node, find(parent.get(node)));
        }
        return parent.get(node);
    }
    
    // 合并两个顶点的连通分量
    function union(node1, node2) {
        const root1 = find(node1);
        const root2 = find(node2);
        if (root1 !== root2) {
            parent.set(root2, root1);
        }
    }

    // 遍历所有边合并连通顶点
    for (const [u, v] of pairs) {
        union(u, v);
    }

    // 按根节点对顶点分组
    const groups = new Map();
    for (const node of parent.keys()) {
        const root = find(node);
        if (!groups.has(root)) {
            groups.set(root, []);
        }
        groups.get(root).push(node);
    }

    return Array.from(groups.values());
}

使用示例 #

// 测试示例1
const pairs1 = [[9, 6], [10, 2], [2, 1], [7, 1], [5, 6], [1, 10], [8, 11], [10, 4], [9, 0], [12, 0], [3, 9], [0, 6]];
console.log(groupConnectedVertices(pairs1));

// 测试复杂用例
const pairs2 = [[25, 15], [22, 6], [6, 15], [15, 9], [9, 6], [16, 9], [7, 29], [2, 5], [26, 24], [24, 29], [5, 24], [29, 5], [1, 18], [13, 12], [19, 30], [30, 18], [12, 30], [18, 12], [8, 20], [11, 3], [28, 23], [20, 3], [3, 23], [23, 20], [4, 10], [14, 27], [21, 17], [10, 17], [17, 27], [27, 10], [0, 31]];
console.log(groupConnectedVertices(pairs2));

输出结果完全符合预期。

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