-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] 是相邻的，但是作为一个整体，这个集合并没有形成一个簇。如果将“F”添加到集合中以形成 [A,B,F,J,K]，那么我会认为它是一个集群。

更新：我已经有一个函数来检查两个节点是否相邻 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'。

找到最大连通分量可以通过Flood fill之类的方法来完成。

（注意，首先使用带有限制的洪水填充，可以调整图的创建，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 回答