張亞蕾

（仰恩大學(xué) 數(shù)學(xué)系，福建 泉州 362014）

0 引言

樹是圖論中很重要的概念，最早是由德國物理學(xué)家基爾霍夫提出來的，當時沒有引起人們的重視，但是現(xiàn)在樹已經(jīng)發(fā)展為圖論中重要部分，在大數(shù)據(jù)、人工智能、物流運輸、道路工程、管道問題等許多領(lǐng)域和實際問題中都有著廣泛的應(yīng)用.所謂樹就是連通且沒有回路的無向圖，生成樹就是一個無向連通圖中連通且沒有回路的生成子圖，帶權(quán)無向連通圖的最小生成樹問題作為一個典型的圖論問題，求最小生成樹算法和求生成樹的權(quán)這些問題已經(jīng)比較成熟，常用的求最小生成樹算法有克魯斯卡爾算法和普里姆算法［1-2］，除此外還有破圈法、逐步短接法［1］、Sollin算 法、Dijkstra算法等算法，近年來最小生成樹算法的應(yīng)用也越來越多［3-4］.毛華等［5］研究了求最小生成樹的矩陣算法，劉育剛［6］對最小生成樹的鄰接矩陣法也進行了研究，本文在毛華等人研究的基礎(chǔ)上討論最大生成樹的改進的權(quán)矩陣算法及其應(yīng)用.本文中的G=V,E,W表示無向圖，其中V={ }v1,v2,…,vn為無向圖的頂點集，E為該無向圖的邊集，W為該無向圖中邊的權(quán)集，(vi,vj)表示以vi,vj為頂點的邊，Wij為邊的(vi,vj)權(quán).

1 預(yù)備知識

無向樹的定義［1-2］：一個連通且無回路的無向圖稱為樹，也稱為自由樹.

最大生成樹的定義［1-2］：設(shè)G=V,E是一個具有n個結(jié)點的無向連通圖，包含G所有n個結(jié)點，保持連通性的權(quán)的極大連通子圖就稱為G的最大生成樹.

生成樹存在定理［1-2］：一個無向圖帶權(quán)連通圖一定存在生成樹.假設(shè)G=V,E,W是一個無向連通圖，U是頂點集V的一個非空子集.若(u ,v)是一條權(quán)最大邊，其中u∈U，v∈V-U，則一定可以找到一棵的最大生成樹，這個最大生成樹包含邊(u ,v).

2 三種常見的最大生成樹算法

2.1 利用Kruskal算法求最大生成樹

Kruskal算法也稱為閉圈法，該算法最早由Kruskal于1956年提出，最大生成樹的Kruskal算法的基本思想：首先按照邊的權(quán)值由大到小把所有邊排序，然后依次選取沒有進入生成樹中權(quán)值最大的邊e，如果沒有構(gòu)成回路，則將該邊加入生成樹T中，重復(fù)此過程至生成樹中達到n-1條邊為止.這時我們發(fā)現(xiàn)T中不含任何回路且連通，因此是樹，而且按照這種過程得到的一定是最大生成樹[7].

2.2 利用破圈法求最大生成樹

我國的管梅谷教授于1975年提出了計算最小生成樹的破圈法.破圈法是“見圈破圈”的一種算法：即如果看到無向連通圖中有一個回路，就將這個回路中的邊去掉一條，直至圖中再無任何回路且還保持連通性為止.利用破圈法求最大生成樹，就是見圈就刪除該回路中權(quán)最小的那個邊，如此見圈破圈，直到圖中沒有一圈為止，這是剩下的圖一定是原圖（原圖是無向連通圖）的最大生成樹[7].

2.3 利用Prim算法求最大生成樹

