基于鄰接矩陣的近似Prim算法解決無向圖特定問題

王 敏，楊秀香，李云飛

(渭南師范學院a.網(wǎng)絡(luò)安全與信息化學院;b.數(shù)理學院，陜西 渭南714099)

用計算機解決一個具體問題，大致需要經(jīng)過下列幾個步驟:首先要從具體問題中抽象出一個適當?shù)臄?shù)學模型，然后設(shè)計一個解此數(shù)學模型的算法，最后編出程序，進行測試、調(diào)試直至得到最終解答.尋求數(shù)學模型的實質(zhì)是分析問題，從中提取操作對象，然后用數(shù)學語言描述它們之間的關(guān)系［1］.算法必須采用與之相適應(yīng)的數(shù)據(jù)結(jié)構(gòu)，才能有效地計算所求解的問題［2］.

數(shù)據(jù)的邏輯結(jié)構(gòu)通常有集合、線性、樹和圖四類.數(shù)據(jù)在計算機中有順序和鏈式兩種存儲結(jié)構(gòu).算法的設(shè)計取決于數(shù)據(jù)選定的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)［1］.本文將研究消除無向連通圖中構(gòu)成環(huán)路的冗余邊的算法.

1 圖的概念

圖的邏輯結(jié)構(gòu)可形式化定義為:Graph=(V，R).其中:V={x|x∈dataobject}，R={VR}，VR={＜x，y＞|P(x，y)∧ (x，y∈V)}.V是頂點的有窮非空集合，VR是頂點間關(guān)系的集合，P(x，y)代表頂點x和y具有某種謂詞關(guān)系［1］.在本文所討論的范圍內(nèi)，謂詞P(x，y)可表示為頂點x和y之間存在一條相關(guān)邊.

2 問題描述

待求解問題描述為:對于任意一個無向連通圖G=(V，{E})，G中可能含有環(huán)，要求編寫算法實現(xiàn)刪除G中的某些冗余邊，使得G中不含環(huán).

算法要求:編寫出的算法所刪除的邊數(shù)必須最少.

3 數(shù)據(jù)結(jié)構(gòu)分析

在圖的邏輯結(jié)構(gòu)中，任意兩個頂點之間的關(guān)系不存在先后順序，因而不能采用一維數(shù)組的線性結(jié)構(gòu)來存儲;另一方面，如果采用鏈式存儲結(jié)構(gòu)，由于圖中各頂點的度不同，最小度數(shù)和最大度數(shù)可能相差較大，若按頂點的最大度數(shù)設(shè)計鏈表的指針域，則會造成存儲單元的浪費.反之，若根據(jù)各頂點的度分別設(shè)計不同的鏈表結(jié)點，則又增加了操作復雜性.因此，圖的存儲結(jié)構(gòu)需要特殊設(shè)計.

3.1 存儲結(jié)構(gòu)分析與設(shè)計

常用的圖的存儲結(jié)構(gòu)有鄰接矩陣、鄰接表、十字鏈表和鄰接多重表，具體選用哪種取決于圖的特點和所定義的運算.

鄰接矩陣是圖的順序存貯，該結(jié)構(gòu)容易判斷圖中兩個頂點是否相關(guān)，易于實現(xiàn)求圖中各頂點的度的算法.該存儲結(jié)構(gòu)的缺點是不適用于存儲頂點多而邊較少的圖.

鄰接表是圖的鏈式存儲［3］.頂點的順序存儲便于實現(xiàn)訪問任意頂點的相關(guān)邊的算法，因而求圖中各頂點的度的算法也易于實現(xiàn).存儲有向圖時，某個頂點指向的單鏈表中，各邊結(jié)點都是以該頂點為弧尾的弧，因而求頂點的出度算法易于實現(xiàn)，而求頂點入度的算法則需要遍歷全部單鏈表中的邊結(jié)點，此時仍需要借助逆鄰接表存儲結(jié)構(gòu)來實現(xiàn).由此可見，鄰接表存儲結(jié)構(gòu)在不考慮空間浪費的情況下更適用于存儲無向圖.

十字鏈表存儲結(jié)構(gòu)專為存儲有向圖設(shè)計，不適用于存儲無向圖，此時無需同時設(shè)計有向圖的鄰接表和逆鄰接表，但較多的指針域仍然容易造成涉及頻繁修改弧之類的算法操作的復雜度提升.

