-1

グリッドのようなグラフと[A、B、J、K]のようなノードのセットがあるとします。

Grid Graph:

A B C D
E F G H
I J K L

Note: diagonals not considered neighbours

これらのノードがすべて隣接しており、クラスターを形成しているかどうかを確認する最善の方法は何ですか?

上記の例では、[A,B] が隣接し、[J,K] が隣接していますが、全体として、セットはクラスターを形成していません。[A、B、F、J、K]を形成するために「F」がセットに追加された場合、それをクラスターと見なします。

更新: 2 つのノードが隣接しているかどうかをチェックする関数が既にあります boolean isAdjacent(Node a, Node b)。クラスターを確認するには、展開する必要があります。

4

1 に答える 1

2

元のグラフG = (V,E)をSET、目的のノードのセット ( SET <= V)とします。

G' = (V',E')とどこでV' = SETグラフを作成するE' = { (u,v) | (u,v) is in E and u,v is in SET }

グラフG'が接続されている場合は、すべての要素のクラスターがあります。
最大クラスターは、 の最大連結成分ですG'。

最大の連結成分を見つけることは、フラッド フィルのようなもので行うことができます。

(注、最初にフラッド フィルを制限付きで使用すると、G'実際に作成する必要なく のグラフ作成を調整できます)。

BFSを使用してクラスタを検索する疑似コード:

int maximalCluster(E,SET): //SET is the set of desired nodes, E is the edges in G.
    roots <- new map<node,interger>
    for each node n in SET: 
       //run a BFS for each root, 
       //and count the total number of elements reachable from it
       queue <- { n } 
       roots.put(n,1)
       while (queue is not empty):
           curr <- queue.takeFirst()
           for each edge (curr,u) in E:
              if (u is in SET):
                  SET.delete(u)
                  queue.add(u)
                  roots.put(roots.get(n) + 1)
    return max { roots.get(v) | for each  v in roots.keys }

上記の疑似コードは を生成しませんがG'、ノードが SET にあるエッジのみをチェックすることでシミュレートします。

于 2012-07-09T21:25:50.783 に答える