Prim算法雖然是以美國計算機科學(xué)家羅伯特·普里姆命名的，但是最早是在1930年由捷克數(shù)學(xué)家沃伊捷赫·亞爾尼克發(fā)現(xiàn)；因此，普里姆算法又被稱為DJP算法、亞爾尼克算法或普里姆-亞爾尼克算法.最大生成樹Prim算法是按逐個將頂點連通的方式來構(gòu)造的.首先任意選取圖G=V，E，W中的一個頂點v加入到頂點集Q中，之后在V-Q中任選頂點u，如果u到集合Q中的某個頂點有邊，并且該邊的權(quán)是所有連接Q中的點和不在Q中的點的邊中權(quán)最大的，就將頂點u加入集合Q中，同時將剛才找到的那個權(quán)最大邊加入邊集ET中，如此反復(fù)重復(fù)該過程，直到原圖中的所有頂點都進入Q中，這時候ET中的邊和所有頂點就可以形成原圖的一棵最大生成樹[7].

3 改進的鄰接矩陣求最大生成樹

定義1［1］：設(shè)圖G是一個無向圖，令aij為vi鄰接到vj的邊的條數(shù)，則稱()aijn×n為G的鄰接矩陣.

定義2：設(shè)圖G是一個無向連通簡單圖，Wij為邊( )vi,vj的權(quán)，仿照鄰接矩陣定義給出權(quán)矩陣A的定義如下：

定義3：設(shè)圖G是一個無向連通復(fù)雜圖，Wij為邊( )vi,vj的權(quán)，這是可能會有平行邊，定義改進的權(quán)矩陣A如下：

3.1 改進的鄰接矩陣算法

毛華等介紹了求最小生成樹的權(quán)矩陣算法［5］，我們仿照該算法給出最大生成樹的矩陣算法.假設(shè)G=是一個具有n個頂點的帶權(quán)無向連通圖，A表示其權(quán)矩陣，定義如上定義2和定義3.

3.2 最大生成樹的權(quán)矩陣算法

假設(shè)G=V,E,W是一個具有n個頂點的帶權(quán)無向連通圖，開始時，我們設(shè)Q=?，ET=?，K=0，然后在權(quán)矩陣任取一行找出一個最大元素，不妨設(shè)為aij，若邊，此時用*在權(quán)矩陣中標注元素aij，aji；若邊(ui,uj) ? ET，則令ET=ET，Q=Q，K=K，此時用×在權(quán)矩陣中標注元素aij，aji.然后在權(quán)矩陣中選取Q中元素對應(yīng)行中除了標注外的最大元素，重復(fù)上述過程，直至K=n-1，算法結(jié)束，此時ET中的元素對應(yīng)的邊的導(dǎo)出子圖就是圖G的一個最大生成樹.

3.3 最大生成樹的改進的權(quán)矩陣算法

假設(shè)G=V,E,W是一個具有n個頂點的帶權(quán)無向連通圖，顯然G的權(quán)矩陣是一個對稱矩陣，因此我們只需要從主對角線以上（或以下）找最大元素即可.開始時，我們設(shè)Q=?，ET=?，K=0，然后在權(quán)矩陣主對角線以上（或以下）的任取一列（或者一行）找出一個最大元素，不妨設(shè)為aij，若邊(ui,uj) ?ET，則令，此時用*在權(quán)矩陣中標注元素aij，若邊(ui,uj) ?ET，則令ET=ET，Q=Q，K=K，此時用×在權(quán)矩陣中標注元素aij.然后在權(quán)矩陣中主對角線以上（或以下）選取Q中元素對應(yīng)列（或者行）中除了標注外的最大元素，重復(fù)上述過程，直至K=n-1，算法結(jié)束，此時ET中的元素對應(yīng)的邊的導(dǎo)出子圖就是圖G的一個最大生成樹.

3.4 改進的權(quán)矩陣法的具體步驟

（1）初始狀態(tài)，ET為空集，Q= ?，ET= ?，K=0；

