我有一组节点和边，我使用 Dijkstra 算法来找到最短的闭合循环。我的循环相互连接(图中的小黑色循环)。这意味着，对于 2 个周期，有一个共同的边缘。现在，我想要得到最外层的循环(图中的红色循环)，其中包含所有最短的循环。我认为这是一种联盟。没有把握。有没有什么具体的方法或算法方法可以从图中可用的最短闭环中获取最外环？如何实现这个？
在这里，我也将问题标记在c++下，因为大多数程序员确实知道如何获得连接循环的并集，并且我也希望在c++中实现它。预先感谢您。
我已经编辑了一个图形并将其上传到我的原始帖子中，因为其他人不清楚。
最佳答案
据我了解您的问题，您正在尝试找到连接的 planar graph 的边缘最大面。 Boost 库中有一个用于枚举平面图面的算法:Planar Face Traversal 。您可以使用它来迭代图形的面并找到涉及最多边的面。
注释:
- 这实际上只适用于平面图
- 对于许 multimap ，解不是唯一的，考虑正多面体的图 - 在这里，所有面都具有相同的度数，因此没有很好地定义其中哪一个是“外循环” '你正在寻找
- 对于2-连通图和非2-连通图，“涉及最多边的面”的含义是不同的。如果它不是 2-连通的，则会有“分支”伸入某些面，并且根据定义，同一个面位于此类分支的两侧。根据您的喜好/需求，您可以将这些边缘计入脸部的长度，也可以忽略它们，从而得到不同的结果。
关于c++ - 图中循环的并集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9297308/