有哪些算法可以找到最小环的最小集合？
Which algorithms are there to find the Smallest Set of Smallest Rings?
我有一个未加权的无向连通图。一般来说，它是一种有很多并排循环的化合物。该问题在该领域很常见，如标题所述。好的算法是霍顿的算法。但是，我似乎没有找到有关该算法的任何确切信息，一步一步。
很明显，我的问题是 Algorithm for finding minimal cycles in a graph，但不幸的是，该站点的 link 已被禁用。
我只找到了 Figueras 算法的 python 代码，但 Figuearas 并非在所有情况下都有效。有时它找不到所有的环。
问题与此类似， Find all chordless cycles in an undirected graph ，我尝试过但不适用于像我这样的更复杂的图形。
我找到了 4-5 个所需信息的来源，但根本没有完全解释算法。
我似乎没有找到任何 SSSR 的算法，虽然它似乎是一个常见的问题，主要是在化学领域。
Horton 的算法非常简单。我会针对您的用例进行描述。
对于每个顶点 v，计算以 v 为根的广度优先搜索树。对于每条边 wx 使得 v、w、x 成对不同并且使得 w 和的最小共同祖先x是v，加上由v到w的路径、边wx、x回到v的路径组成的圈。
按大小非递减对这些循环进行排序，并按顺序考虑它们。如果当前循环可以表示为之前考虑的"exclusive OR"个循环，则它不是基础的一部分。
步骤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
所以这组循环是相关的（不要保留最后一行）。
我有一个未加权的无向连通图。一般来说，它是一种有很多并排循环的化合物。该问题在该领域很常见，如标题所述。好的算法是霍顿的算法。但是，我似乎没有找到有关该算法的任何确切信息，一步一步。
很明显，我的问题是 Algorithm for finding minimal cycles in a graph，但不幸的是，该站点的 link 已被禁用。 我只找到了 Figueras 算法的 python 代码，但 Figuearas 并非在所有情况下都有效。有时它找不到所有的环。 问题与此类似， Find all chordless cycles in an undirected graph ，我尝试过但不适用于像我这样的更复杂的图形。 我找到了 4-5 个所需信息的来源，但根本没有完全解释算法。
我似乎没有找到任何 SSSR 的算法，虽然它似乎是一个常见的问题，主要是在化学领域。
Horton 的算法非常简单。我会针对您的用例进行描述。
对于每个顶点 v，计算以 v 为根的广度优先搜索树。对于每条边 wx 使得 v、w、x 成对不同并且使得 w 和的最小共同祖先x是v，加上由v到w的路径、边wx、x回到v的路径组成的圈。
按大小非递减对这些循环进行排序，并按顺序考虑它们。如果当前循环可以表示为之前考虑的"exclusive OR"个循环，则它不是基础的一部分。
步骤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
所以这组循环是相关的（不要保留最后一行）。