在图中寻找循环的高效算法

Question

我必须研究percolating network of conducting wires 的主簇的电阻。单独的电线从1到n标记。我用图G（V，E）表示网络并找到它的邻接矩阵A，其中如果导线i和j接触，则A_ij = 1，否则为0。

我的问题如下：鉴于我需要在主渗透群集上实现Kirchhoff's Laws ，我需要一种算法，它返回群集中所有理想的最小环路。你知道一个算法（我现在是否是bruteforce并且效率不高），它从它的邻接矩阵中找出图中的所有循环？

Answer 1

一般来说，可以有许多简单的循环（循环），所以既然你只需要“最小的”，听起来就好像你不需要它们。如果你想写出对应于所有可能循环的基尔霍夫第二定律的方程，那么只需使用cycle basis中的每个循环的方程即可。有一个多项式时间算法来查找使用最少总数的边的循环基（最小循环基）。然而，不是实现该算法，而是从弧变量x _{u → v}切换到节点变量y的差异可能就足够了（将每个连接的组件的一个节点变量固定为零）。