有哪些算法可以找到最小环的最小集合？

Question

我有一个无权无向连通图。一般情况下，它是一种化学化合物，有许多循环，并排。这个问题在这个领域很常见，就像标题说的那样。好算法是霍顿的算法。然而，我似乎没有找到任何关于算法的确切信息，一步一步。

显然，我的问题是这个，Algorithm for finding minimal cycles in a graph，但不幸的是，该网站的链接被禁用。我只找到了Figuera算法的python代码，但是Figuearas并不是在每种情况下都能工作。有时它找不到所有的戒指。问题与此类似，Find all chordless cycles in an undirected graph，我试过了，但对像我这样的更复杂的图没有用。我找到了4-5个所需信息的来源，但是算法根本没有得到充分的解释.

我似乎没有找到任何的SSSR算法，虽然这似乎是一个常见的问题，主要是在化学领域。

Answer 1

霍顿的算法很简单。我会为你的用例描述它。

1. 对于每个顶点v，计算根植于v的宽度优先搜索树，使v、w、x成对不同，使w和x的最小公共祖先为v，加上一个由v到w、边wx和从x返回到v的路径组成的循环。
2. 按大小不递减对这些循环进行排序，并按顺序考虑它们。如果当前周期可以表示为它之前所考虑的循环的“排他性或”，那么它就不是基础的一部分。

步骤2中的测试是该算法中最复杂的部分。基本上，您需要做的是将已接受的周期和候选周期写出为0-1关联矩阵，其行按周期索引，其列由边缘索引，然后对该矩阵执行高斯消去，以查看它是否生成一个全为零的行(如果是，则丢弃候选周期)。

通过一些努力，可以节省每次重新消除可接受的循环的成本，但这是一种优化。

例如，如果我们有一个图

a---b
|  /|
| / |
|/  |
c---d

那么我们就有了一个矩阵

      ab  ac  bc  bd  cd
abca   1   1   1   0   0
bcdb   0   0   1   1   1
abdca  1   1   0   1   1

因为abdca实际上不是在步骤1中生成的循环之一。

消除的收益如下：

ab  ac  bc  bd  cd
 1   1   1   0   0
 0   0   1   1   1
 1   1   0   1   1

row[2] ^= row[0];

ab  ac  bc  bd  cd
 1   1   1   0   0
 0   0   1   1   1
 0   0   1   1   1

row[2] ^= row[1];

ab  ac  bc  bd  cd
 1   1   1   0   0
 0   0   1   1   1
 0   0   0   0   0

因此，这组周期是依赖的(不要保留最后一行)。