在鄰接多重表中，邊結(jié)點結(jié)構(gòu)類似有向圖的十字鏈表存儲結(jié)構(gòu)，唯一的邊結(jié)點消除了無向圖的邊結(jié)點冗余存儲，但相應(yīng)增加的指針域也使得涉及對邊結(jié)點單鏈表進行遍歷之類的算法操作復雜度增大.

綜上對比分析，本文所討論的無向連通圖，其存儲結(jié)構(gòu)宜選擇較為簡單常用的鄰接矩陣存儲方式.

3.1.1 鄰接矩陣存儲結(jié)構(gòu)定義

鄰接矩陣表示法也稱數(shù)組表示法，它用一個一維數(shù)組存儲數(shù)據(jù)元素(頂點)的信息，一個二維數(shù)組(稱為鄰接矩陣)存儲數(shù)據(jù)元素間關(guān)系(邊或弧)的信息［4］.

具有n個頂點的圖G的鄰接矩陣A為n×n的方陣，其形式化定義如下:

其中:VR為頂點間關(guān)系的集合;有直接邊的兩個頂點vi和vj在矩陣中對應(yīng)的行列交叉點處取值為1.

3.1.2 鄰接矩陣的壓縮存儲

由于無向圖G的鄰接矩陣為對稱方陣，要將一條邊記錄為已被訪問或刪除，需要在該邊依附的兩個鄰接點所在的行同時進行操作.這顯然存在重復操作，因此，可考慮只存儲G的鄰接矩陣的下三角(i≥j)，將n2個元壓縮存儲到n(n+1)/2個元的空間中.

假設(shè)以一維數(shù)組SA［n(n+1)/2］作為G的鄰接矩陣存儲結(jié)構(gòu)，則SA［k］和矩陣元A［i，j］之間存在如下對應(yīng)關(guān)系:

這樣，對于任意給定的一組下標(i，j)，均可在 SA 中找到矩陣元 A［i，j］.反之，對所有的 k=0，1，2，…，n(n+1)/2－1，都能確定 SA［k］中的元在矩陣中的位置(i，j)［1］.

3.1.3 鄰接矩陣存儲結(jié)構(gòu)的C語言描述

圖的壓縮存儲的鄰接矩陣存儲結(jié)構(gòu)可用C語言描述如下:

#define MAX_VER 50 //最大頂點個數(shù)

typedef structArcNode{

intadj;//取值為1或0

InfoType info;//邊上的其他信息

}ArcNode;

typedef struct{

VerType vexs［MAX_VER］; //頂點向量

ArcNode arcs［MAX_VER(MAX_VER+1)/2］;//壓縮存儲的鄰接矩陣

intvexnum，arcnum; //當前頂點數(shù)和邊數(shù)

}MatrixGraph;

3.2 算法分析與設(shè)計

3.2.1 算法設(shè)計思路

通過類似Prim算法求解圖的生成樹，在求解過程中記錄下已選中的各邊，并在求得G的生成樹后，將G中未被記錄的邊(即不屬于生成樹中的邊)刪除.

3.2.2 思路分析

Prim算法可稱之為“加點法”.初始狀態(tài)G的生成樹GT的頂點集VT中只含起點，邊集TE為空.隨后，從G的頂點集VG中選擇同VT中的頂點相關(guān)，但不屬于VT的點加入VT，同時將鄰接點的相關(guān)邊也加進TE.重復該過程直到VT=VG時算法結(jié)束.

Prim算法求解的是帶權(quán)圖的最小生成樹，因此在選取符合條件的邊時，是按照邊的權(quán)值非遞減順序進行的.本文介紹的待求解問題中并未說明圖G是否為帶權(quán)圖，且需要進行的操作只是刪除某些冗余邊，而又未指明待刪邊的權(quán)值相關(guān)性，因此，可將其視為針對非帶權(quán)無向連通圖的一個特定算法.這樣，在采用Prim算法的思路選取邊時，根據(jù)鄰接矩陣存儲結(jié)構(gòu)的特點，只需順序選擇VT中頂點的第一條未標記的相關(guān)邊即可.

