基于Prim最小生成樹算法的時間成本研究

程媛媛

（亳州職業(yè)技術(shù)學(xué)院信息工程系，安徽 亳州236800）

目前，為了解決最小成本的實際應(yīng)用問題，采用了帶權(quán)圖的最小生成樹算法 （prim），該算法由若干條指令對問題進行運算等操作，得出問題的最優(yōu)解。在程序執(zhí)行過程中，算法分析和算法復(fù)雜度都占有了算法所需的時間。因此，本文針對Prim算法的時間復(fù)雜性依使用的數(shù)據(jù)結(jié)構(gòu)不同，得出在使用數(shù)組時時間復(fù)雜性為O （V2），使用 （二元）堆結(jié)構(gòu)時為O （EIgV），使用斐波那契堆結(jié)構(gòu)的情況下為O （E＋VlgV）。

1 Prim算法

與Kruskal算法齊名的是最小生成樹算法，即Prim算法。Kruskal算法是一條邊一條邊地考慮，而Prim算法則是一個節(jié)點一個節(jié)點地考慮。這也算很自然的一種考慮。事實上，凡是涉及圖的算法，都可以有按邊和按節(jié)點進行考慮的不同。

該算法由捷克數(shù)學(xué)家Vojtěch Jarník于1930年提出，后來被計算機科學(xué)家Robert C.Prim于1957年獨立發(fā)現(xiàn)。[1]1959年Edsger Dijkstra重新發(fā)現(xiàn)該算法。因此，該算法有很多名稱，如DJP算法、Prim－Jarník算法。

本文從一顆空的最小生成樹開始，每一步增加該生成樹的尺寸，直到其包括所有節(jié)點為止。這種思路就是Prim算法。該算法自然地用到切割屬性，如果將所有節(jié)點分為2個（分離）集合，則連接2個集合的所有邊里面最小的一條邊必然屬于某棵最小生成樹。這樣，如果其中一個集合代表正在構(gòu)建的生成樹，另一個集合代表尚未考慮的節(jié)點，則每次從尚未考慮的節(jié)點里面選取距離正在構(gòu)建的集合最短（或最近）的節(jié)點將是正確的。[2]每次增加生成的尺寸時，只要遵守貪婪的原則，即選擇最小的跨越當前最小生成樹內(nèi)外的邊，就會正確產(chǎn)生最小生成樹。

2 構(gòu)建最小生成樹及Prim算法

可以按照一個節(jié)點到其中一個分離集合 （即正在構(gòu)建的最小生成樹）的最短距離來賦值。這個值當然是該節(jié)點到給定集合里面所有邊中距離最小的值。

2.1 最小生成樹問題

在圖論問題中，對于連通且沒有環(huán)路的連通圖稱為樹，這種圖可以以任意一個節(jié)點為杠桿提起來，而形成一個由上往下的節(jié)節(jié)分支的倒樹形狀。[3]在一個連通圖里刪除所有的環(huán)路而形成的樹叫做該圖的生成樹，需要找出的樹由于具有最小總權(quán)重，因此又被稱為最小生成樹。[4]最小生成樹問題在實際生活中應(yīng)用非常多，可以在計算機網(wǎng)絡(luò)、路由控制、公路、電力等網(wǎng)絡(luò)規(guī)劃，甚至在人際關(guān)系網(wǎng)的構(gòu)建等方面也提供了一定的幫助。

對這些問題進行抽象，得到最小生成樹問題的定義如下：

輸入：帶權(quán)重的連通無向圖G＝ （V，E），每條邊的權(quán)重為Wi。

2.2 算法步驟

（1）構(gòu)建一個空的最小生成樹T，并將所有節(jié)點的賦值設(shè)為無窮。

（2）選擇圖G的任意一節(jié)點，將其置于欲構(gòu)建的最小生成樹T里，另外一個節(jié)點集合為V－T。

（3）對V－T里面的節(jié)點的賦值進行修改 （因為T里面多了一個節(jié)點，這些距離可能發(fā)生變化）。

（4）從V－T集合中選擇賦值最小的節(jié)點，加入到T里面。

（5）如果V－T為非空，則繼續(xù)步驟3～5；否則算法終結(jié)。

在算法結(jié)束時，二元對組 ｛（v，π[v]）｝給出的就是一顆最小生成樹。

2.3 算法分析

