課件數(shù)據(jù)結(jié)構(gòu)教學(xué)圖

7.1圖的基本概念和術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷和求圖的連通分量7.4圖的生成樹7.5最短路徑7.6有向無環(huán)圖及應(yīng)用7.7圖的第7章圖返回主目錄7.1圖的基本概念和術(shù)語第7章圖返回主目錄第7章圖7.1圖的基本概念和術(shù)語

7.1.1圖的基本概念圖G由集合V和E組成,記為G=(V,E),圖中的結(jié)點又稱為頂點,其中V是頂點的非空有窮集合,相關(guān)的頂點的偶對稱為邊,E是邊的有窮集合。

若圖中的邊是頂點的有序?qū)?則稱此圖為有向圖。有向邊又稱為弧,通常用尖括弧表示一條有向邊,〈vi,vj〉表示從頂點vi到vj的一段弧,vi稱為邊的始點(或尾頂點),vj稱為邊的終點(或頭頂點),〈vi,vj〉和〈vj,vi〉代表兩條不同的弧。第7章圖7.1圖的基本概念和術(shù)語

若圖中的邊是頂點的無序?qū)?則稱此圖為無向圖。通常用圓括號表示無向邊,(vi,vj)表示頂點vi和vj間相連的邊。在無向圖中(vi,vj)和(vi,vj)表示同一條邊,如果頂點vi

、vj之間有邊(vi,vj),則vi

、vj互稱為鄰接點。圖7.1給出兩個圖G1和G2,其中G1是無向圖,G2是有向圖。在有向圖中用箭頭表示弧的方向,箭頭從始點指向終點。圖G1是一個無向圖的例子。在圖G1中,V={v1,v2,v3,v4},E={(v1,v2),(v2,v3),(v1,v3),(v1,v4),(v3,v4)}。而(v2,v1)與（v1,v2

）表示同一條邊,(v2,v3)與(v3,v2)也表示同一條邊,等。若圖中的邊是頂點的無序?qū)?則稱此圖為無向課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-

圖G2是一個有向圖的例子,在圖G2中V={v1,v2,v3,},E={〈v1,v2

〉,〈v1,v3

〉,〈v2,v3,〉,〈v3,v2

〉}。而〈v3,v2

〉與〈v2,v3,〉表示兩條不同的邊。對于圖G=(V,E),G′=(V′,E′),若有V′∈V,E′∈E,則稱圖G′是G的一個子圖。圖7.2給出了G3與其子圖G3′。在下面的討論中不考慮頂點到自身的邊,也不允許一條邊(或弧)在圖中重復(fù)出現(xiàn)。因此有n個頂點的無向圖最大邊數(shù)為C2n=n(n-1)/2,這樣的圖稱為無向完全圖；有向圖中最多可能有A2n=n(n-1)條弧,這樣的圖稱為有向完全圖。圖G2是一個有向圖的例子,在圖G2中V課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-

7.1.2路徑和回路所謂頂點vp

到頂點vq之間的路徑,是指頂點序列vp,vi1

,vi2

,…,vim,vq,其中（vp,vi1）,（vi1

,vi2）,…,（vim,vq

）分別為圖中的邊。路徑上邊的數(shù)目稱為路徑長度。圖7.3所示的無向圖中,頂點v1(注：v1在圖中用數(shù)字1表示，其余類同)到頂點v5的路徑有兩條,分別為v1,v2,v3,v4與v1,v5,v4,路徑長度分別為3和2。如果路徑的起點和終點相同(即vp=vq),則稱此路徑為回路或環(huán)。序列中頂點不重復(fù)出現(xiàn)的路徑稱為簡單路徑,圖7.3所示的v1到v5的兩條路徑都為簡單路徑。除第一頂點與最后一個頂點之外,其它頂點不重復(fù)出現(xiàn)的回路為簡單回路或者簡單環(huán)。7.1.2路徑和回路課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-

7.1.3連通圖若從頂點vi到頂點vj(i≠j)有路徑,則vi和vj是連通的。如果無向圖中任意兩個頂點vi和vj都是連通的,則稱無向圖是連通的。無向圖中極大連通子圖稱為連通分量。圖7.2中的G3有兩個連通分量,見圖7.4(a)。對于有向圖來說,圖中任意一對頂點vi和vj(i≠j)均有從vi到vj及從vj到vi的有向路徑,則稱該有向圖是強(qiáng)連通的。有向圖中的極大強(qiáng)連通子圖稱為該有向圖的強(qiáng)連通分量。圖7.1中G2不是強(qiáng)連通的,但它有一個強(qiáng)連通分量,見圖7.4(b)。7.1.3連通圖課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-

7.1.4頂點的度頂點的度是指依附于某頂點vi的邊數(shù),通常記為TD(vi)。在有向圖中,要區(qū)別頂點的入度和出度的概念。所謂頂點vi的入度是指以vi為終點的弧的數(shù)目,記為ID(vi);所謂頂點vi的出度是指以vi為始點的弧的數(shù)目,記為OD(vi)。顯然

TD(vi)=ID(vi)+OD(vi)例如,在G1中頂點v1的度TD(v1)=3,在G2中頂點v2的入度ID(v2)=2,出度OD(v2)=1,TD(v2)=3。可以證明,對于具有n個頂點、e條邊的圖,頂點vi的度TD(vi)與頂點的個數(shù)及邊的數(shù)目滿足關(guān)系:7.1.4頂點的度7.2圖的存儲結(jié)構(gòu)

7.2.1鄰接矩陣圖的鄰接矩陣表示法是用一個二維數(shù)組來表示圖中頂點之間的相鄰關(guān)系。設(shè)圖G=(V,E)有n(n≥1)個頂點,則G的鄰接矩陣是按如下定義的n階方陣:

aij=1若(vi,vj)或<vi,vj>∈E(G)

