c – 如何在图形网络中找到闭环

概述我有一个由街道和交叉口组成的无向图网络,我想知道是否有任何算法可以帮助我找到闭环,即我可以放置建筑物的地方. 任何帮助表示感谢,谢谢！ 基于对我之前回答的评论： 看起来这些图都是无向和平面的,即可以嵌入2D平面而不交叉边缘,并给出一个这样的嵌入.这种嵌入将分割平面.例如.图8将平面划分为三个：两个“内部”区域和一个无限外部区域.另一种观点是节点的所有边缘都是循环排序的. (这是允许我们应用图论的重 我有一个由街道和交叉口组成的无向图网络,我想知道是否有任何算法可以帮助我找到闭环,即我可以放置建筑物的地方.
任何帮助表示感谢,谢谢！解决方法 基于对我之前回答的评论：

看起来这些图都是无向和平面的,即可以嵌入2D平面而不交叉边缘,并给出一个这样的嵌入.这种嵌入将分割平面.例如.图8将平面划分为三个：两个“内部”区域和一个无限外部区域.另一种观点是节点的所有边缘都是循环排序的. (这是允许我们应用图论的重要部分)

分区必须由循环包围,但并非所有循环都可以分区单个区域.然而,在图8的平凡情况中,所有三个区域都与不同的循环直接相关.

通常可以简化输入图.一些节点可能只有一条边;它们无法为分区做出贡献,可以与边缘一起移除.其他节点具有连接不同节点的两条边.这里,节点和两个边缘可以由连接邻居的直接边缘代替.即图8的图可以简化为两个节点和它们之间的三个边. (这不是必要的步骤,但有助于计算).

现在,每个顶点都有两个区域(因为它们是无向的,“左右”并不是明显的区别).所以,对于| V |顶点,我们需要考虑2 * | V |两侧.它们通常并不明显.如果它们也以该节点的边缘的循环顺序相邻,则两个相邻边(连接到同一节点)可以边界相同的区域.显然,对于只有两条边的节点,两条边共享两个区域(这就是我们在上一步中消除它们的原因).对于具有三条边的节点,任何两条边共享至少一个区域.

所以,这里是如何枚举这些区域：为所有边和顶点分配一个序号.为每条边指定方向,使其从较低编号的边缘延伸到较高编号的边缘.从顶点1开始,右侧,并对此区域进行编号1.跟踪此区域的边界边缘,将相同的数字1指定给其边界边缘的相应边.您可以通过以反周期顺序在每个节点处获取下一个相邻边缘来完成此 *** 作.当你回到起点时,你知道边界区域1的所有边缘.

然后检查第一个顶点的左边缘.如果它不是区域1的一部分,那么它是区域2,并且您应用相同的算法.接下来,检查顶点2,右侧和左侧等.每次找到尚未编号的边和边时,分配下一个区域编号并跟踪新建区域的边缘.

确定哪个区域编号对应于无穷大有一点点问题.要看到这一点,请使用一个简单的()图：两条边,两个节点和两个区域(内部和外部).由于边缘和顶点的随机编号,外部可能最终为1或2.这是不可避免的;在图论中,内部和外部没有区别.

总结

以上是内存溢出为你收集整理的c – 如何在图形网络中找到闭环全部内容，希望文章能够帮你解决c – 如何在图形网络中找到闭环所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。