我有一个由街道和人行横道组成的无向图网络，我想知道是否有任何算法可以帮助我找到闭合的回路，即可以放置建筑物的地方。
任何帮助表示赞赏，谢谢!
最佳答案
根据我对先前答案的评论:
似乎所有图都是无向的和平面的，即可以嵌入到2D平面中而没有交叉的边缘，并且给出了这样一种嵌入。该嵌入将对飞机进行分区。例如。图8将平面分为三个区域:两个“内部”区域和一个无限大的外部区域。另一种观点是，节点的所有边缘都是周期性排序的。 (这是使我们能够应用图论的重要部分)
分区必须由一个循环包围，但并非所有循环都可以对单个区域进行分区。但是，在图8的琐碎情况下，所有三个区域都直接与一个独特的循环相关联。
输入图通常可以简化。某些节点可能只有一个边缘。它们不会有助于分区，可以与边缘一起移除。其他节点具有连接不同节点的两个边缘。在这里，节点和两个边缘可以由连接邻居的直接边缘代替。即图8的图形可以简化为两个节点以及它们之间的三个边。 (这不是必要步骤，但有助于计算)。
现在，每个顶点在两侧都有两个区域(由于它们是无向的，因此“左右”并不是明显的区别)。因此，对于|V|顶点，我们需要考虑2 * |V|边。它们通常没有区别。如果两个相邻的边(连接到同一节点)也以同一区域为边界，则它们也以该节点的边的循环顺序相邻。显然，对于只有两个边的节点，两个边共享两个区域(这就是为什么我们在上一步中消除了它们的原因)。对于具有三个边缘的节点，任何两个边缘共享至少一个区域。
因此，这是枚举这些区域的方法:为所有边和顶点分配一个序列号。为每个边指定一个方向，以使其从编号较低的边到较高的边。从顶点1开始，在该区域的右侧进行编号，并对该区域1进行编号。跟踪该区域的边界边缘，并将相同的数字1分配给其边界边缘的相应侧面。为此，您可以在每个节点上以反周期顺序获取下一个相邻边。当您回到起点时，便知道所有边界区域1。
然后，您检查第一个顶点的左边缘。如果它不是区域1的一部分，则它是区域2，并且您应用相同的算法。接下来，检查顶点2，右侧和左侧等。每次找到未编号的边和边时，请分配下一个区域编号并跟踪新建立的区域的边缘。
确定哪个区域号对应于无穷大是一个小问题。为此，请使用一个简单的()图:两个边，两个节点和两个区域(内部和外部)。由于边缘和顶点的随机编号，外部最终可能是1或2。在图论中，内部和外部之间没有区别。