图中圈的并

Question

​

我有一组节点和边，我使用Dijkstra的算法来找到相互连接的最短闭合cycles.My圈(图中的小黑圈)。这意味着，对于2个周期，有一个共同的边缘。现在，我想要得到最多的外部循环(图中的红色循环)，它包含所有最短的循环。我认为这是一种联盟。不确定。是否有任何特定的方法或算法方法来从图中可用的最短闭合圈中获得最外层的圈？如何实现这一点？

在这里，我也在c++下面标记了这个问题，因为大多数程序员确实知道如何获得连接循环的并集，我也希望在c++中实现这一点。提前谢谢你。

我已经编辑并上传了一个图形到我的原始帖子中，因为这对其他人来说并不清楚。

Answer 1

我理解你的问题，你正在尝试寻找一个连通planar graph的最大边的面。Boost库中有一个用于枚举平面图的面的算法：Planar Face Traversal。您可以使用它来迭代图的面，并找到涉及到的边最多的面。

备注：

这实际上只适用于平面graphs

• For许多图，解决方案是不唯一的循环，考虑一个正则多面体的图-在这里，所有的面都有相同的次数，所以没有很好地定义它们中的哪一个是你正在寻找的‘’

​

​

• 对于2-和非2-connected的图来说，“面对最多的边”是什么意思是不同的。如果它不是2-连接的，将会有“分支”到达一些面，根据定义，相同的面位于这样的分支的两侧。根据你的喜好/需要，你可以将这些边缘计入脸部的长度，也可以忽略它们，得到不同的结果。

Answer 2

Boost geometry似乎包含您需要的what，但它相当抽象，我需要一些时间来与您的问题联系起来。显然，within可以应用于每一对环，以确定周长。或者更好的是，找到面积最大的环。