algorithm - 需要图论名称/算法帮助

Question

对标题表示歉意，不能使用“图论问题名称”。

我正在尝试处理一些数据，我需要在其中提取有关数据中包含的结构的信息。

• 是封闭的空间吗
• 所述封闭空间的体积

编辑:初始的“原始”数据在一系列字节中，我可以像访问多维数组一样访问它。

//   X   Y   Z 
data(10, 10, 8);   // 0
data(10, 10, 9);   // 1
data(10, 10, 10);  // 1 
data(10, 10, 11);  // 1

如果该位置的数据中存在大于零的值，则此数据结构中的每个邻居都可能是边节点对。因此数据结构中的每个元素/节点可能有六个可能的边。

因为我知道起始位置(种子)，所以将这些原始数据转换成图形结构对我来说很简单。

node = dataToGraph(10,10,10); // seed position 
node->Edges[0]; // this would correspond to node represented by the value at 9,10,10
                // returns null if the value is less than zero. i.e. no edge/node.

数据表示 3D 空间中的结构，每个结构都有一个特定的种子(下面的深灰色)，其位置是已知的。从这个位置我需要扫描数据/结构以验证其完整结构，即没有间隙，如果有，计算它的内部体积。

虽然我确信我能够找到某种解决方案，但它不会是最优的，而且每个数据集有数百万个这样的结构需要扫描。

我猜我可以使用一个标准的图论解决方案，它比我想出的任何解决方案都要好。不幸的是，我不太熟悉这种数学，所以我什至不知道从哪里开始寻找。

以下是有效数据的二维切片的三个示例。 #3 上的红线说明了我对该示例感兴趣的修剪结构。

一个有效的结构总是有种子，结构是完全封闭的。无效结构可以是任何有间隙的结构，在完整的 3D 结构中的任何地方，或者种子在它所在的切片上有两个以上的邻居/边缘。即不得在外表面或内表面上堵塞。

下面立方体的新图片在一定程度上说明了这一点。假设它有一个空心的内部。红色球体是种子，蓝线代表单个切片，在 2D 示例中为 #1。不幸的是，它永远不会成为像这样规则的结构，因此需要图算法 imo。

如果有人可以提供一些关于从哪里开始的指示，我将不胜感激。我不希望有人给我代码，只是为了教育我 ;)

Answer 1

要找到连接到特定初始种子 block 的所有 block ，您可以使用深度优先搜索算法。

http://en.wikipedia.org/wiki/Depth-first_search