設計一個在線性時間內找到這個圖的最小生成樹的算法

我正在研究一個問題，在這個問題中我給出了n個頂點和m個邊的無向圖G，這樣每個邊都有一個權w （e）∈{1,2,3}。其任務是設計一種算法，在線性時間內找到G的最小生成樹（O（n + m））。設計一個在線性時間內找到這個圖的最小生成樹的算法

這是我的想法至今：

在算法圖論的課程，我目前正在研究中，我們已經介紹秩的和普里姆的MST算法。也許我可以用某種方式修改它們，以獲得線性時間。
邊的排序通常需要對數線性（O（mlog（m）））時間;但是，由於所有邊權重爲1,2或3，因此可以使用剷鬥排序對邊的數量進行線性排序（O（m））。

我使用Kruskal算法以下版本：

Kruskal(G) 
    for each vertex ∈ do MAKE−SET() 
    sort all edges in non-decreasing order 
    for edge , ∈ (in the non-decreasing order) do 
    if FIND ≠ FIND() then 
     colour (,) blue 
     UNION(,) 
    od 
    return the tree formed by blue edges

此外，還要-SET（X），聯合（X，Y）和FIND（x）的定義如下：

MAKE-SET() 
    Create a new tree rooted at 
    PARENT()=x 

UNION(,) 
    PARENT FIND() ≔() 

FIND() 
    ≔ 
    while ≠ PARENT() do 
    ≔ PARENT() 
    return y

我現在的問題是，雖然我可以在線性時間內實現Kruskal's的前兩行，但我還沒有設法爲接下來的四行算法（從'for edge ü，...'直到'UNION（u，v）'）。

我希望提示如何在線性時間內實現算法的其餘部分，或者如何在線性時間內找到Kruskal（或其他最小生成樹算法）的修改。

謝謝。

來源

2016-03-01 CKKOY

如果你使用Disjoint Sets data structure with both path compression and union by rank，你會得到一個數據結構，它的每個操作的複雜度增長非常緩慢 - 它類似於Ackermann function的倒數，並且對於諸如宇宙中估計的原子數量。實際上，每個操作都被認爲是恆定的時間，所以算法的其餘部分也被認爲是線性時間。

，從同樣的維基百科文章

由於α（n）是這個函數的反函數，α（n）是小於5對於n的所有遠程實用價值。因此，每次操作的攤銷運行時間實際上是一個小常數。

來源

2016-03-01 16:32:32

非常感謝您的支持。它鞏固了我在講義中教過的材料。 – CKKOY

不客氣。祝你好運。 –

設計一個在線性時間內找到這個圖的最小生成樹的算法

回答

相關問題