在图中寻找最小循环的算法

Question

我正在寻找一种算法，它可以在给定一个图的情况下返回所有最小环路。
为了清楚表达我的意思，我需要该算法从以下图中返回确切的环路：
(1,3,6,1)、(1,6,4,1)、(1,4,2,1)、(6,4,7,6)、(2,4,7,2)、(2,7,5,2)

我已经搜索了很多资料，但仍然无法确定这个问题的名称。它是循环基问题还是基本循环问题，或者这两个问题是相同的？我找到了一些涉及最小生成树或全点对最短路径的解决方案，但我都无法理解。
我尝试实现了这里发现的Horton算法：Horton's Algorithm 但我卡在第五页的第四步上，试图找出实际的循环。
有人能够向我解释一下Horton算法的第四步需要做什么，或者给我另一个解决我的问题的算法吗？

- Paris P

---

如果你的图是无权图，DFS 不就能满足你的需求了吗？ - Juan Lopes

我认为霍顿算法适用于带权图。 - Mzf

不，Horton算法用于最短循环基的无权图。引用论文中的话：“在本文中，图是有限的、无向的，没有环或多重边。” - juniper-

您好，链接已经失效了，请问您有其他的资源吗？ - kebs

Answer 1

本文描述了几何工具库中使用的算法（我认为是用C ++编写的）。它基本上是一个修改后的DFS算法，加入了一些代数学。 伪代码太长了，无法在此处发布，因此提供链接：http://www.geometrictools.com/Documentation/MinimalCycleBasis.pdf。

我目前正在进行JavaScript实现。 如果您感兴趣，可以在此处查看：http://jsbin.com/igujuz/8/edit。

- Tomasz Kowalczyk

---

这个算法有一个JS实现，作为JS模块：https://github.com/vbichkovsky/min-cycles - rude

Answer 2

这个算法只适用于无权图：

例子：

INPUT GRAPH: A, B, C, D, E

A: B, C, E
B: A, C
C: A, B, D
D: C, E
E: A, D

算法：

初始化

[LIST] = { }

LIST[A] = { A }
LIST[B] = { B }
LIST[C] = { C }
LIST[D] = { D }
LIST[E] = { E }

DISTANCE = 0

SOLVED = FALSE

SOLUTION = { }

搜索

WHILE NOT SOLVED DO

    DISTANCE = DISTANCE + 1

    FOR EVERY LIST[X] IN [LIST]
        TEMP = LIST[X]
        LIST[X] = { }
        FOR EVERY VERTEX IN TEMP
            LIST[X] += NEIGHBORS(VERTEX)
        END-FOR
    END-FOR

    FOR EVERY LIST[X] IN [LIST]
        FOR EVERY VERTEX IN LIST[X]
            IF VERTEX = X THEN
                SOLUTION = { X, DISTANCE }
                SOLVED = TRUE
            END-IF
        END-FOR
    END-FOR

END-WHILE

- Khaled.K

---

这个算法的来源是什么？它有证明吗？ - sehe