1

我有一些图形数据，节点之间的边在这种形式上：

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。伪代码也很好:)

更新：因为有些人提出这是这个问题的副本，所以我将解释我使用它的目的。

我有许多 2D 点（可能少于 500 个），我想对彼此靠近的点进行分组。首先，我在得到一个平面图的地方进行delaunay 三角剖分，我将欧几里德距离添加为边上的权重，并使用Kruskal 算法制作最小生成树(MST)。我从 MST 中删除了所有过长的边。现在我最终得到了一些我想要处理并找到集群的边（如上所述）。当我有集群时，我会制作它们的凸包来可视化它。

所以它是一个无向图。边缘唯一告诉我的是，它连接的两个顶点将在同一个簇中。

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

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

// 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;
4

2 回答 2

0

这是我要做的：

  1. 制作节点列表。将每个标记为未访问（白色）
  2. 从第一个节点开始将其标记为灰色。仅处理白色节点进行广度优先或深度优先搜索。当您与父母结束时，将其标记为黑色。
  3. 列表中的所有黑色节点都已连接。您可以将它们从您在 (1) 中创建的列表中删除，然后再次执行此操作以查找下一组连接的节点。
于 2013-03-15T00:49:21.017 回答
0

这是有向图吗？还是无向图？

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

  1. 遍历未访问的顶点列表。
  2. 从一个顶点开始，该顶点有一条边，而另一个顶点尚未访问。做 bfs/dfs。跟踪当前遍历中访问的节点
  3. 对当前遍历中访问的节点进行分组。
  4. 转到 1。

复杂性将与 BFS/DFS 相同。

于 2013-03-15T01:27:51.490 回答