我需要一个工作算法来查找无向图中的所有简单循环.我知道成本可能是指数级的并且问题是NP完全的,但我将在一个小图(最多20-30个顶点)中使用它,并且循环数量很少.
经过长时间的研究(主要是在这里),我仍然没有工作方法.以下是我的搜索摘要:
无向图中的循环 - >仅检测是否存在循环
在无向图中查找多边形 - >非常好的描述,但没有解决方案
在有向图中查找所有循环 - >仅在有向图中查找循环
我发现的唯一一个解决我问题的答案是:
似乎找到一组基本的循环并对它们进行异或可以解决问题.找到一组基本循环很容易,但我不明白如何组合它们以获得图中的所有循环...