c++ - 来自二维三角形阵列的 MST，但有一点扭曲

Question

以下是迄今为止所采取步骤的说明:

1. 伪随机矩形生成
2. “中心节点”插入、矩形分离和最终节点选择
3. Delaunay triangulation (与先前选择的节点一起显示)
4. 三角形边的渲染

此时(第 5 步)，我想使用此数据形成一个 Minimum Spanning Tree ，但有一个轻微问题...

图表中的某处(可能靠近中心，但不总是)将是一个节点，需要从其他唯一节点到它的 3-5 个连接。这使事情变得复杂，因为每个其他节点都应该只包含一个连接，并且所使用的数据结构使得很难以可靠的、可遍历的格式确定“什么连接到什么”。

因此，给定上述格式的三角形数组和一个用作“根节点”的随机顶点，我如何正确地遍历网络以创建一个 MST，其中至少有 3 个连接到我们的“中心节点”节点”，但连接不超过 5 个？这可能吗？

Answer 1

由于 Delaunay 三角剖分中的顶点很少有超过 6 条边，因此您可以使用蛮力:只有 20+15+6 种方法可以从 6 条边中选择 3、4 或 5 条(分别), 所以尝试所有这些。对于由此创建的 41 棵小树(9 阶最多 336 棵)中的每棵小树(根和一些边)，运行 Kruskal's algorithm或 Prim's algorithm从已经“发现”成为 MST 一部分的那棵树开始。 (忽略根的其他边，以免进一步增加其度。)然后选择最好的一条(包括种子树的成本)。

至于一般的邻居信息问题，看来你只需要先建立一个标准的图形表示。例如，您可以通过扫描所有 Edge 来创建邻接表。对象并将每个端点存储在与另一个关联的列表中(在 map<Vector2<T>,vector<Vector2<T>>> 或基于您的顶点的任何标识符的等效项中)。