节点的有效分组，可以达到彼此

我有一些图形数据，其中，节点之间的边缘是此形式：节点的有效分组，可以达到彼此

var edges = [ 
    ["A","B"], ["B","C"], ["B","D"], ["E","F"], ["E","G"] 
];

什么是最有效的（运行时间）的方式来组的节点那可以达到对方？在我的情况：

[["A","B","C","D"],["E","F","G"]]

我要寻找一个在纯JavaScript的解决方案，或者可能使用d3.js，underscore.js或jQuery的。伪代码也蛮好:)

UPDATE：因为有人提出这是this question重复，我将解释什么，我用这个了。

我有一些二维点（可能少于500），我想分组彼此接近的点。首先我做delaunay triangulation我得到一个平面图，我加上euclidean distance作为权重的边缘和使用Kruskal's algorithm作出minimum spanning tree（MST）。我从MST中删除要长的所有边。现在我最终得到了一些我想要处理和查找集群的边（如上所述）。当我拥有这些簇时，我会使它们的凸包可视化。

所以它是一个无向图。边缘告诉我的唯一事情是，它连接的两个顶点将位于同一个群集中。

即使点数可能很低，运行时间也很重要，因为这将在每个鼠标移动时计算。

SOLUTION：感谢您的建议。为了完整起见，这里是我想出了解决方案：

// Make a cluster for each vertex 
var clusters = _.map(vertices, function(node) { return [node]; }); 

while(edges.length > 0) { 

    var edge = edges.pop(); 
    var vertexA = edge[0], 
     vertexB = edge[1]; 

    var cA = _.filter(clusters, function(cluster) { 
     return _.contains(cluster, vertexA); 
    }); 

    var cB = _.filter(clusters, function(cluster) { 
     return _.contains(cluster, vertexB); 
    }); 

    if(_.union(_.difference(cA,cB) , _.difference(cB,cA)).length > 0) { 
     clusters = _.without(clusters, cA[0], cB[0]); 
     clusters.push(_.union(cA[0], cB[0])); 
    } 
} 

return clusters;

来源

2013-03-15 swenedo

它不是重复的。我想查找所有可以互相访问的节点“群集”。 – swenedo 2013-03-15 08:35:55

看看http://en.wikipedia.org/wiki/Disjoint-set_data_structure – MBo 2013-03-15 10:24:05

这里是我会做什么：

使节点的列表。将每个标记为未访问（白色）
从第一个节点开始标记为灰色。做一个breadth-first或depth first search只处理白色节点。当您与父母结束时，将其标记为黑色。
列表中的所有黑色节点都已连接。您可以从您在（1）中创建的列表中删除它们，并再次执行此操作以查找下一组连接节点。

来源

2013-03-15 00:49:21 angelatlarge

这是一个有向图吗？或无向图？

如果它的无向图，可以使用bfs/dfs。

浏览未访问的顶点列表。
从具有边缘而另一个顶点尚未访问的顶点开始。做bfs/dfs。跟踪在当前遍历中访问的节点
对您在当前遍历中访问的节点进行分组。
转至1。

复杂性与BFS/DFS相同。

来源

2013-03-15 01:27:51

节点的有效分组，可以达到彼此

回答

相关问题