該算法一開始將所有的節(jié)點分解為2個集合：Q和V－Q。一開始V－Q里沒有元素，而Q中所有元素離V－Q里元素距離為無窮。然后選擇任意節(jié)點作為起始節(jié)點，并將該元素與V－Q集合里元素的距離初始化為0。之后算法的主要部分就可以開始了。

算法主要由第4步的while循環(huán)構(gòu)成。該循環(huán)以隊列Q里面是否還有元素作為終結(jié)條件。只要Q里面還有元素，算法就繼續(xù)進行：從隊列里面選取離集合最近的元素u加入到集合V－Q里，然后對每個與u有邊直接相連的節(jié)點進行考慮 （第6行的for循環(huán)）。

算法的第8個步驟對節(jié)點v到S的距離進行調(diào)整。這個調(diào)整因為有新加入到S的節(jié)點與新加入之間的邊長w （u，v）和當前已經(jīng)計算出的v到S的距離key[v]的相對關(guān)系，[5]如果邊長小于當前距離，就將當前距離調(diào)降為邊長。因此，這個步驟也稱為降距 （Decrease－Distance）。圖1至圖6為該算法的一個演示。

根據(jù)圖1給出的是選取任意節(jié)點作為起始節(jié)點，將其加入到集合S后的狀態(tài)。此時除源點到集合S的最近距離0外，其他節(jié)點與S的距離都被初始化為∞。[6]然后考察與S里面唯一節(jié)點右邊相鄰的節(jié)點，發(fā)現(xiàn)7、10、15三個節(jié)點，降距其與S的距離后形成圖2。

圖1 從任意節(jié)點開始，其他為∞

圖2 與源點0有邊相連的節(jié)點被降低

在所有節(jié)點里面，按照貪婪策略選取離S最近的節(jié)點，即7，加入到S里，并對與節(jié)點7有邊直接相連的所有節(jié)點進行降距，得到圖3。然后在所有S外面的節(jié)點里選擇離S最近的節(jié)點，即5，加入到S里，并將于節(jié)點5直接有邊相連的節(jié)點進行降距，得到圖4。

圖3 最近的節(jié)點7被加入

圖4 降距相鄰節(jié)點，加入最近節(jié)點5

之后選擇離S最近的節(jié)點，即6，加入到S中，并降距與節(jié)點6直接有邊相連的節(jié)點的距離，形成圖5。這樣循環(huán)往復(fù)，最后得到圖6。此時，最小生成樹已經(jīng)完成。

圖6 加入節(jié)點8、9、14、15后的狀態(tài)

圖5 降距相鄰節(jié)點，加入最近節(jié)點6

3 算法的時間成本分析及結(jié)果

3.1 算法的時間復(fù)雜度

若要比較不同算法的時間效率，就要確定一個度量標準，最直接的辦法就是將計算法轉(zhuǎn)化為程序，在計算機上運行，通過計算機內(nèi)部的計時功能獲得精確的時間，然后進行比較。但該方法受計算機硬件、軟件等因素的影響，會掩蓋算法本身的優(yōu)劣，所以一般采用事先分析估算的算法，即撇開計算機軟硬件等因素，只考慮問題的規(guī)模 （一般用自然數(shù)n表示），認為一個特定算法的時間復(fù)雜度，只采取于問題的規(guī)模，或者說它是問題的規(guī)模的函數(shù)。[7]為了方便比較，通常的做法是，從算法選取一種對于所研究的問題 （或算法模型）來說是基本運算的操作，以其重復(fù)執(zhí)行的次數(shù)作為評價算法時間復(fù)雜度的標準。該基本操作多數(shù)情況下是由算法最深層環(huán)內(nèi)的語句表示的，基本操作的執(zhí)行次數(shù)實際上就是相應(yīng)語句的執(zhí)行次數(shù)。一般T（n）Of（n），部分執(zhí)行語句如下：

則有T（n）＝n的平方＋n的三次方，根據(jù)上面括號里的同數(shù)量級，可以確定n的三次方為T （n）的同數(shù)量級

則有f（n）＝n的三次方，然后根據(jù)T（n）／f（n）求極限可得到常數(shù)c。則該算法的時間復(fù)雜度：T（n）＝O （n的三次方）

O（1）＜O（log2n）＜O（n）＜O（nlog2n）＜O（n2）＜O（n3）＜O（2n）

所以要選擇時間復(fù)雜度量級低的算法。

3.2 利用時間復(fù)雜性對算法的時間成本分析