0反之例如,圖7.1中的G1、G2的鄰接矩陣分別表示為A1和A2,矩陣的行、列號對應(yīng)于圖中結(jié)點的號。7.2圖的存儲結(jié)構(gòu)7.2.1鄰接矩陣

從圖的鄰接矩陣表示法中很容易看出圖的一些特性,這種表示方法具有以下特點:

(1)無向圖的鄰接矩陣一定是對稱的,而有向圖的鄰接矩陣不一定對稱。因此,用鄰接矩陣來表示一個具有n個頂點的有向圖時需要n2個單元來存儲鄰接矩陣;對有n個頂點的無向圖則只需存入上(下)三角形,故只需n(n+1)/2個單元。0111101011011010A2=011001010從圖的鄰接矩陣表示法中很容易看出圖的一些特性,7.2.2鄰接鏈表圖的鄰接鏈表存儲結(jié)構(gòu)是一種順序分配和鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲結(jié)構(gòu)。它包括兩個部分,一部分是鏈表,另一部分是向量。在鏈表部分中共有n個鏈表(n為頂點數(shù)),即每個頂點對應(yīng)一個鏈表。每個鏈表由一個表頭結(jié)點和若干個表結(jié)點組成。表頭結(jié)點用來指示第i個頂點vi所對應(yīng)的鏈表;表結(jié)點由頂點域(vex)和鏈域(link)所組成。頂點域指示了與vi相鄰接的頂點的序號,所以一個表結(jié)點實際上代表了一條依附于vi的邊,鏈域指示了依附于vi的下一條邊的結(jié)點。因此,第i個鏈表就表示了依附于頂點vi的所有的邊。對于有向圖來說,第i個鏈表就表示了從vi發(fā)出的所有的弧。7.2.2鄰接鏈表

鄰接鏈表的另一部分是一個向量,用來存儲n個結(jié)點。向量的下標(biāo)指示了頂點的序號,這樣就可以隨機(jī)地訪問任一個頂點的鏈表。例如,對于圖7.1中的G1和G2,其鄰接鏈表如圖7.5所示。defineMaxSize20[WB]

typedefstructArcNode{

intadjvex;/*該弧所指向的頂點的位置*/

structArcNode*nextarc;/*指向下一條弧的指針*/

InfoTypeinfo/*該弧相關(guān)信息的指針*/

}ArcNode;鄰接鏈表的另一部分是一個向量,用來存儲n個結(jié)課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-typedefstructVnode{

VertexTypedata;/*頂點信息*/

ArcNode*firstarc;/*指向第一條依附該頂點的弧的指針*/

}Vnode,AdjList［MaxSize］;

typedefstruct{

AdjListvertices;

intvexnum,arcnum;

}ALGraph;[HT5SS]typedefstructVnode{

若無向圖有n個頂點,e條邊,則鄰接鏈表需n個表頭結(jié)點和2e個表結(jié)點,每個表結(jié)點有兩個域。顯然,對于邊很少的圖,用鄰接鏈表比用鄰接矩陣要節(jié)省存儲單元。在無向圖的鄰接鏈表中,第i個鏈表中的表結(jié)點數(shù)就是頂點vi的度數(shù)。在有向圖的鄰接鏈表中,第i個鏈表中的表結(jié)點數(shù)就是頂點vi的出度。若要求vi的入度,必須對鄰接鏈表進(jìn)行掃描,統(tǒng)計點域的值為i的表結(jié)點的數(shù)目,顯然,這是很費(fèi)時間的。為了便于確定有向圖中頂點的入度,可以另外再建立一個逆鄰接鏈表,使第i個鏈表表示以vi為頭的所有的弧。圖7.6即為圖G2的逆鄰接表。若無向圖有n個頂點,e條邊,則鄰接鏈表需課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-7.3圖的遍歷和求圖的連通分量

7.3.1圖的建立由上節(jié)知道,可采用鄰接矩陣或鄰接鏈表作為圖的存儲結(jié)構(gòu)。下面給出無向圖的鄰接矩陣的形式說明及其建立算法7.1。算法7.1

typedefcharvextype;/*頂點的數(shù)據(jù)類型*/

typedefstruct

{vextypevexs［n+1］;

intarcs［n+1］［n+1］;〖ZK)〗

}graph;7.3圖的遍歷和求圖的連通分量7.3.1voidcreatgraph(graph*ga)/*建立無向圖*/

{inti,j,k;

for(i=1;i<n;i++)ga->vexs［i］=getchar();/*讀入頂點信息*/

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)ga->arcs［i］［j］=0;/*鄰接矩陣初始化*/

for(k=1;k<=e;k++)/*讀入e條邊*/

{scanf("%d%d",&i,&j);ga->arcs［i］［j］=1;

ga->arcs［j］［i］=1;

}}/*creatgraph*/voidcreatgraph(graph*ga)

7.3.2圖的遍歷從圖中某一頂點出發(fā)訪遍其余頂點,且使每一頂點僅被訪問一次,這一過程稱為圖的遍歷。遍歷圖的基本方法有兩種:深度優(yōu)先搜索和廣度優(yōu)先搜索。這兩種方法都適用于有向圖和無向圖。因為圖的任一頂點都可能和其余頂點相鄰接,因此在遍歷過程中,可能會多次訪問某個頂點。為了避免這種情況,要記下每個已訪問過的頂點,一般可增設(shè)一個輔助數(shù)組visited［n］,每個visited［i］的初值置為零。一旦頂點vi被訪問,就將visited［i］置為1。

1.連通圖的深度優(yōu)先搜索遍歷7.3.2圖的遍歷

連通圖的深度優(yōu)先搜索遍歷類似于樹的先根遍歷,其基本思想如下:假定圖中某個頂點v1為出發(fā)點,首先訪問出發(fā)點然后選擇一個v1的未訪問的鄰接點v2,以v2為新的出發(fā)點繼續(xù)進(jìn)行深度優(yōu)先搜索,直至圖中所有頂點都被訪問過。顯然,圖的深度優(yōu)先搜索是一個遞歸過程。現(xiàn)以圖7.7(a)為例說明深度優(yōu)先搜索過程。假定v1是出發(fā)點,首先訪問v1

