關於切入最小生成樹

Question

我正在閱讀最小生成樹算法。它被提及關於削減。 無向圖G =（V，E）的切割（S，V-S）是V的邊界。如果邊的交叉是切割的任何邊交叉的最小值，則邊是交叉切割的光邊。

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

我沒有得到切是如何在Kruskals和普里姆的算法中使用

感謝

Answer 1

在普里姆的算法，第一頂點（任何）被選中。現在，削減，所選的頂點屬於S，其餘的是V-S。現在，您選擇了最輕的重量邊，並將連接頂點添加到S。而且，你繼續這樣做直到所有的頂點都在S。

在克魯斯卡爾的算法中，您不斷添加圖中的最小權重邊到集S。 您可以用任何方式剪切圖形，但如果該剪裁通過最小重量邊緣，則該邊緣將是最輕的邊緣。而且，它必須被添加到最小生成樹（假設它連接兩棵不同的樹）。

我希望有幫助。