Kruskal算法解釋

我讀wikipeida，發現克魯斯卡的僞代碼如下所示：Kruskal算法解釋

KRUSKAL(G):  
    foreach v ∈ G.V:  
     MAKE_SET(v)  
    G.E = sort(G.E)  
    i = 0  
    while (i != |V|-1):  
     pick the next (u, v) edge from sorted list of edges G.E   
     if (FIND_SET(u) != FIND_SET(v)):   
      UNION(u, v)   
      i = i + 1

我安靜不知道什麼FIND_SET()呢，和維基百科有如下描述：

如果邊連接兩棵不同的樹，然後將其添加到森林中，將兩棵樹組合成一棵樹。

所以我想它會檢查兩個不同的樹是否連接，但這是什麼意思？

來源

2012-11-30 Chaos

「偏離主題」...這是一個脫離主題？！（@ Close-voter） –

你誤表了代碼。再看看'i = i + 1'應該去的地方。 –

我認爲如果用if（！inSameSet（u，v））替換'if（FIND_SET（u）！= FIND_SET（v））'，代碼會更容易清楚。 – goat

最初，每個頂點本身都在一個集合中：每個頂點v有一個單獨集合{v}。在僞代碼中，這些集合是make_set(v)的結果。

對於給定的頂點v，函數find_set(v)爲您提供了包含v的集合。

該算法合併集迭代地，因此，如果{u}，{v}是單組最初和存在邊緣(u, v)，則算法通過聯合{u, v}替換兩個集合。現在find_set(u)和find_set(v)都會返回該集合。

算法在您添加|V| - 1非平凡邊緣後終止，這正好是樹中邊緣的數量。

來源

2012-11-30 23:26:47

謝謝，現在的僞碼對我更有意義:) – Chaos

FIND_SET（X）中找到與邊緣X相關聯的集合，使得比較：

FIND_SET(u) != FIND_SET(v)

確保u和v不連接到相同的事情。一種有用的思考方法是找到u和v的「價值」，這些價值觀本身就是這樣設定的。

有關合並森林中的部分具有無關FIND_SET，而是下一行：

UNION(u,v)

其中融合了兩套。

來源

2012-11-30 23:26:06 RonaldBarzell

find_set()是一種稱爲Union-Find的數據結構的常用操作。這個數據結構的想法是有不相交的集合（在你的例子中是頂點）。

在這個算法中，我認爲每個集合都代表連接的頂點。

因此，當您呼叫find_set()傳遞一個頂點時，您將收到表示該組連接的verxtex的元素。

來源

2012-11-30 23:28:20

find_set(u)!=find_set(v)

表示生成樹的基本屬性，即它沒有生成周期。如果它們相等，則表明在圖中有一個週期。

我們基本上通過Kruskal算法制作一個森林（最小邊權重），並在每一步檢查它是否正在循環。

希望它有幫助:)

來源

2012-12-01 07:56:32 tusharmakkar08

Kruskal算法解釋

回答

相關問題