。因v1有兩個鄰接點v2

、v3均未被訪問過,可以選擇v2作為新的出發(fā)點,訪問v2之后,再找v2的未訪問過的鄰接點。同v2鄰接的有v1

、v4、v5,其中v1已被訪問過,而v4

、v5尚未被訪問過,可以選擇v4作為新的出發(fā)點。連通圖的深度優(yōu)先搜索遍歷類似于樹的先根遍歷,課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-

重復(fù)上述搜索過程,繼續(xù)依次訪問v8、v5

。訪問v5之后,由于與v5相鄰的頂點均已被訪問過,搜索退回到v8

。由于v8

、v4

、v2都是已被訪問的鄰接點,所以搜索過程連續(xù)地從vv8退回到v4,再退回到v2,最后退回到v1

。這時選擇v1的未被訪問過的鄰接點v3,繼續(xù)往下搜索,依次訪問v3

、v6、v7,從而遍歷了圖中全部頂點。在這個過程中得到的頂點的訪問序列為

v1→v2→v4→v8→v5→v3→v6→v7

因為深度優(yōu)先搜索遍歷是遞歸定義的,故容易寫出其遞歸算法。下面以鄰接矩陣作為圖的存儲結(jié)構(gòu)給出具體算法。重復(fù)上述搜索過程,繼續(xù)依次訪問v8、v5算法7.2

intvisited［MaxSize］,n;/*訪問標(biāo)志數(shù)組*/voiddfstraverse(GraphG,intv)

{/*對圖G作深度優(yōu)先遍歷*/

for(v=0;v<G.vexnum;++v)visited［v］=0;/*訪問標(biāo)志數(shù)組初始化*/

for(v=0;v<G.vexnum;++v)

if(![KG-*2]visited［v］)dfs(G,v);/*對尚未訪問的頂點調(diào)用dfs*/

}/*dfstraverse*/算法7.2voiddfs(GraphG,intv)

{/*從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G*/

visited［v］=1;printf("%d",v);/*訪問第v個頂點*/

for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))

f(!visited［w］)dfs(G,w);/*對v的尚未訪問的鄰接頂點w遞歸調(diào)用dfs*/

}/*dfs*/voiddfs(GraphG,intv)

由上述可知,遍歷圖的過程實質(zhì)上是對每個頂點搜索其鄰接點的過程。故用鄰接矩陣表示圖時,搜索一個頂點的所有鄰接點需花費(fèi)O(n)時間,則從n個頂點出發(fā)搜索的時間應(yīng)為O(n2),即dfs算法的時間復(fù)雜度是(n2);如果使用鄰接鏈表來表示圖時,其dfs算法的時間復(fù)雜度為O(n+e),此處e為無向圖中邊的數(shù)目或有向圖中弧的數(shù)目。

2.連通圖的廣度優(yōu)先搜索遍歷連通圖廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷,其基本思想是:從圖中某個頂點vi出發(fā),在訪問了vi之后依次訪問vi所有鄰接點;然后分別從這些鄰接點出發(fā)按廣度優(yōu)先搜索遍歷圖的其它頂點,直至所有頂點都被訪問過。由上述可知,遍歷圖的過程實質(zhì)上是對每個頂點

下面以圖7.7(a)中G圖為例說明廣度優(yōu)先搜索的過程。首先從起點v1出發(fā)訪問v1。v1有兩個未曾訪問的鄰接點v2和v3,先訪問v2,再訪問v3;然后再先訪問v2的未曾訪問過的鄰接點v4

、v5及v3的未曾訪問過的鄰接點v6和v7,最后訪問v4的未曾訪問過的鄰接點v8

。至此圖中所有頂點均已被訪問過。得到的頂點訪問序列為:

v1→v2→v3→v4→v5→v6→v7→v8

在廣度優(yōu)先搜索中,若對x的訪問先于y,則對x鄰接點的訪問也先于對y鄰接點的訪問。因此,可采用隊列來暫存那些剛被訪問過,但可能還有未訪問的鄰接點的頂點?，F(xiàn)在,我們以鄰接矩陣作為圖的存儲結(jié)構(gòu),給出廣度優(yōu)先搜索遍歷算法。下面以圖7.7(a)中G圖為例說明廣度優(yōu)先搜算法7.4Voidbfs(intk)/*從vk出發(fā)廣度優(yōu)先遍歷圖Ｇ,Ｇ用鄰接矩陣表示*/

