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未満）、互いに近いポイントをグループ化したいと思います。まず、平面グラフを取得するドロネー三角形分割を行い、エッジの重みとしてユークリッド距離を追加し、クラスカルのアルゴリズムを使用して最小スパニングツリー（MST）を作成します。MSTから長すぎるすべてのエッジを削除します。これで、クラスターを処理して検索するためのいくつかのエッジ（上記のとおり）ができあがります。クラスターができたら、それらの凸包を作成して視覚化します。

つまり、無向グラフです。エッジが私に伝える唯一のことは、それが接続する2つの頂点が同じクラスター内にあるということです。

ポイント数が少ない場合でも、マウスを動かすたびに計算されるため、実行時間は重要です。

解決策：提案をありがとう。完全を期すために、私が思いついた解決策は次のとおりです。

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

これは有向グラフですか？または無向グラフ？

無向グラフの場合は、bfs/dfs を使用できます。

  1. 訪問されていない頂点のリストを調べます。
  2. エッジを持つ頂点と、まだ訪れていない他の頂点から開始します。bfs/dfs を実行します。現在のトラバーサルで訪問されているノードを追跡する
  3. 現在のトラバーサルで訪れたノードをグループ化します。
  4. 1に行きます。

複雑さは BFS/DFS と同じになります。

于 2013-03-15T01:27:51.490 に答える
0

これが私がすることです：

  1. ノードのリストを作成します。それぞれを未訪問としてマーク (白)
  2. 最初のノードから始めて、灰色でマークします。白いノードのみを処理する幅優先検索または深さ優先検索を実行します。親で終了するときは、黒としてマークします。
  3. リスト内のすべての黒いノードが接続されています。(1) で作成したリストからそれらを削除し、これをもう一度実行して、接続された次のノードのセットを見つけることができます。
于 2013-03-15T00:49:21.017 に答える