关于最小生成树的切割
我正在阅读有关最小生成树算法的内容。提到了切割。 无向图 G = (V, E) 的割 (S, VS) 是 V 的划分。 如果一条边的权重是所有交叉边中的最小值，则该边是穿过切口的轻边 削减。
上述定义如何在 Kruskal 和 Prims 算法中使用？
我不明白 Kruskals 和 Prim 的算法中如何使用 cut
谢谢
I am reading about minimum spanning trees algorithms. It is mentioned about cut.
A cut (S, V-S) of an undirected graph G = (V, E) is a parition of V.
An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing
the cut.
How above definitions is used in Kruskal's and Prims algorithms?
I am not getting how cut is used in Kruskals and Prim's algorithms
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
在Prim算法中，首先选择一个顶点（任意）。现在，进行剪切，使得所选顶点属于
S，其余顶点属于VS。现在，您选择了最轻的边并将连接顶点添加到S。然后，继续执行此操作，直到所有顶点都位于S中。在Kruskal算法中，您不断地将图中的最小权重边添加到集合
S中。您可以以任何方式切割图形，但如果该切割穿过最小权重边，则该边将是最轻的边。并且，它必须被添加到最小生成树中（前提是它连接两棵不同的树）。
我希望这有帮助。
In Prim's algorithm, first a vertex(any) is chosen. Now, cut such that, that the chosen vertex belongs to
Sand rest areV-S. Now, you chose the lightest weight edge and add the connecting vertex toS. And, you continue doing it till all the vertices are inS.In Kruskal's algorithm, you keep adding the minimum weight edge in the graph to the set
S.You can cut the graph in any manner, but if that cut passes through the minimum weight edge, then that edge will be the lightest edge. And, it has to be added to the minimum spanning tree (provided that it connects two different trees).
I hope that helps.