這種近似Prim算法在順序選擇VT中頂點的各條未標記的相關(guān)邊時，如何選擇VT中作為起點的頂點是需要首先考慮的問題.如果按照頂點序號次序進行選擇，則在算法實現(xiàn)上增加了搜索確定起始頂點的時間耗費.因此，可采用廣度優(yōu)先搜索遍歷的思路來實現(xiàn).廣度優(yōu)先搜索遍歷即從G中某個起始頂點出發(fā)，訪問該頂點，然后依次訪問該頂點的所有未被訪問的鄰接點，再根據(jù)各鄰接點被訪問的先后次序，分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，直到圖中所有已被訪問頂點的鄰接點都被訪問到為止［1］.

3.2.3 算法的C語言描述

設(shè)無向連通圖G采用前述MatrixGraph存儲結(jié)構(gòu)，且G中有n個頂點v1～vn，分別存儲在vexs［0..n－1］單元，其arcs數(shù)組的數(shù)組元均已初始化.為保證圖中各頂點在遍歷過程中僅被訪問一次，可以通過設(shè)置一個全局的訪問標志數(shù)組 visited［n］來實現(xiàn)，其初始值均為 0，一旦頂點 vi被訪問，則置 visited［i］為 1［1，5］.不失一般性，假設(shè)從頂點vi(vexs［i］，i=0～n－1)出發(fā)構(gòu)造G的生成樹.由于G為非帶權(quán)圖，因此不必附設(shè)輔助數(shù)組closedge(用以記錄鄰接點分別在VT和VG－VT的具有最小權(quán)值的邊).在得到GT后，將屬于EG但不屬于TE的邊從EG中刪除.算法的C語言描述如下:

intvisited［MAX_VER］;//訪問標志數(shù)組

voidBreadthFirstSearch(MatrixGraph*G，int i)

{InitQueue(Q);

visited［i］=1;

EnQueue(Q，i);

while(!EmptyQueue(Q))

{DeleteQueue(Q，k);

for(j=0;j＜G－＞vexnum;j++)

if(!visited［j］＆＆G－＞arcs［k(k+1)/2+j］.adj==1)

{G－＞arcs［k(k+1)/2+j］.info=1;//記錄被訪問邊

visited(j)=1;

EnQueue(Q，j);}//End－of－if

}//End－of－while

}//End［1］

void DeleteRedundentEdge(MatrixGraph*G)

{BreadthFirstSearch(G，0);

for(i=0;i＜G－＞vexnum;i++)

for(j=0;j＜i;j++)

{k=i(i+1)/2+j;

if(G－＞arcs［k］.adj==1＆＆G－＞arcs［k］.info==0)

G－＞arcs［k］.adj=0;//刪除未被記錄的邊

}//End－of－for

}//End

4 算法性能評價

本文介紹的消除無向連通圖中冗余邊的算法通過函數(shù)DeleteRedundentEdge()最終實現(xiàn)，該函數(shù)的函數(shù)體中包括兩條基本語句:一是對函數(shù)BreadthFirstSearch()的調(diào)用，二是一條雙重for循環(huán)語句.函數(shù)BreadthFirstSearch()完成對G的廣度優(yōu)先搜索遍歷，遍歷結(jié)束得到G的廣度優(yōu)先搜索生成樹.雙重for循環(huán)完成刪除不屬于生成樹中的邊，即構(gòu)成回路的冗余邊.該算法采用了鄰接矩陣存儲結(jié)構(gòu)，查找每個頂點的鄰接點所需時間為O(n(n+1)/2)=O(n2)，其中n為圖中的頂點數(shù).雙重for循環(huán)語句的循環(huán)體執(zhí)行次數(shù)為O(n(n－1)/2)=O(n2).將頂點數(shù)n看作問題的規(guī)模，則隨著問題的規(guī)模n逐漸增大，算法的時間復雜度約為T(n)=O(n2).

該算法除了函數(shù)本身和圖G所占空間外，引入了一個一維數(shù)組visited［MAX_VER］的輔助空間，從而算法的空間復雜度為線性階，即S(n)=O(n).

［1］嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)［M］.北京:清華大學出版社，2002.

［2］王衛(wèi)東.數(shù)據(jù)結(jié)構(gòu)學習指導［M］.西安:西安電子科技大學出版社，2004.

［3］江濤.數(shù)據(jù)結(jié)構(gòu)［M］.北京:中央廣播電視大學出版社，1995.

［4］王昆侖，李紅.數(shù)據(jù)結(jié)構(gòu)與算法［M］.北京:中國鐵道出版社，2007.

［5］耿國華.數(shù)據(jù)結(jié)構(gòu)—C語言描述［M］.西安:西安電子科技大學出版社，2005.