{r=0;f=0;/*置空隊列qu,f和r分別是頭指針和尾指針*/printf("%c\n",g.vexs［k］);/*訪問出發(fā)點vk+1*/visited［k］=1;/*標(biāo)記vk已訪問過*/

r++;qu［r］=k;/*已訪問過的頂點（序號）入隊列*/

while(r![KG-*2]=f)/*隊非空時執(zhí)行*/

{f++;i=qu［f］;/*隊頭元素序號出隊列*/

for(j=1;j<=n;j++)算法7.4if((g.arcs［i］［j］==1)&&((!visited［j］))

{printf("%c\n",g.vexs［j］;/*訪問vi的未曾訪問的鄰接點vj*/

visited［j］=1;

r++;qu［r］=j;/*訪問過的頂點入隊列*/

}/*if*/

}/*while*/

}/*bfs*/if((g.arcs［i］［j］==1)&&((

7.3.3求圖的連通分量如果要遍歷一個非連通圖,則需多次調(diào)用dfs或bfs。每一次都得到一個連通分量;調(diào)用dfs或bfs的次數(shù)就是連通分量的個數(shù)。因此很容易寫出非連通圖的遍歷算法和計算一個圖的連通分量的算法。下面給出以鄰接矩陣為存儲結(jié)構(gòu),通過調(diào)用深度優(yōu)先搜索算法實現(xiàn)的計算連通分量的算法。算法7.5

voidcomponent()

{count=0;

for(i=1;i<=n;i++)

visited［i］=0;/*初始化標(biāo)志數(shù)組*/7.3.3求圖的連通分量for(i=1;i<=n;i++)

{if(

{count=count+1;

dfs(i);/*從頂點vi+1出發(fā)遍歷一個連通分量*/

printf(″compend\n″);

}/*if*/

}/*for*/

printf(″Toyalcomponents:%d″,count);

}/*component*/for(i=1;i<=n;i++)

在此算法中,若將dfs換成bfs亦可,改換后的算法即是通過調(diào)用廣度優(yōu)先搜索算法實現(xiàn)的計算連通分量的算法。對圖7.2所示的非連通圖G3,執(zhí)行算法component時,分別調(diào)用dfs(1)和dfs(6),可求出兩個連通分量:

v1,v2,v3,v4,v5compend

v6,v7compend

TotalComponents:2因為一旦調(diào)用了dfs(i)之后,頂點vI即被做上了訪問標(biāo)記,而對每個頂點v1,dfs(i)最多只能被調(diào)用一次,因此,算法component中調(diào)用及內(nèi)部遞歸調(diào)用自己,其次數(shù)仍是n,故算法的時間復(fù)雜度是O(n2)。在此算法中,若將dfs換成bfs亦可,改7.4圖的生成樹

7.4.1生成樹的概念設(shè)圖G=(V,E)是個連通圖,當(dāng)從圖任一頂點出發(fā)遍歷圖G時,將邊集E(G)分成兩個集合A(G)和B(G)。其中A(G)是遍歷圖時所經(jīng)過的邊的集合,B(G)是遍歷圖時未經(jīng)過的邊的集合。顯然,G1=(V,A)是圖G的子圖。我們稱子圖G1是連通圖G的生成樹。圖的生成樹不是唯一的。如對圖7.7中的圖G,當(dāng)按深度和廣度優(yōu)先搜索法進(jìn)行遍歷就可以得到圖7.8所示的兩種不同的生成樹,并分別稱為深度優(yōu)先生成樹和廣度優(yōu)先生成樹。對于有n個頂點的連通圖,至少有n-1條邊,而生成樹中恰好有n-1條邊,所以連通圖的生成樹是該圖的極小連通子圖。若在圖G的生成樹中任意加一條屬于邊集B(G)中的邊,則必然形成回路。7.4圖的生成樹7.4.1課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-

7.4.2最小生成樹

1.網(wǎng)絡(luò)的概念若將圖的每條邊都賦上一個權(quán),則稱這種帶權(quán)的圖為網(wǎng)絡(luò)。通常權(quán)是具有某種意義的數(shù),比如,我們可以表示兩個頂點之間的距離,耗費(fèi)等。圖7.9就是兩個網(wǎng)絡(luò)的例子。若G=(V,E)是網(wǎng),則鄰接矩陣可定義為

aij=Wij若(vi,vj)或〈V〉∈E

0若i=j

∞若(vi,vj)或〈vi,vj

〉E其中Wij

表示邊上的權(quán)值;∞表示一個計算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。7.4.2最小生成樹課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-A1=0615∞∞605∞3∞1505645∞50∞2∞36∞06∞∞4260A2=01∞234∞∞01∞∞∞∞∞∞0∞∞4∞∞∞20∞∞∞∞∞∞∞0∞3∞∞∞∞∞0∞∞∞3∞∞50

2.最小生成樹的定義及MST性質(zhì)以下討論無向網(wǎng)絡(luò)(簡稱網(wǎng)絡(luò)或網(wǎng))的最小生成樹問題。A1=0615∞∞A2=0

如果連通圖是一個網(wǎng)絡(luò),稱該網(wǎng)絡(luò)中所有生成樹中權(quán)值總和最小的生成樹為最小生成樹(也稱最小代價生成樹)。圖7.10給出圖7.9(a)的幾棵生成樹。其中(a)的權(quán)為26,(b)的權(quán)為16,(c)的權(quán)為15,可以證明(c)為一棵最小生成樹。求網(wǎng)絡(luò)的最小生成樹是一個具有重大實際意義的問題。例如,要求溝通n個城市之間的通訊線路,需要建造n-1條通訊線路?？梢园裯個城市看作圖的n個頂點,各個城市之間的通訊線路看作邊,相應(yīng)的建設(shè)花費(fèi)作為邊的權(quán),這樣就構(gòu)成了一個網(wǎng)絡(luò)。由于在n個城市之間,可行線路有(n*(n-1))/2條,那么,如何選擇其中的n-1條線路(邊)在n個城市間建成全都能相互通訊的網(wǎng),并且總的建設(shè)花費(fèi)為最小?這就是求該網(wǎng)絡(luò)的最小生成樹問題。如果連通圖是一個網(wǎng)絡(luò),稱該網(wǎng)絡(luò)中所有生成樹課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-

構(gòu)造最小生成樹的方法很多,其中大多數(shù)算法都利用了稱之為MST的性質(zhì)。MST性質(zhì):設(shè)G=(V,E)是一個連通圖,T=(U,TE)是正在構(gòu)造的最小生成樹。若邊(u,v)是G中所有一端在U中(即u∈U)而另一端在V-U中(即v∈V-U)具有最小權(quán)值的一條邊,則存在一棵包含邊(u,v)的最小生成樹。證明(反證法):設(shè)網(wǎng)絡(luò)G的任何一棵最小生成樹T都不包含(u,v),當(dāng)把(u,v)加到T中,則根據(jù)生成樹的定義和性質(zhì),生成樹T中必然存在一條包含(u,v)的回路(見圖7.11),并且T中必然已有另一條邊(u′,v′),其中u′∈U,v′∈V-U,且u和u′,v和v′之間均有路徑相通。構(gòu)造最小生成樹的方法很多,其中大多數(shù)算法課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-

7.4.3普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法如何利用MST性質(zhì)來構(gòu)造最小生成樹呢？一般有構(gòu)造它的Prim算法和Kruskal算法,我們先介紹Prim算法。

Prim算法的基本思想如下:假設(shè)G=(V,E)是連通網(wǎng),T=(U,TE)為欲構(gòu)造的最小生成樹。初始化U={u0},TE=φ。重復(fù)下述操作:在所有u∈U,v∈V-U的邊(u,v)∈E中,選擇一條權(quán)最小的邊(u,v)并入TE,同時將v并入U,直到U=V為止。這時產(chǎn)生的TE中具有n-1條邊。容易看出,上述過程求得的T=(U,TE)是G的一棵最小生成樹。連通網(wǎng)用鄰接矩陣net表示,若兩個頂點之間不存在邊,其權(quán)值用一大于任何邊上權(quán)值的較大數(shù)max來表示不存在邊的長度。數(shù)據(jù)類型定義和普里姆算法描述如下:7.4.3普里姆(Prim)算法和克魯斯卡爾(Kru算法7.6typedefstruct

{intbegin,end;/*邊的起點和終點*/

floatlength;/*邊的權(quán)值*/

}edgefloatnet［n］［n］;/*連通網(wǎng)的帶權(quán)鄰接矩陣*/edgetree［n-1］;/*生成樹*/voidPrim(void)

{/*構(gòu)造網(wǎng)net的最小生成樹,u0=1為構(gòu)造出發(fā)點*/

intj,k,m,v,min,max=10000;算法7.6floatd;

edgee;

for(j=1;j<n;j++)/*初始化tree［n-1］*/

{tree［j-1］.begin=1;/*頂點1并入U*/

tree［j-1］.end=j+1;

tree［j-1］.length=net［0］［j］;

}

for(k=0;k<n-1;k++)/*求第k+1條邊*/

{min=max;floatd;for(j=k;j<n-1;j++)if(tree［j］.length<min)

{min=tree［j］.length;m=j;}

e=tree［m］;tree［m］=tree［k］;tree［k］=e;

v=tree［k］.end;/*V∈U*/for(j=k+1;j<n-1;j++)/*在新的頂點v并入U之后更新tree［n-1］*/{d=net［v-1］［tree［j］.end-1］;

if(d<tree［j］.length)

{tree［j］.length=d;for(j=k;j<n-1;j++)if(tretree［j］.begin=v;

}/*if*/

}/*for*/

}/*for*/

for(j=1;j<n;j++)

printf(″%d%d%f\n″,tree［j］.begin,tree［j］.end,tree［j］.length);

}/*Prim*/求圖7.9中網(wǎng)的最小生成樹的Prim算法的執(zhí)行過程如圖7.12所示。t課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-

在圖7.12中,(a)為一個網(wǎng),此時U={1},V-U={2,3,4,5,6},在和1相關(guān)聯(lián)的所有的邊中,(1,3)的權(quán)值最小,因此取(1,3)為最小生成樹的第一條邊,如(b)所示;此時U={1,3},V-U={2,4,5,6},在和1、3相關(guān)聯(lián)的所有邊中,(3,6)為權(quán)值最小的邊,取(3,6)為最小生成樹的第二條邊,如(c)所示;現(xiàn)在U={1,3,6},V-U={2,4,5},在和1、3、6相關(guān)聯(lián)的所有邊中,(6,4)的權(quán)值最小,取(6,4)為最小生成樹的第三條邊,如(d)所示;這樣,U={1,3,6,4},V-U={2,5},在所有和1、3、6、4相關(guān)聯(lián)的邊中,(3,2)為權(quán)值最小的邊,取(3,2)為最小生成樹的第四條邊,如(e)所示;U={1,3,6,4,2},V-U={5},U中頂點和5相關(guān)聯(lián)的權(quán)值最小的邊為(2,5),取(2,5)為最小生成樹的第五條邊,如(f)所示。(f)為最終得到的最小生成樹。在圖7.12中,(a)為一個網(wǎng),此時U={Prim算法的初始化時,其時間復(fù)雜度為O(n),但k循環(huán)內(nèi)有兩個循環(huán)語句,故這個循環(huán)的總時間為O(n2),所以整個算法的時間復(fù)雜度是O(n2)。Prim算法的運(yùn)算量與網(wǎng)的邊數(shù)有關(guān),因此適合于求邊稠密的網(wǎng)的最小生成樹。構(gòu)造最小生成樹的另一算法是一種按權(quán)值遞增的次序來構(gòu)造最小生成樹的方法,這是由Kruskal提出的。

Kruskal算法的基本思想如下:設(shè)G=(V,E)是連通網(wǎng),最小生成樹T=(V,TE),初始時TE=Ф,即T僅包含網(wǎng)G的全部頂點,T中每個頂點自成一個連通分量,在圖G的邊集E中按權(quán)值自小至大依次選擇邊(u,v),若該邊端點u、v分別是當(dāng)前T的兩個連通分量T1、T2中的頂點,則將該邊加入到T中,T1、T2也由此連接成一個連通分量;若u、v是當(dāng)前同一個連通分量中的頂點,則舍去此邊,依次類推,直到T中所有頂點都在同一連通分量上為止,T便成為G的一棵最小生成樹。Prim算法的初始化時,其時間復(fù)雜度為O(

此算法可以簡單描述如下:

T=(V,Φ);

While(T中所有邊數(shù)<n-1)

{從E中選取當(dāng)前最短邊(u,v);從E中刪去邊(u,v);

If((u,v)并入T之后不產(chǎn)生回路)將(u,v)并入T中;

}按此算法思想對圖7.12(a)的網(wǎng)進(jìn)行處理,逐步形成最小生成樹的過程如圖7.13所示?？梢宰C明Kruskal算法的時間復(fù)雜度是O(e),其中e是圖G的邊數(shù)。此算法可以簡單描述如下:課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-7.5最短路徑

7.5.1單源頂點最短路徑問題求解設(shè)從頂點v1出發(fā),找從它到圖中所有其它各頂點的最短路徑。迪杰斯特拉(Dijkstra)提出了一個按路徑長度遞增的順序產(chǎn)生最短路徑的方法。此方法的基本思想是:把圖中所有的頂點分成兩組,第一組包括已確定最短路徑的頂點,第二組包括尚未確定最短路徑的頂點,按最短路徑長度遞增的順序逐個把第二組的頂點加到第一組中去,直至從v1出發(fā)可以到達(dá)的所有頂點都包括在第一組中。在這個過程中,總保持從v1到第一組各頂點的最短路程長度,都不大于從v1到第二組的任何頂點的最短路徑長度。另外,每一個頂點對應(yīng)一個距離值,第一組的頂點對應(yīng)的距離值就是從v1到此頂點的只包括第一組的頂點為中間頂點的最短路徑長度。7.5最短路徑7.5.1單源頂點最短路

具體的做法是:一開始第一組只包括頂點v1,第二組包括其它所有頂點,v1對應(yīng)的距離值為0,第二組的頂點對應(yīng)的距離值是這樣確定的:若圖中有邊〈v1,vj

〉,則vj的距離為此邊所帶的權(quán)值,否則vj的距離值為一個很大的數(shù)(大于所有頂點間的路徑長度),然后每次從第二組的頂點中選一個距離值為最小的vm加入到第一組中。每往第一組加入一個頂點vm,就要對第二組的各個頂點的距離值進(jìn)行一次修正。若加進(jìn)vm做中間頂點,使從v1到vj的最短路徑比不加vm的路徑為短,則要修改vj的距離值。修改后再選距離最小的頂點加入到第一組中。具體的做法是:一開始第一組只包括頂點v1,

如此進(jìn)行下去,直到圖中所有頂點都包括在第一組中,或再也沒有可加入到第一組中的頂點存在為止。假設(shè)有向圖G的n個頂點為1到n,并用鄰接矩陣cost表示,若〈vi,vj

〉是圖G中的邊,則cost［i］［j］的值等于邊所帶的權(quán);若〈vi,vj〉不是圖G中的邊,則cost［i］［j］等于一個很大的數(shù);若i=j,則cost［i］［j］=0。另外,設(shè)置3個數(shù)組S［n］、dist［n］、pre［n］。S用以標(biāo)記那些已經(jīng)找到最短路徑的頂點,若S［i-1］=1,則表示已經(jīng)找到源點到頂點i的最短路徑；若S［i-1］=0,則表示從源點到頂點i的最短路徑尚未求得。dist［i-1］用來記錄源點到頂點i的最短路徑。

pre［i-1］表示從源點到頂點i的最短路徑上該點的前趨頂點,若從源點到該頂點無路徑,則用0作為其前一個頂點序號。算法描述如下。如此進(jìn)行下去,直到圖中所有頂點都包括在第一算法7.7

voidDijkstra(floatcost［］［n］,intv)

{/*求源點v到其余頂點的最短路徑及其長度,cost為有向網(wǎng)的帶權(quán)鄰接矩陣*//*設(shè)max值為32767,代表一個很大的數(shù)*/

v1=v-1;

for(i=0;i<n;i++)

{dist［i］=cost［v1］［i］;/*初始化dist*/

if(dist［i］<max)pre［i］=v;elsepre［i］=0;

}算法7.7pre［v1］=0;

for(i=0;i<n;i++)S［i］=0;/*第一組開始為空集*/

S［v1

］=1;/*源點v并入第一組*/

for(i=0;i<n;i++)/*擴(kuò)充第一組*/

{min=max;

for(j=0;j<n;j++)

if(!S［j］&&(dist［j］<min)){min=dist［j］;k=j;}S［k］=1;/*將k+1加入第一組*/

for(j=0;j<n;j++)

if(!S［j］&&(dist［j］>dist［k］+cost［k］［j］))/*修正第二組各頂點的距離值*/pre［v1］=0;{dist［j］=dist［k］+cost［k］［j］;pre［j］=k+1;}/*k+1是j+1的前趨*/

}/*所有頂點均已擴(kuò)充到S中*/

for(j=0;j<n;j++)/*打印結(jié)果*/

{printf(″%f\n%d″,dist［i］,i+1);

p=pre［i］;

while(p![KG-*2]=0)/*繼續(xù)找前趨頂點*/

{printf(″<″%d″,p};

p=pre［p-1］;

}

}

}/*Dijkstra*/{dist［j］=dist［k］+cost

例如,對圖7.14所示的有向網(wǎng)絡(luò)實施算法7.7,若源點為1,鄰接矩陣cost如左,則運(yùn)算執(zhí)行中S,dist及pre的變化狀況如表7.1所示。

∞050∞∞∞∞0∞10∞∞20060∞∞∞∞0

由表7.1容易看出,Dijkstra算法的時間復(fù)雜度為O(n2)。例如,對圖7.14所示的有向網(wǎng)絡(luò)實施算法7課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-

7.5.2求有向網(wǎng)中每對頂點間的路徑給出一個含有n個頂點的帶權(quán)有向網(wǎng),要求其每一對頂點之間的最短路徑。解決這個問題的一種方法是反復(fù)執(zhí)行n次Dijkstra算法,每次執(zhí)行以一個頂點為起始頂點,求得從該頂點到其它各頂點的最短路徑;執(zhí)行n次之后,就能求得從每一個頂點出發(fā)到其它各頂點的最短路徑。弗洛伊德(Floyd)提出了另一種算法,這種算法仍用鄰接矩陣cost表示帶權(quán)有向圖。如果從vi到vj有弧,則從vi到vj存在一條長度為cost［i］［j］的路徑,該路徑不一定是最短路徑,需要進(jìn)行n次試探。首先考慮路徑(vi,v1,vj)是否存在(即判別弧〈vi,v1

〉和〈v1,vj

〉是否存在),如果存在,則比較〈vi,v1v〉和〈vi,vj

〉的路徑長度,取較短者為從v到vj的中間頂點序號不大于1的最短路徑。7.5.2求有向網(wǎng)中每對頂點間的路徑

在路徑上再增加一個頂點v2,若(vi,…,v2)和(v2,…,vj)分別是當(dāng)前找到的中間頂點序號不大于1的最短路徑,則(vi,…,v2,…,vj)就有可能是從v到vj的中間頂點的序號不大于2的最短路徑。將它和已經(jīng)得到從vi到vj中間頂點序號不大于1的最短路徑相比較,從中選出長度較短者作為從vi到vj中間頂點序號不大于2的最短路徑之后,再增加一個頂點v3,繼續(xù)進(jìn)行試探,依次類推。在一般情況下,若(vi,…,vk)和(vk,…,v)分別是從vi到vk和從vk到vj的中間頂點序號不大于k-1的最短路徑,則將(vi,…,vk,…,vj)和已經(jīng)得到的vi到vj且中間頂點序號不大于k-1的最短路徑相比較,取其長度較短者作為從vi到vj的中間頂點序號不大于k的最短路徑。在路徑上再增加一個頂點v2,若(vi,…

如此重復(fù),經(jīng)過n次比較后,最后求得的必是從vi到vj的最短路徑。用此方法,可同時求得每對頂點間的最短路徑。綜上所述,弗洛伊德(Floyd)算法的基本思想是遞推地產(chǎn)生一個矩陣序列:A0,A1,…Ak,…An,其中:

A0［i］［j］=cost［i］［j］

Ak

［i］［j］=Min{A(k-1)［i］［j］,A(k-1)

［i］［k］+(k-1)［k］［j］}(1≤k≤n)由上述公式可以看出,A1［i］［j］是從vi到vj中間頂點序號不大于1的最短路徑長度;Ak

［i］［j］是從vi到vj中間頂點序號不大于k的最短路徑長度;An［i］［j］是從vi到vj的最短路徑長度。如此重復(fù),經(jīng)過n次比較后,最后求得的必是

還設(shè)置一個矩陣path,path［i］［j］是從vi到vj中間頂點序號不大于k的最短路徑上vi的一個鄰接頂點的序號,約定若vi到vj無路徑時path［i］［j］=0。由path［i］［j］的值,可以得到從vi到vj的最短路徑。算法描述如下：算法7.8

intpath［n］［n］/*路徑矩陣*/

voidFloyd(floatA［］［n］,cost［］［n］);

{/*A是路徑長度矩陣,cost是有向網(wǎng)G,max=32767代表一個很大的數(shù)*/

for(i=0;i<n;i++)/*設(shè)置A和path的初值*/還設(shè)置一個矩陣path,path［i］［jfor(j=0;j<n;j++)

{if(cost［i］［j］<max)path［i］［j］=j;/*j是i的后繼*/else{path［i］［j］=0;A［i］［j］=cost［i］［j］;

}

for(k=0;k<n;k++)

/*做n次迭代,每次均試圖將頂點k擴(kuò)充到當(dāng)前求得的從i到j(luò)的最短路徑上*/

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(A［i］［j］>(A［i］［k］+A［k］［j］))/*修改長度和路徑*/for(j=0;j<n;j++){A［i］［j］=A［i］［k］+A［k］［j］;path［i］［j］=path［i］［k］;}

for(i=0;i<n;i++)/*輸出所有頂點對i,j之間的最短路徑的長度及路徑*/

for(j=0;j<n;j++)

{printf(″%f″,A［i］［j］);/*輸出最短路徑的長度*/next=path［i］［j］;/*next為起點i的后繼頂點*/if(next==0)/*i無后繼表示最短路徑不存在*/{A［i］［j］=A［i］［k］+A［kprintf(″%dto%dnopath.\n″,i+1,j+1)

else/*最短路徑存在*/

{printf(″%d″,i+1);

while(next![KG-*2]=j+1)/*打印后繼頂點,然后尋找下一個后繼頂點*/

{printf(″″-->%d″,next);next=path［next-1］［j］;}printf(″″-->%d\n″,j+1);

}/*else*//*打印終點*/*/

}/*for*/

}/*Floyd*/printf(″%dto%dnopath.\n″,

以圖7.14中的有向網(wǎng)絡(luò)為例實施上述算法,迭代過程中A和path的變化及其最終輸出的結(jié)果見圖7.15。圖中A0=cost,∝在機(jī)內(nèi)表示為max。對此例而言,迭代時有:A1=A0,path1=path0,A5=A4,path5=path4,因此表中省略了A1,path1,A5和path5。算法輸出的結(jié)果是由最終求得的路徑長度矩陣A5和路徑矩陣path5求得的。以圖7.14中的有向網(wǎng)絡(luò)為例實施上述算法,課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-7.6有向無環(huán)圖及應(yīng)用

7.6.1拓樸排序所有的工程或者某種流程都可以分為若干個小的工程或者階段,稱這些小的工程或階段為“活動”。若以圖中的頂點來表示活動,有向邊表示活動之間的優(yōu)先關(guān)系,則這樣的有向圖稱為AOV(ActivityOnVertexnetwork)網(wǎng)。在AOV網(wǎng)中,若從頂點vi到頂點vj之間存在一條有向路徑,稱頂點vi是頂點vj的前趨,或者稱頂點vj是頂點vi的后繼。若〈vi,vj

〉是圖中的弧,則稱頂點vi是頂點vj的直接前趨,頂點vj是頂點vi的直接后繼。

AOV網(wǎng)中的弧表示了活動之間存在的制約關(guān)系。7.6有向無環(huán)圖及應(yīng)用7.6.1拓樸排

例如,計算機(jī)專業(yè)的學(xué)生必須完成一系列規(guī)定的專業(yè)基礎(chǔ)課和專業(yè)課才能畢業(yè),這個過程就可以被看成是一個大的工程,而活動就是學(xué)習(xí)每一門課程。我們不妨把這些課程的名稱與相應(yīng)的代號列于表7.2。其中C1,C13是獨立于其它課程的基礎(chǔ)課,而有的課卻需要有先行課（如學(xué)完解析幾何才能學(xué)微積分）,前提條件規(guī)定了課程之間的優(yōu)先關(guān)系。這種優(yōu)先關(guān)系可以用圖7.16所示的有向圖來表示。其中,頂點表示課程,有向邊表示前提條件。若課程vi為課程vj的前行課,則必然存在有向邊〈vi,vj

〉。例如,計算機(jī)專業(yè)的學(xué)生必須完成一系列規(guī)定課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-

顯然,任何一個可執(zhí)行程序也可以劃分為若干個程序段(或若干語句),由這些程序段組成的流程圖也是一個AOV網(wǎng)。

對于一個AOV網(wǎng),常常要以有向圖的次序關(guān)系為前提,為每個單項活動進(jìn)行的先后安排一個線性序列的次序關(guān)系,如對圖7.16來說,(C1,C13,C4,C8,C14,C15,C5,C2,C3,C10,C7,C11,C12,C6,C9)是一個可行的線性序列,因為有向圖Ci是Cj的前趨,則在上述線性序列中Ci排在Cj的前面。在AOV網(wǎng)中不允許出現(xiàn)環(huán),因為環(huán)意味著某項子工程的開工將以本身工作完成為先決條件,這顯然是不合理的。檢測有環(huán)的一個方法是,把AOV網(wǎng)中全部頂點排成一個線性序列,使得在此序列中頂點之間不僅保持有向圖中原有的次序關(guān)系,而且在有向圖中所有無關(guān)系的各對頂點之間人為建立一個次序關(guān)系。顯然,任何一個可執(zhí)行程序也可以劃分為若干個

若有向圖無環(huán),則可構(gòu)造一個包含圖中所有頂點的線性序列。稱具有上述特性的線性序列為拓樸有序序列。對AOV網(wǎng)構(gòu)造拓樸有序序列的運(yùn)算稱為拓樸排序。若AOV有環(huán),則找不到該網(wǎng)的拓樸有序序列。反之,任何無環(huán)有向圖,其所有頂點都可以排在一個拓樸有序序列里。一個AOV網(wǎng)的拓樸有序序列不是唯一的。例如,對圖7.16的有向圖頂點進(jìn)行拓樸排序,還可以得到(C1,C13,C4,C8,C14,C15,C2,C3,C10,,C11,C12,C9,C9,C7,C5)。對AOV網(wǎng)進(jìn)行拓樸排序的方法和步驟如下:若有向圖無環(huán),則可構(gòu)造一個包含圖中所有頂點(1)從AOV網(wǎng)中選擇一個沒有前趨的頂點（該頂點的入度為0）并且輸出它;

(2)從網(wǎng)中刪去該頂點,并且刪去從該頂點發(fā)出的全部有向邊;

(3)重復(fù)上述兩步,直到剩余網(wǎng)中不再存在沒有前趨的頂點為止。操作的結(jié)果有兩種:一種是網(wǎng)中全部頂點都被輸出,這說明網(wǎng)中不存在有向回路,拓樸排序成功;另一種是網(wǎng)中頂點未被全部輸出,剩余的頂點均有前趨頂點,這說明網(wǎng)中存在有向回路,不存在拓樸有序序列。圖7.17給出了一個AOV網(wǎng)實施上述步驟的例子。這樣得到一個拓樸序列(v1,v6,v4,v3,v2,v5)。(1)從AOV網(wǎng)中選擇一個沒有前趨的頂點課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-

為了實現(xiàn)上述思想,我們采用鄰接鏈表作為給定的AOV網(wǎng)的存儲結(jié)構(gòu),在表頭結(jié)點增設(shè)一個入度域,以存放各個頂點當(dāng)前的入度值,每個頂點的入度域的值都隨鄰接鏈表動態(tài)生成過程中累計得到,由圖7.17的AOV網(wǎng)生成的鄰接鏈表如圖7.18(a)所示。為了避免在每一步選入度為零的頂點時重復(fù)掃描表頭數(shù)組,利用表頭數(shù)組中入度為零的頂點域作為鏈棧域,存放下一個入度為零的頂點序號,零表示棧底,棧頂指針為top,寄生在表頭數(shù)組的入度域中的入度為零的頂點鏈表如圖7.18(b)所示。棧頂指針top=6指出v6的入度為零,v6的入度域為1,指出下一個入度為零的頂點是v1,v1的入度為零表示v1是棧底。根據(jù)上面的敘述,我們得到鄰接鏈表作存儲結(jié)構(gòu)的拓樸排序算法梗概如下:為了實現(xiàn)上述思想,我們采用鄰接鏈表作為給定課件-數(shù)據(jù)結(jié)構(gòu)教學(xué)第7章圖-(1)掃描頂點表,將入度為零的頂點入棧;

(2)While(棧非空)

{將棧頂點vj彈出并輸出之;在鄰接鏈表中查vj的直接后繼vk,把vk的入度減1,若vk的入度為零則進(jìn)棧;}

(3)若輸出的頂點數(shù)小于n,則輸出“有回路”;否則拓樸排序正常結(jié)束。下面給出求精的拓樸排序算法。算法7.9

typedefstructnode

{intvex;(1)掃描頂點表,將入度為零的頂點入棧;typedefstructvnode{intid;

structnodelink;}vexnode;voidtoposort(vexnodedig［］)

{/*AOV網(wǎng)的鄰接鏈表*/

edgenode*p;

top=0;m=0;

for(i=1;i<n+1;i++)/*入度為零的頂點進(jìn)棧*/if(dig［i］.id==0){dig［i］.id=top;top=i;}typedefstructvnodeWhile(top>0)

{j=top;top=dig［top］.id;

printf(″%d\n″,j);