Kruskal 的演算法

Kruskal 演算法是一種貪心演算法，用於查詢圖的最小生成樹（MST） 。最小生成樹是連線圖的所有頂點並具有最小總邊權重的樹。

Kruskal 的演算法是通過重複挑選具有最小權重的邊 （它們尚未在 MST 中）來實現的，如果由該邊連線的兩個頂點尚未在 MST 中連線，則將它們新增到最終結果中，否則它會跳過該邊。聯合 - 查詢資料結構可用於檢查 MST 中是否已連線兩個頂點。MST 的一些屬性如下：

1. 具有 n 頂點的圖形的 MST 將具有正好的 n-1 邊緣。
2. 從每個頂點到每個其他頂點存在唯一的路徑。