查找已连接节点的群集的算法

Question

我正在处理3d数据，并被提供了一个相互连接的顶点列表。数据格式如下：

faces = [
    (0, 1, 2),
    (1, 3, 2),
    (3, 5, 6),
    (5, 7, 4),
    (10, 11, 12),
    (11, 12, 13),
    (12, 13, 14)    
]

数组中的每一项都由一个三元组组成，其中每个位置上的数字表示相互连接的顶点的索引。我已经在图片中可视化了这个例子，以便更好地理解顶点是如何连接的。

我正在寻找一个简单的，易于实现的算法，它接受faces作为它的输入，并返回以下内容作为它的输出：

[
    [0, 1, 2, 3, 4, 5, 6, 7],
    [10, 11, 12, 13, 14]
]

​

​

Answer 1

您可以使用union-find

我将在这里添加它的一个简单版本

前面未测试的代码

using face = std::array<int, 3>;
std::vector<face>  faces = {
    {0, 1, 2},
    {1, 3, 2},
    {3, 5, 6},
    {5, 7, 4},
    {10, 11, 12},
    {11, 12, 13},
    {12, 13, 14}
}

std::unordered_map<int> con;

int Find(int vert) {
  while (vert != con[very])
    vert = con[vert];
  return vert;
}

for (auto triple : faces) {
  for (int vert : triple) {
    if (!con.count(vert)) {
      con[vert]=vert; // i'm my own parent ...
    } else {
      con[vert] = Find(vert);
    }
  }
}

std::unordered_map<int, std::vector<int>> clusters

for (auto& pair : con) {
  // reduce the search path for nodes that has pair as parent.
  int cluster = Find(pair.second);
  con[pair.second] = cluster; 

  clusters[cluster].push_back(pair.first);
}

return clusters; // or convert to vector of vectors 

注意，如果没有路径减半和有效的联合，这将会有一个可怕的运行时。

Answer 2

Surt算法是一种可能的解决方案。

由于您的图是无向的，并且您正在寻找非常简单的东西，请看一下广度优先搜索或深度优先搜索(它们是图论的标准算法，非常容易理解和实现)。

基本上，您可以搜索从起始顶点可达的每个顶点，并将它们标记为同一组。重复此过程，直到每个顶点都有一个组。

Answer 3

假设您要将顶点分成多个顶点集，这些顶点集彼此都可以到达，但不能从该集之外的任何顶点到达。

以下是该算法的伪代码

LOOP
    CONSTRUCT empty current set
    SELECT V arbitrary vertex
    add V to current set
    remove V from graph
    LOOP      // while set is growing
        added_to_set = false
        LOOP V over vertices in graph
            LOOP Vset over current set
                IF Vset connected to V
                     add V to current set
                     remove V from graph
                     added_to_set = true
                     break;
        IF added_to_set == false
           break;    // the set is maximal
    ADD current set to list of sets
    IF graph has no remaining vertices
       OUTPUT sets found
       STOP

有关这一点的C++实现，请参阅https://github.com/JamesBremner/PathFinder2/blob/dbd6ff06edabd6a6d35d5eb10ed7972dc2d779a6/src/cPathFinder.cpp#L483上的代码