最小生成樹 (MST)

在加權圖中，最小生成樹是指權重小於同一圖所有其他生成樹的生成樹。在現實情況下，此權重可以衡量為距離、擁塞、交通負荷或賦予邊的任何任意值。

Java 中的 Prim 演算法

Prim 演算法（與克魯斯卡爾演算法一樣）用於查詢最小成本生成樹，它使用貪心方法。Prim 演算法與最短路徑優先演算法類似。

與克魯斯卡爾演算法相比，Prim 演算法將節點視為一棵樹，並不斷從給定圖中向生成樹新增新節點。

為了與克魯斯卡爾演算法進行對比並更好地理解 Prim 演算法，我們將使用相同的示例：

步驟 1 - 刪除所有環和並行邊

從給定圖中刪除所有環和並行邊。如果存在並行邊，則保留關聯成本最低的邊，並刪除所有其他邊。

步驟 2 - 選擇任意節點作為根節點

在本例中，我們選擇S節點作為 Prim 生成樹的根節點。此節點是任意選擇的，因此任何節點都可以是根節點。有人可能會想知道為什麼任何影片都可以是根節點。答案是，在生成樹中，包含圖的所有節點，並且由於它是連通的，因此必須至少有一條邊將其連線到樹的其餘部分。

步驟 3 - 檢查輸出邊並選擇成本較低的邊

選擇根節點S後，我們看到 S，A 和 S，C 是兩條權重分別為 7 和 8 的邊。我們選擇邊 S，A，因為它小於另一條邊。

現在，將樹 S-7-A 視為一個節點，我們檢查所有從中引出的邊。我們選擇成本最低的邊並將其包含在樹中。

此步驟之後，將形成 S-7-A-3-C 樹。現在，我們將再次將其視為一個節點，並再次檢查所有邊。但是，我們只會選擇成本最低的邊。在本例中，C-3-D 是新的邊，它小於其他邊的成本 8、6、4 等。

將節點D新增到生成樹後，我們現在有兩條從中引出的邊具有相同的成本，即 D-2-T 和 D-2-B。因此，我們可以新增任意一個。但是下一步將再次產生邊 2 作為最低成本。因此，我們顯示了一個包含兩條邊的生成樹。

我們可能會發現，使用兩種不同的演算法對同一圖得到的生成樹是相同的。