節點的有效分組，可以達到彼此

我有一些圖形數據，其中，節點之間的邊緣是此形式：節點的有效分組，可以達到彼此

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

節點的有效分組，可以達到彼此

回答

相關問題