algorithm - 关于切入最小生成树

Question

我正在阅读有关最小生成树算法的信息。提到了cut。无向图 G = (V, E) 的一个割 (S, VS) 是 V 的一个分区。如果一条边的权重是穿过该割的任何边中的最小值，则该边是穿过该割的轻边。

Kruskal 和 Prims 算法中如何使用上述定义？

我不明白 Kruskals 和 Prim 的算法中如何使用 cut

谢谢

Answer 1

在Prim 的算法中，首先选择一个顶点（任意）。现在，切割这样，选择的顶点属于S和休息是V-S。现在，您选择了最轻的边并将连接顶点添加到S. 并且，您继续这样做，直到所有顶点都在S.

在Kruskal算法中，您不断将图中的最小权重边添加到集合S中。您可以以任何方式切割图形，但如果该切割通过最小权重边，则该边将是最轻的边。并且，它必须被添加到最小生成树中（前提是它连接了两个不同的树）。

我希望这会有所帮助。