（2）在權(quán)矩陣主對角線元素以上（或以下）的任取一列（或者一行）找出一個最大元素，不妨設(shè)為aij，若此時用*在權(quán)矩陣中標注元素aij，若邊此時用×在權(quán)矩陣中標注元素aij.若K=n-1，算法結(jié)束，此時ET中的元素對應(yīng)的邊的導(dǎo)出子圖就是圖G的一個最大生成樹.若K＜n-1，轉(zhuǎn)（3）.

（3）在權(quán)矩陣主對角線以上（或以下）選取Q中元素對應(yīng)列（或者行）中除了標注外的最大元素，轉(zhuǎn)（2）.

3.5 算法分析

Kruskal算法的時間復(fù)雜度不僅與無向連通圖的邊的數(shù)目有關(guān)，還與頂點的個數(shù)有關(guān)，其時間復(fù)雜度為O（mlnn），破圈法則只與圖中邊的個數(shù)有關(guān)，時間復(fù)雜度為O（mlnm），當G中圈較少時，這兩種算法用破圈法比較好.Prim算法的計算復(fù)雜度和圖的邊樹無關(guān)，只和頂點的數(shù)目有關(guān)，其復(fù)雜度為O（n2），Prim算法和Kruskal算法分別適用于稠密圖和稀疏圖，但兩種算法都不能根據(jù)圖的頂點數(shù)、頂點的度數(shù)以及邊的分布情況自適應(yīng)地改變自身.參考文獻［5］中毛華提出的權(quán)矩陣算法考慮整個的時間復(fù)雜度為O（n3），我們今天改進了權(quán)矩陣算法，其復(fù)雜度為權(quán)矩陣算法的一半.

4 改進的權(quán)矩陣法求最大生成樹的應(yīng)用研究

下圖是我國某省幾個地區(qū)的高速公路圖，弧上標注的是兩地區(qū)之間的車流量，某年冬季因為大雪封路，需要盡快清除積雪，但由于時間有限，我們不能一次全部掃完，為了保證任意兩個地區(qū)都連通，并且保證車流總量達到最大，需要優(yōu)先清除哪些路段的積雪？

算法過程：先寫出無向圖的改進的鄰接矩陣如下，初始狀態(tài)令Q=?，ET=?，K=0

步驟（1）：不妨從主對角線以上找出最大元素a45=50，得到

步驟（2）：在A的主對角線以上第四、五列的沒有標注的元素中找出最大元素a56=18，得到Q={d ,e,f}，ET={( d,e),(e,f)} ，K=2，給元素a56=18標注*，此時

步驟（3），在A的主對角線以上第四、五、六列的沒有標注的元素中找出最大元素a34=20，得到Q={d ,e,f,c}，ET={( d,e),(e,f),(d,c)} ，K=3，給元素a34=20標注*，此時

步驟（4）：在A的主對角線以上第三、四、五、六列沒有標注的元素中找出最大元素a24=14，這一步得到Q={d ,e,f,c,b}，ET={( d,e),(e,f),(d,c),(b,d)} ，K=4，給元素a24=14標注*，此時

步驟（5）：在A的主對角線以上第二、三、四、五、六列的沒有標注的元素中找出最大元素a12=30，得到=5，給元素a12=30標注*，此時

算法結(jié)束.此時，ET={( d,e),(e,f),(d,c),(b,d),(a,b)}的導(dǎo)出子圖就是圖1的一個最大生成樹，如下圖虛線所示.

說明：改進的權(quán)矩陣算法也可以從主對角線以下找上述最大元素，不過此時我們是從權(quán)矩陣主對角線以下選取U中元素對應(yīng)行的除了標注外的最大元素.

5 結(jié)束語

生成樹算法在實際生活中有著廣泛的應(yīng)用，是圖論和離散數(shù)學(xué)的重要部分，最大生成樹可能不止一個，但不管利用哪種算法求出的最大生成樹的權(quán)值必然是相同的，本文在最小生成樹的矩陣算法的基礎(chǔ)上介紹了一種改進的矩陣算法，豐富了生成樹的相關(guān)理論，一般我們求稠密圖的最大生成樹用該算法比較簡單.