根據(jù)Prim的算法及對算法的分析來對算法的時間成本進行分析。通過上面的算法可以看出，第1～3行的總成本為Θ （V），第6～9行的內(nèi)循環(huán)一共循環(huán)節(jié)點u的度數(shù) （degree（u））次，第4行的外層循環(huán)的次數(shù)最多為｜V｜次。因此，該算法的時間復(fù)雜性為Θ（V）·TEXTRACT－MIN＋Θ（E）·TDECREASE－DISTANCE

顯然，TEXTRACT－MIN和TDECREASE－DISTANCE所需要的時間與實現(xiàn)隊列Q所使用的數(shù)據(jù)結(jié)構(gòu)相關(guān)。如果直接使用數(shù)組，則每次選取最小元素需要的時間成本為O（V）。而對一個節(jié)點進行降距操作為常數(shù)時間[8]。因此，在使用數(shù)組作為隊列Q的實現(xiàn)機制時，Prim算法的總時間成本為O（V2）。

如果使用二進制堆來存放Q的元素，則抽取最小元素的時間成本將降低到O（lgV），但在堆里面對一個元素進行降距操作所需要的時間也是O（lgV），從而導(dǎo)致Prim算法的總時間成本為O（ElgV）。如果圖為稀疏圖 （即E遠遠小于V2），則該時間復(fù)雜性要好于數(shù)組的情況。如果圖為稠密圖，則時間復(fù)雜性接近O（V2lgV），顯然不如使用數(shù)組的情況。

如果使用改進的斐波那契堆來實現(xiàn)隊列Q，則抽取最小元素的成本維持為O（lgV），但降距的時間成本將重新回歸到常數(shù)時間，從而使Prim算法的總時間成本降為O（E＋lgV），好于數(shù)組或二進制堆的情況。這里的攤銷成本分析指的是針對一組操作進行最壞情況分析后得出的每個具體操作的成本。因此得出在不同數(shù)據(jù)結(jié)構(gòu)下，Prim算法的時間復(fù)雜性，如表1所示。

表1 Prim最小生成樹算法的時間成本

斐波那契堆是一種所謂的 “可歸并的堆”（mergeable heap），它實際上是一組堆 （或樹）的集合。此種數(shù)據(jù)結(jié)構(gòu)由于理解困難和編程過程復(fù)雜，在實際上并沒有多少價值。因此，表1里給出的O（E＋VlgV）攤銷時間成本只有理論上的價值。在實際中，Prim算法的時間成本通常被認為是min（O（ElgV），O（V2））。

4 結(jié) 語

本文在Prim最小生成樹算法的基礎(chǔ)上對時間成本進行分析，算法的復(fù)雜性決定了時間的復(fù)雜性，算法越復(fù)雜，在算法運行上耗費的時間越多。針對prim最小生成樹算法在運行上，利用了時間復(fù)雜度對算法時間成本進行分析，得到了時間成本的結(jié)果，為今后在工程應(yīng)用領(lǐng)域解決問題、選擇算法起到了關(guān)鍵性的作用。

[1]丁國強，呂治國.基于Prim算法最小生成樹優(yōu)化的研究[J].甘肅聯(lián)合大學(xué)學(xué)報，2009，23（05）：67－69.

[2]武鵬，李美安.具有 O（n）時間復(fù)雜度的分布式請求集生成算法[J].計算機應(yīng)用，2013，33（02）：323－325.

[3]江波，張黎.基于Prim算法的最小生成樹優(yōu)化研究[J].計算機工程與設(shè)計，2009，30（13）：3244－3247.

[4]歐陽浩，陳波.求解最小生成樹的一種小生境遺傳禁忌算法[J].計算機工程與應(yīng)用，2013，49（01）：59－61.

[5]潘大志，陳友軍.Prim算法的一種優(yōu)化實現(xiàn)[J].西華師范大學(xué)學(xué)報，2011，32（01）：63－66.

[6]邊釗，唐娉，陳趁新.基于閾值約束最小生成樹算法的區(qū)域合并方法[J].計算機工程與設(shè)計，2012，33（01）：229－232.

[7]王會青，陳俊杰，郭凱.啟發(fā)式初始化獨立的k－均值算法研究[J].計算機工程與應(yīng)用，2012，48（11）：129－132.

[8]任仕玖，宋暉，蔣勛.基于改進Prim算法的變電站巡檢機器人路徑規(guī)劃[J].西南科技大學(xué)學(xué)報，2011，26（01）：61－63.