给定我们有一个图 G = (V,E) 和一个只有 V 的子集 F，对于 F 的每个连通分量 S，将切割 (S, V\S) 中的最小权重边添加到 F .
为什么每次给F加上最小权值的边，F还是无环的？
最佳答案
要创建循环，您必须创建连接已连接顶点的边。
如果在未连接的顶点之间添加边，则不会创建新循环。您连接两个未连接的组件。但是图仍然是非循环的。
为了更好地理解它的工作原理，您可以将图的连通分量表示为单个顶点。然后，当您在未连接的组件之间添加边时，您只需合并顶点。
顺便说一句，这道题与权重(和MST算法)无关。没有重量它仍然有效。
关于algorithm - 图中的非循环交叉切割，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36296804/