我需要一个工作算法来查找无向图中的所有简单循环.我知道成本可能是指数级的并且问题是NP完全的,但我将在一个小图(最多20-30个顶点)中使用它,并且循环数量很少.
经过长时间的研究(主要是在这里),我仍然没有工作方法.以下是我的搜索摘要:
无向图中的循环 - >仅检测是否存在循环
在无向图中查找多边形 - >非常好的描述,但没有解决方案
在有向图中查找所有循环 - >仅在有向图中查找循环
我发现的唯一一个解决我问题的答案是:
似乎找到一组基本的循环并对它们进行异或可以解决问题.找到一组基本循环很容易,但我不明白如何组合它们以获得图中的所有循环...
我知道这个问题有很多答案.但是,我发现它们中没有一个能够真正实现它.
有人认为一个循环(几乎)与强连通组件相同(s.在有向图中查找所有循环),因此可以使用为该目标设计的算法.
有人认为找到一个循环可以通过DFS完成并检查后端(s.文件依赖关系的boost图文档).
我现在想对是否可以通过DFS检测图中的所有循环并检查后沿有一些建议？
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf(在SO上找到)陈述了一种基于循环基础的方法.我个人而言,我觉得它不是很直观,所以我正在寻找一个不同的解决方案.
编辑:我最初的意见显然是错误的.S."Moron"的下一个回答.
初步意见:我的观点是它确实可以这样工作,因为DFS-VISIT(DFS的伪代码)刚刚进入尚未访问过的每个节点.从这个意义上讲,每个顶点都表现出一个潜在的循环开始.此外,由于DFS每次访问每个边缘,因此也会覆盖通向循环起点的每条边.因此,通过使用DFS和后沿检查,确实可以检测图中的所有周期.注意,如果存在具有不同数量的参与者节点的循环(例如,三角形,矩形等),则必须进行额外的工作以区分每个循环的实际"形状".