薛 瑞,劉宏兵，司倩楠

(信陽師范學院 計算機與信息技術學院, 河南 信陽 464000)

0 引言

最小生成樹(Minimum Spanning Tree，MST)是圖論研究中一個經典的問題，許多網絡優(yōu)化和運籌學問題都可以利用最小生成樹來解決.最小生成樹旨在賦權連通圖中尋找一些能到達各點而且邊權總和最小的優(yōu)化模型.近年來，國內外對最小生成樹的研究非?；钴S，這些研究主要集中在最小生成樹算法的改進及最小生成樹的應用兩方面.例如，文獻[1]提出了最小生成樹的DNA算法，文獻[2-4]分別提出了最小生成樹在聚類算法中的應用，文獻[5]提出了最小生成樹在圖像分割中的應用，文獻[6]提出了最小生成樹在圖像融合算法中的應用.Tewarie等[7]研究了最小生成樹在腦網絡分析中的應用，Ruiz等[8]研究了最小生成樹在密碼學中的應用，Ahmadi等[9]研究了如何應用最小生成樹使得網絡再配置中損失達到最小.

到目前為止，求解最小生成樹常用的算法有Kruskal算法[10]、Prim[11]算法和避圈法[12]等.當一個賦權的連通圖中多條邊的權值相同時,最小生成樹的形式可能不唯一.權值相同的最小生成樹涉及通信、網絡布線、道路交通等很多領域，然而在國內外眾多的研究成果中，這方面的研究幾乎沒有.本文基于Kruskal算法，針對權值相同的邊，提出了改進的最小生成樹算法.

1 最小生成樹的Kruskal算法

Kruskal算法是尋找最小生成樹的一種貪心算法，在算法的每一步，都從剩下的可用數據中做出一個最優(yōu)選擇，而且如果局部最優(yōu)(比如對于頂點a和與a鄰近的點)可以導致整體最優(yōu).

1.1 算法概述

給定連通帶權圖G，設G有n個點，m條邊.邊集E={e1，e2，…，em}.

Step1 選取最小權邊e1，置邊數i←1.

Step2i=n-1結束，否則轉Step3.

Step3 設已選擇邊為e1，e2，…，ei，在G中選取不同于e1，e2，…，ei的邊ei+1，使得{e1，e2，…，ei，ei+1}無回路且ei+1是滿足條件的最小邊.

Step4i←i+1，轉Step2.

1.2 算法分析

Kruskal算法常被用于求解邊稀疏的網絡最小生成樹問題，假設一個圖有n個點，該算法每次選擇n-1條邊，所使用的貪婪準則是從剩下的邊中選擇一條不會產生回路的權值最小的邊加入已選擇的邊的集合中，其時間復雜度為O(elog2e).當圖中存在兩條權值相同的邊時，利用Kruskal算法，如果保留其中的一條邊不會產生回路，但同時保留兩條會有回路時，算法會自動將第二條邊刪除，繼續(xù)在剩余的邊中尋找權值最小的邊.然而實際上，如果用刪除掉的那條邊代替保留生成樹中的那一條，有可能會得到另一棵生成樹.

因此，當圖中存在權值相同的邊時，利用Kruskal不能保證可以找到所有的最小生成樹.如圖1中賦權連通圖G1，利用Kruskal算法在Matlab中進行求解，結果只能得到一顆最小生成樹(v1,v3)，(v1,v4)，(v5,v6)，(v4,v6)，(v1,v7).

圖1 賦權連通圖G1Fig. 1 Weighted connected graph G1

而實際上相同權和的最小生成樹還有(v1,v3)，(v1,v4)，(v5,v6)，(v3,v5)，(v1,v7)與(v1,v3)，(v1,v4)，(v5,v6)，(v4,v6)，(v2,v4)及(v1,v3)，(v1,v4)，(v5,v6)，(v3,v5)，(v2,v4)等最小生成樹.

2 邊權相同的最小生成樹改進算法

針對圖中存在權值相同的邊時，Kruskal算法不能找到所有的最小生成樹，從而造成決策方案丟失的情況，提出改進的最小生成樹算法.

2.1 邊權相同的兩條邊

邊權相同的兩條邊在構造最小生成樹時共有以下4種分布情況:

①兩條邊均可保留，如圖G2中的邊(v1,v2)與邊(v2,v3).

②兩條邊只有1條可以保留，如圖G2中的邊(v3,v5)與邊(v3,v6)，根據Kruskal算法，在遍歷流程中保留邊(v3,v5)不會產生回路，但保留邊(v3,v6)會產生回路.

③兩條邊均不可保留，如圖G2中的邊(v1,v3)與邊(v1,v4)；在遍歷過程中，無論保留哪一條都會產生回路；

④兩條邊可任意保留一條，但不可同時保留，如圖G1中的邊(v4,v6)與邊(v3,v5),在遍歷過程中，無論保留哪一條都不會產生回路，但同時保留兩條邊會產生回路.

