gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:45:15 27 4
gpt4 key购买 nike

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

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

最佳答案

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

关于algorithm - 在图中寻找循环的高效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26405262/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com