在圖中尋找循環的高效算法

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的差異可能就足夠了（將每個連接的組件的一個節點變量固定爲零）。