Prim演算法和Kruskal演算法的區別

在這篇文章中，我們將瞭解Prim演算法和Kruskal演算法之間的區別。

Kruskal演算法用於最小生成樹 (MST)

  • 給定一個連通且無向的圖，該圖的生成樹是連線所有頂點的子圖，且該子圖是一棵樹。
  • 一個圖可以有多棵生成樹。
  • 對於一個加權的、連通的、無向的圖，最小生成樹 (MST)（也稱為最小權重生成樹）是一棵生成樹，其權重小於或等於所有其他生成樹的權重。
  • 生成樹的權重是透過將與生成樹中每條邊關聯的權重加起來得到的。
  • 最小生成樹可以從圖中權重最小的頂點構建。
  • 每個節點只遍歷一次。
  • 它在稀疏圖中執行速度很快。
  • 時間複雜度為 O(E log V)，其中 V 是頂點數。
  • 它也可以處理不連通的元件。

使用Kruskal演算法查詢MST的步驟

  • 按關聯權重升序對邊進行排序。
  • 選擇最小的邊。
  • 檢查它是否與到目前為止形成的生成樹構成環。
  • 如果沒有形成環，則必須包含此邊。
  • 否則，可以將其丟棄。
  • 重複步驟2、3、4，直到生成樹包含V-1條邊。

Prim演算法最小生成樹 (MST)

  • 這類似於Kruskal演算法，即它是一種貪心演算法。
  • 它從一個空的生成樹開始。維護兩組頂點。
  • 第一組將包含已包含在MST中的頂點，而另一組將包含尚未包含的頂點。
  • 在每一步中，演算法都會考慮所有連線這兩組的邊。然後，它從這些邊中選擇權重最小的邊。
  • 在此步驟之後，演算法移動到包含MST的集合的邊的另一端點。
  • 最小生成樹可以從圖中的任何頂點構建。
  • 一個節點被多次遍歷以獲得最小距離值。
  • 它的時間複雜度為 O(V2)，其中 V 是頂點數。使用斐波那契堆可以將此時間複雜度提高到 O(E + log V)。
  • 它在稠密圖中執行速度很快。
  • 它給出連通分量，並且僅適用於連通圖。

使用Prim演算法查詢MST的步驟

  • 建立一個mstSet，用於跟蹤已包含在MST中的頂點。
  • 為輸入圖的所有頂點分配一個鍵值。
  • 鍵值最初設定為“INFINITE”。
  • 為第一個頂點分配鍵值0，以便可以首先選擇它。
  • 當mstSet不包含所有頂點時，遵循以下步驟。
    • 選擇一個不在mstSet中且具有最小鍵值的頂點“u”。
    • 此“u”現在包含在mstSet中。
    • 更新“u”的所有相鄰頂點的鍵值。
    • 這可以透過遍歷所有相鄰頂點來完成。
    • 對於每個相鄰頂點“v”，如果邊“u”-“v”的權重小於“v”的先前鍵值，則將鍵值更新為“u-v”的權重。

更新於： 2021年3月2日

787 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告