王 敏，楊秀香，李云飛

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

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

數(shù)據(jù)的邏輯結(jié)構(gòu)通常有集合、線性、樹和圖四類.數(shù)據(jù)在計(jì)算機(jī)中有順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu).算法的設(shè)計(jì)取決于數(shù)據(jù)選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(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是頂點(diǎn)的有窮非空集合，VR是頂點(diǎn)間關(guān)系的集合，P(x，y)代表頂點(diǎn)x和y具有某種謂詞關(guān)系［1］.在本文所討論的范圍內(nèi)，謂詞P(x，y)可表示為頂點(diǎn)x和y之間存在一條相關(guān)邊.

2 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1.2 鄰接矩陣的壓縮存儲

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

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

這樣，對于任意給定的一組下標(biāo)(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 //最大頂點(diǎn)個(gè)數(shù)

typedef structArcNode{

intadj;//取值為1或0

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

}ArcNode;

typedef struct{

VerType vexs［MAX_VER］; //頂點(diǎn)向量

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

intvexnum，arcnum; //當(dāng)前頂點(diǎn)數(shù)和邊數(shù)

}MatrixGraph;

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

3.2.1 算法設(shè)計(jì)思路

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

3.2.2 思路分析

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

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

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

3.2.3 算法的C語言描述

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

intvisited［MAX_VER］;//訪問標(biāo)志數(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 算法性能評價(jià)

本文介紹的消除無向連通圖中冗余邊的算法通過函數(shù)DeleteRedundentEdge()最終實(shí)現(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)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O(n(n+1)/2)=O(n2)，其中n為圖中的頂點(diǎn)數(shù).雙重for循環(huán)語句的循環(huán)體執(zhí)行次數(shù)為O(n(n－1)/2)=O(n2).將頂點(diǎn)數(shù)n看作問題的規(guī)模，則隨著問題的規(guī)模n逐漸增大，算法的時(shí)間復(fù)雜度約為T(n)=O(n2).

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

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

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

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

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

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