从无向图提取无弦循环

几年前,我不得不在工作中深入探讨这个主题。谷歌搜索令我惊讶的是,我没有找到任何现成的解决方案。总体而言,仍然看不到任何东西。因此,我不得不从头开始开发主题。



为了清楚说明这是什么,我将给出最简单的示例。



图片



该图非常简单,对于这种图,很容易提出一种选择无弦循环(即没有自相交且无法拆分成较小的循环)的算法。问题在于,图形可能会更加棘手,必须考虑所有情况。经过深思熟虑,编码,反复试验,终于诞生了该算法,该算法现在对工程勘察员有利。



文字说明:



  1. 对于图的每个顶点,我们找到所有相邻的顶点,并通过依次移向每个相邻的顶点开始形成一个循环。
  2. 如果相邻顶点的数量(不包括您输入的顶点)= 0,那么我们返回,形成一个循环--->第5项
  3. 如果相邻顶点的数目(不包括您输入的顶点)等于1,则我们沿着它走,形成一个循环--->第5项
  4. ( , ) >=2, ( ), , ---> .5
  5. — ? , ---> .2
  6. , .
  7. , , , .
  8. , , ---> .1 ( )
  9. 我们再次遍历循环,并查看循环中的左侧分支。找到了这样的分支之后,对于每个分支,我们都进行广度优先搜索(或深度优先),这无关紧要。如果同时我们在所形成的循环的顶部结束(当前循环除外),则我们中断循环的形成并转到--->项目1
  10. 我们编写循环,然后去寻找一个新的--->第1项




更大的伪代码:

图片



首先,建立了越来越复杂的图形来测试算法。

图片



图片

,最后,它已在所有真实的勘探图上进行了如下测试:

图片

我认为它不是最佳的,但目前(大约3年)它可以正常工作而没有失败和抱怨。



我没有引用代码,几乎没有人会对它感兴趣,并且很难抽出一段代码,因为这只是工作的一小部分。



All Articles