找到连接的节点集群的算法 [英] Algorithm to find cluster of nodes that are connected

问题描述

我正在处理 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]]

解决方案

您可以使用 union-找到

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

未测试的代码

using face = std::array;std::vector<face>面孔 = {{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 Find(int vert) {while (vert != con[very])vert = con[vert];返回顶点；}对于(自动三重:面孔){for (int vert : 三倍) {如果(！con.count(vert)){转换[转换]=转换；//我是我自己的父母...} 别的 {con[vert] = Find(vert);}}}std::unordered_map>集群for (auto& pair : con) {//减少对作为父节点的节点的搜索路径.int cluster = Find(pair.second);con[pair.second] = 集群；集群[集群].push_back(pair.first);}返回集群；//或转换为向量的向量

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

I'm working with 3d data and am provided with a list of vertices that are connected to each other. The data has the following format:

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

Each item in the array consist of a 3-tuple where the number in each position represents the index of the vertices that are connected with each other. I've visualized this example in the picture to give a better understanding of how the vertices are connected.

What I'm looking for is a simple, easy to implement, algorithm that takes faces as it's input and returns the following as it's output:

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

解决方案

You could use union-find

I'll add a naive version of it here

untested code ahead

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 

Note without path halving and effective union this will have a horrible runtime.

这篇关于找到连接的节点集群的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！