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

Question

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

我的问题如下:鉴于我需要实现 Kirchhoff's Laws在主渗透集群上，我需要一个算法来返回集群中所有的，理想情况下，最小的循环。您是否知道一种算法(我的算法现在是暴力破解且效率不高)可以从邻接矩阵中找到图中的所有循环？

Answer 1

一般来说，可以有许多简单循环(循环)，因此由于您只想要“最小的”，这听起来好像您不需要所有循环。如果您要为所有可能的循环编写对应于基尔霍夫第二定律的方程式，那么只需为 cycle basis 中的每个循环使用方程式就足够了。 .有一种多项式时间算法可以找到使用最少总边数的循环基(最小循环基)。然而，与其实现该算法，从弧变量 x_u→v 切换到节点变量 y_v - y_u 的差异可能就足够了>(将每个连通分量的一个节点变量固定为零)。