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

Question

我有一个未加权的无向连通图。一般来说，它是一种有很多并排循环的化合物。该问题在该领域很常见，如标题所述。好的算法是霍顿的算法。但是，我似乎没有找到有关该算法的任何确切信息，一步一步。

很明显我的问题是这个，Algorithm for finding minimal cycles in a graph , 但不幸的是，该网站的链接已被禁用。 我只找到了 Figueras 算法的 python 代码，但 Figuearas 并非在所有情况下都有效。有时它找不到所有的环。 问题类似这个，Find all chordless cycles in an undirected graph ，我试过了，但对像我这样的更复杂的图表不起作用。 我找到了 4-5 个所需信息的来源，但根本没有完全解释该算法。

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

Answer 1

Horton 的算法非常简单。我会针对您的用例进行描述。

1. 对于每个顶点 v，计算以 v 为根的广度优先搜索树。对于每条边 wx，使得 v、w、x 成对不同，并且 w 和 x 的最小公共(public)祖先是 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

因此这组循环是相关的(不要保留最后一行)。