圖2 賦權連通圖G2Fig. 2 Weighted connected graph G2

利用Kruskal算法之所以不能找到所有權值最小的生成樹，是因為該算法中忽略了上述中的第④種情況中權值相同的邊對最小生成樹結果的影響.針對第④種狀況，以下定理成立.

定理1 賦權連通圖G的任意兩條權相同的兩條邊ei和ej，若ei與G中任意邊e構成回路，則ej也和e構成回路.

證明如圖3，根據Kruskal算法，首先將權為1，2，3的邊置于生成樹中，在剩下的邊中存在兩條權最小的邊(v3,v4)，(v5,v6).兩條邊任取一條置于樹中都不會產生回路，但若兩條邊都保留，則會產生回路.

在圖G中任取一條與(v3,v4)產生回路的邊，取法有兩種.

①在邊(v3,v4)，(v5,v6)圍成的回路內任取一條邊.如圖3，連接邊(v1,v5)，則該邊把由邊(v3,v4)，(v5,v6)圍成的回路v1→v3→v4→v5→v6→v1分成了兩個子回路v1→v5→v6→v1與v1→v3→v4→v5→v1.

圖3 賦權連通圖GFig. 3 Weighted connected graph G

②在邊(v3,v4)，(v5,v6)圍成的回路外任取一條邊.如圖3，連接邊(v2，v4)，則邊(v2，v4)與邊(v2，v3)、(v3，v4)圍成一個回路v2→v4→v3→v2，去除邊(v3，v4)，邊(v2，v4)仍然可以和邊(v5，v6)圍成回路v1→v6→v5→v4→v2→v3→v1.證畢.

由定理1，可得定理2成立.

定理2 賦權連通圖G的任意兩條權相同的兩條邊ei和ej，若ei與G中任意邊e不構成回路，則ej也與e不構成回路.

設T0是已求得的一棵最小生成樹，在最小生成樹不唯一的情況下，存在其他的生成樹T，稱T-T0得到的邊集長度為距離[6](這里的長度是指集合中元素的個數).結合定理1與定理2得出以下結論成立.

定理3 賦權連通圖G有且只有兩條權相同的兩條邊ei和ej，其中ei,ej的分布如上所述的第④種狀況，設T1是包含邊ei的最小生成樹，T2是包含邊ej的最小生成樹，則T1-T2=T2-T1.

一般情況下，若賦權連通圖G中權值為w1的邊有n1條，權值為w2的邊有n2條,…,wt的邊有nt條,且權值相同得邊均如上述的第④種分布狀況，則圖G的最小生成樹共有n1×n2×…×nt條.

2.2 改進算法的步驟

設G=〈V,E〉是一個簡單的賦權連通圖，其中|V|=n并且每條邊都賦值為一個正實數w(e).

Step0 令i=1,j=0,T=φ.把G的邊按照權由小到大排列，即w(e1)≤w(e2)≤…≤w(em).

Step1 判斷T∪{ei}是否含圈.若不含圈,轉Step3.若含圈，驗證ei=ei-1是否成立，若ei≠ei-1，轉Step2;若ei=ei-1,驗證T-{ei-1}∪{ei}是否含圈.若含圈，轉Step2;若不含圈，則T=T或T=T-{ei-1}∪{ei}.

Step2 令i=i+1.若i≤m,轉Step1;否則結束,此時G不連通,所以沒有最小樹.

Step3 令T=T∪{ei},j=j+1.若j=n-1,則結束，T是最小樹;否則，轉Step1.

3 應用實例

以信陽師范學院交通路線圖作為網絡拓撲圖.隨著校園規(guī)模的不斷擴大，現要對校園的通訊光纜進行重新改造.為了施工的便利，光纜線通常是沿著道路兩端鋪設的.把信陽師范學院每個道路交叉口當成一個結點，各點之間的連線表示兩交叉口之間的距離(單位：m).如圖4所示.

根據改進的最小生成樹算法原理，最優(yōu)的施工方案有：

T1:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v1,v4)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v19,v21),(v7,v10)，(v2,v3).

T2:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v1,v4)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v18,v21),(v7,v10)，(v2,v3).

T3:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v2,v5)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v19,v21),(v7,v10)，(v2,v3).

T4:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v2,v5)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v18,v21),(v7,v10)，(v2,v3).

T5:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v1,v4)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v19,v21),(v8,v9)，(v2,v3).

T6:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v1,v4)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v18,v21),(v8,v9)，(v2,v3).

T7:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v2,v5)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v19,v21),(v8,v9)，(v2,v3).

T8:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v2,v5)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v18,v21),(v8,v9)，(v2,v3).

圖4 校園交通網絡拓撲圖Fig. 4 The graph of campus transport network

4 結束語

本文針對當賦權圖中存在多條權值相同的邊時，對最小生成樹的分布狀況進行了深入的研究.實驗結果表明，該算法可以找到所有的最小生成樹，繼而可為決策者提供更多的優(yōu)化方案.