Javascript 按交集对数组进行分组

Question

给定一个成对整数数组，我如何按交集分组。有没有人有一个简单的函数可以将我的输入转换为所需的输出？

输入

var in = ["0:3", "1:3", "4:5", "5:6", "6:8"]

期望的输出

[
    [0, 1, 3],
    [4, 5, 6, 8]
]

更新:

@apsiller 在评论中问我的问题比我最初发布的更清楚:

“将每个数字视为图中的一个节点，并将每个配对 x:y 视为节点 x 和 y 之间的边，使用定义的边找到可以移动到的数字集。也就是说，在图论术语中，在这样的图中找到不同的 connected components。

例如，没有办法从 4 到 0，所以他们在不同的组，但是有办法从 1 到 0(通过 3)，所以他们在同一个组。"

重申一下，所需的输出是基于潜在随机输入集的一组可横向节点。

Answer 1

谢谢大家。鉴于每个人的意见，我能够在这里找到一个类似的问题，这让我得到了答案。 Finding All Connected Components of an Undirected Graph

第一步是将我的输入更改为成对的组。

var input = [
    [0, 3],
    [1, 3],
    [4, 5],
    [5, 6],
    [6, 8]
]

下一步是使用所谓的广度优先搜索

function breadthFirstSearch(node, nodes, visited) {
    var queue = [];
    var group = [];
    var pair  = null;
    queue.push(node);
    while (queue.length > 0) {
        node = queue.shift();
        if (!visited[node]) {
            visited[node] = true;
            group.push(node);
            for (var i = 0, len = nodes.length; i < len; i++) {
                pair = nodes[i];
                if (pair[0] === node && !visited[pair[1]]) {
                    queue.push(pair[1]);
                } else if (pair[1] === node && !visited[pair[0]]) {
                    queue.push(pair[0]);
                }
            }
        }
    }
    return group;
};

---

function groupReachableVertices(input) {
    var groups  = [];
    var visited = {};
    for (var i = 0, len = input.length; i < len; i += 1) {
        var current_pair = input[i];
        var u = current_pair[0];
        var v = current_pair[1];
        var src = null;
        if (!visited[u]) {
            src = u;
        } else if (!visited[v]) {
            src = v;
        }
        if (src) {
            groups.push(breadthFirstSearch(src, input, visited));
        }
    }
    return groups;
};

---

把它们放在一起......

var output = groupReachableVertices(input);
[
    [0, 1, 3],
    [4, 5, 6, 8]
]