来自二维三角形阵列的 MST，但有一点扭曲
MST from an array of 2D triangles, but with a little twist
以下是迄今为止所采取步骤的说明：
- 伪随机矩形生成
- "Central node" 插入、矩形分离和最终节点选择
- Delaunay triangulation（显示之前选择的节点）
- 三角形边的渲染
在这一点上（第5步），我想用这个数据形成一个Minimum Spanning Tree，但是有一个轻微的 catch...
图表中的某处（可能靠近中心，但并非总是如此）将是一个节点，需要从其他唯一节点到它的 3-5 个连接。这使事情变得复杂，因为每个其他节点都应该只包含一个连接，并且所使用的数据结构使得很难以可靠的、可遍历的格式确定 "what's connected to what"。
因此，给定上述格式的三角形数组和一个用作 "root node" 的随机顶点，我如何正确地遍历网络以创建至少有 3 个连接的 MST我们的 "central node"，但不超过 5 个连接吗？这可能吗？
由于 Delaunay 三角剖分中的顶点很少有超过 6 条边，您可以使用蛮力：只有 20+15+6 种方法可以 select 3、4 或 5边缘超出 6（分别），所以尝试所有这些。对于由此创建的 41 棵（9 级最多 336 棵）小树（根和一些边）中的每棵，运行 要么 Kruskal's algorithm or Prim's algorithm 从该树开始已经 "found" 成为一部分MST的。 （忽略根的其他边，以免进一步增加其度。）然后选择最好的（包括种子树的成本）。
至于一般的邻居信息问题，看来你只需要先建立一个标准的图形表示。例如，您可以通过扫描所有 Edge 对象并将每个端点存储在与另一个关联的列表中（在 map<Vector2<T>,vector<Vector2<T>>> 或基于顶点的任何标识符的等效项中）来创建邻接列表.
我采取了一种变通方法...
在我的算法的第 3 步之后，我简单地删除所有连接到 "central node" 的边，跟踪哪些边形成它周围的 "ring"（又名 "edge loop"）， 运行 所有剩余边上的 MST。
对于 MST，我使用了 boost 图形库。
这使得遍历我拥有的三角形变得容易，将它的三个边中的每一个添加到 adjacency_list。然后简单地调用任何一个由 boost 提供的 MST 算法来处理剩下的事情。
最后，我读取了之前取出的边缘。最短路径是上一步中的任何路径加上连接到 "ring" 上另一条边的最短边的长度。
然后我可以添加（或删除）任意数量的先前边，以确保有 3 到 5 条边从边循环连接到 "central node"。
按照这个顺序做事也让我在第 3 步时就知道我们是否有有效的边数，所以我们不会浪费周期 运行MST。
以下是迄今为止所采取步骤的说明：
- 伪随机矩形生成
- "Central node" 插入、矩形分离和最终节点选择
- Delaunay triangulation（显示之前选择的节点）
- 三角形边的渲染
在这一点上（第5步），我想用这个数据形成一个Minimum Spanning Tree，但是有一个轻微的 catch...
图表中的某处（可能靠近中心，但并非总是如此）将是一个节点，需要从其他唯一节点到它的 3-5 个连接。这使事情变得复杂，因为每个其他节点都应该只包含一个连接，并且所使用的数据结构使得很难以可靠的、可遍历的格式确定 "what's connected to what"。
因此，给定上述格式的三角形数组和一个用作 "root node" 的随机顶点，我如何正确地遍历网络以创建至少有 3 个连接的 MST我们的 "central node"，但不超过 5 个连接吗？这可能吗？
由于 Delaunay 三角剖分中的顶点很少有超过 6 条边，您可以使用蛮力：只有 20+15+6 种方法可以 select 3、4 或 5边缘超出 6（分别），所以尝试所有这些。对于由此创建的 41 棵（9 级最多 336 棵）小树（根和一些边）中的每棵，运行 要么 Kruskal's algorithm or Prim's algorithm 从该树开始已经 "found" 成为一部分MST的。 （忽略根的其他边，以免进一步增加其度。）然后选择最好的（包括种子树的成本）。
至于一般的邻居信息问题，看来你只需要先建立一个标准的图形表示。例如，您可以通过扫描所有 Edge 对象并将每个端点存储在与另一个关联的列表中（在 map<Vector2<T>,vector<Vector2<T>>> 或基于顶点的任何标识符的等效项中）来创建邻接列表.
我采取了一种变通方法...
在我的算法的第 3 步之后，我简单地删除所有连接到 "central node" 的边，跟踪哪些边形成它周围的 "ring"（又名 "edge loop"）， 运行 所有剩余边上的 MST。
对于 MST，我使用了 boost 图形库。
这使得遍历我拥有的三角形变得容易，将它的三个边中的每一个添加到 adjacency_list。然后简单地调用任何一个由 boost 提供的 MST 算法来处理剩下的事情。
最后，我读取了之前取出的边缘。最短路径是上一步中的任何路径加上连接到 "ring" 上另一条边的最短边的长度。
然后我可以添加（或删除）任意数量的先前边，以确保有 3 到 5 条边从边循环连接到 "central node"。
按照这个顺序做事也让我在第 3 步时就知道我们是否有有效的边数，所以我们不会浪费周期 运行MST。