圖

軟件技術(shù)基礎(chǔ)（六）西安電子科技大學(xué)

電子工程學(xué)院

林杰1本章要求1.基本要求（1）熟練掌握圖的定義，無向圖、有向圖、子圖、頂點(diǎn)的度、帶權(quán)圖、連通圖、強(qiáng)連通圖等的概念，邊（或?。┡c頂點(diǎn)之間的關(guān)系。掌握圖的兩種存儲(chǔ)方法，以及存儲(chǔ)結(jié)構(gòu)的定義，了解建立圖的算法。（2）熟練掌握深度優(yōu)先和廣度優(yōu)先搜索遍歷圖的方法，了解相應(yīng)的算法，寫出給定圖的遍歷序列。掌握生成樹的概念，了解相應(yīng)的算法，根據(jù)兩種搜索遍歷的方法畫出生成樹；掌握最小生成樹的概念，用Prim（普里姆）和Kruskal（克魯斯卡爾）算法畫出最小生成樹。2.重點(diǎn)、難點(diǎn)重點(diǎn)：圖的定義及圖的概念，圖的遍歷方法和生成樹及最小生成樹。難點(diǎn)：圖的建立和遍歷算法，最小生成樹算法2本章內(nèi)容7.1圖的基本概念7.2圖的存儲(chǔ)方法7.3圖的遍歷7.4生成樹和最小生成樹7.5最短路徑7.6拓?fù)渑判?.7關(guān)鍵路徑3哥尼斯堡七橋問題（1736年）4能否從某個(gè)地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點(diǎn)？5圖的實(shí)例：我的畢業(yè)旅行十三城市之間火車費(fèi)用表十三城市之間火車行駛時(shí)間表方案1：最省錢方案2：最省時(shí)67.1圖的基本概念圖G是由一個(gè)頂點(diǎn)集V(G)和一個(gè)邊集E(G)構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。記為二元組形式：G=(V,E)。其中:

V是由頂點(diǎn)構(gòu)成的非空有限集合，記為：V＝{V0,V1,V2,…Vn-1}

E是由V中頂點(diǎn)的對偶構(gòu)成的有限集合，記為：E={(V0,V2),(V3,V4),…}，若E為空，則圖中只有頂點(diǎn)而沒有邊。在線性表中，元素個(gè)數(shù)可以為零，稱為空表；在樹中，結(jié)點(diǎn)個(gè)數(shù)可以為零，稱為空樹；在圖中，頂點(diǎn)個(gè)數(shù)不能為零，但可以沒有邊。7其中頂點(diǎn)的對偶可以表示成：

(Vi,Vj)—無序的對偶稱為邊（edge），

即(Vi,Vj)=(Vj,Vi)，其圖稱為無向圖。<Vi,Vj>—有序的對偶稱為?。╝rc），

即<Vi,Vj>≠<Vj,Vi>，稱Vi為弧尾（tail）或起始點(diǎn)，稱Vj為弧頭（head）或終端點(diǎn)，該圖稱為有向圖。8無向圖：邊用(x,y)表示，且頂點(diǎn)x與y是無序的。V(G2)={A,B,C}E(G2)={(A,B),(B,C),(C,A)}

={(B,A),(C,B),(A,C)}ABC無向圖G2有向圖：邊用<x,y>表示，且x與y是有序的。a)有向圖中的邊又稱為“弧”

b)x:弧尾或弧的起始頂點(diǎn)；y:弧頭或弧的終止頂點(diǎn)V(G1)={A,B,C}E(G1)={<A,B>,<B,A>,<B,C>,<A,C>}ABC有向圖G19

（1）一條邊中涉及的兩個(gè)頂點(diǎn)必須不相同，即：若（vi，vj）或<vi，vj>是E(G)中的一條邊，則要求vi≠vj；（2）一對頂點(diǎn)間不能有相同方向的兩條有向邊；（3）一對頂點(diǎn)間不能有兩條無向邊。圖的說明V0V1V2V3V4V0V1V2V3V4V0V1V2V3數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖10

1）頂點(diǎn)的數(shù)目n與弧或邊的數(shù)目e的關(guān)系：無向圖：0≤e≤n(n-1)/2e=0：任意兩頂點(diǎn)之間都沒有邊

e=n(n-1)/2：任意兩頂點(diǎn)之間都有邊，稱為無向完全圖。有向圖：0≤e≤n(n-1)e=0：任意兩頂點(diǎn)之間都沒有弧

e=n(n-1)：任意兩頂點(diǎn)之間都有弧，稱為有向完全圖。V0V1V2V3V0V1V2112）稀疏圖：有很少條邊的圖（e<nlogn）稠密圖：e>=nlogn的圖3）子圖：設(shè)有兩個(gè)圖G＝(V,E)和G’＝(V’,E’)。若V’V且E’

E,則稱圖G’是圖G的子圖。ABC有向圖G1ABC有向圖G1的子圖G1’ABC無向圖G2ABC無向圖G2的子圖G2’12v1v2v3v4（a）無向完全圖G3子圖示例v1v2v4v2v3v4v1v2v3v4無向圖G3的部分子圖13v1v2v3v4（b）有向完全圖G4v1v4v2v3v4v1v1v3v2v4完全有向圖G4的部分子圖子圖示例144）鄰接點(diǎn)無向圖：若邊（Ｖi，Ｖj）∈E(G)則稱Ｖi和Ｖj相互鄰接，兩個(gè)頂點(diǎn)互為鄰接點(diǎn)，并稱邊（Ｖi，Ｖj

）關(guān)聯(lián)于頂點(diǎn)Ｖi和Ｖj或稱邊（Ｖi，Ｖj

）與頂點(diǎn)相關(guān)聯(lián)。有向圖：邊<Ｖi，Ｖj>∈E(G)則稱Ｖi鄰接到Ｖj

，或稱Ｖj鄰接于Ｖi，并稱邊<Ｖi，Ｖj>關(guān)聯(lián)于頂點(diǎn)Ｖi和Ｖj

，或稱邊<Ｖi，Ｖj>與頂點(diǎn)Ｖi和Ｖj相關(guān)聯(lián)。ABC無向圖G1ABC有向圖G215不同結(jié)構(gòu)中邏輯關(guān)系的對比FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V0V1V2V3V4圖結(jié)構(gòu)在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線性關(guān)系；在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間具有層次關(guān)系；在圖結(jié)構(gòu)中，任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系。16FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V0V1V2V3V4圖結(jié)構(gòu)在線性結(jié)構(gòu)中，元素之間的關(guān)系為前驅(qū)和后繼；在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系為雙親和孩子；在圖結(jié)構(gòu)中，頂點(diǎn)之間的關(guān)系為鄰接。不同結(jié)構(gòu)中邏輯關(guān)系的對比17

5）度，出度和入度有向圖

頂點(diǎn)v的入度ID(v)：以該頂點(diǎn)為終點(diǎn)的弧的數(shù)目；

頂點(diǎn)v的出度OD(v)：以該頂點(diǎn)為起點(diǎn)的弧的數(shù)目；

頂點(diǎn)v的度D(v)：D(v)=ID(v)+OD(v)；無向圖

頂點(diǎn)v的度D(v)：與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目；ABC有向圖G1ABC無向圖G2ID(A)=1OD(A)=2D(A)=3D(A)=2D(B)=2D(C)=218頂點(diǎn)的度與弧的關(guān)系對于一個(gè)有向圖或無向圖，如果具有n個(gè)頂點(diǎn)，e條邊（?。?，且每個(gè)頂點(diǎn)的度為D(Vi)(1=<i<=n)，則存在以下關(guān)系：注：圖中的每條邊均關(guān)聯(lián)于兩個(gè)頂點(diǎn)ABC有向圖G1ABC無向圖G2196）權(quán)與網(wǎng)如果圖的邊或弧具有一個(gè)與它相關(guān)的數(shù)時(shí)，這個(gè)數(shù)就稱為該邊或弧的權(quán)。這個(gè)數(shù)常常用來表示距離或耗費(fèi)。若將圖的每條邊都賦上一個(gè)權(quán)，則稱這種帶權(quán)圖為網(wǎng)絡(luò)，簡稱為網(wǎng)。V0V1V3V234567825V0V2V1455064（a）無向網(wǎng)絡(luò)G1

（b）有向網(wǎng)絡(luò)G220哈夫曼樹中的權(quán)與網(wǎng)圖的權(quán)有何區(qū)別？V0V1V2V327857423217）路徑與回路在圖G＝(V,E)中，若從頂點(diǎn)vi

出發(fā)，沿一些邊經(jīng)過一些頂點(diǎn)vp1,vp2,…,vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vi，vp1，vp2，...vpm，vj)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E的邊。V0到V3的路徑：V0V3

V0

V1V2V3

V0

V1V4V2V3V0V1V2V3V4一般情況下，圖中的路徑不唯一22路徑長度:非帶權(quán)圖的路徑長度是指此路徑上邊/弧的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊/弧的權(quán)之和。V0V1V2V3V4V0V3：路徑長度為1V0V1V2V3：路徑長度為3V0V1V4V2V3：路徑長度為4V0V3：路徑長度為8V0V1V2V3：路徑長度為7V0V1V4V2V3：路徑長度為15V0V1V2V3V425632823

簡單路徑：若路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù),則稱這樣的路徑為簡單路徑?；芈罚喝袈窂缴系谝粋€(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合（路徑長度≥2）,則稱這樣的路徑為簡單回路或簡單環(huán)。

例如：

a:（0，1，3，2）是簡單路徑；

b:（0，1，3，0，1，2）是非簡單路徑；

c:（0，1，3，0）是簡單回路。0132a簡單路徑0132b非簡單路徑0132c回路24

有根圖：在一個(gè)有向圖中，若存在一個(gè)頂點(diǎn)v，從該頂點(diǎn)有路徑可到達(dá)圖中其它的所有頂點(diǎn)，則稱這個(gè)有向圖為有根圖，v稱為該圖的根。V0V1V2V3278525

8）連通圖連通：在無向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱頂點(diǎn)v1與v2是連通的。連通圖：如果圖中任意一對頂點(diǎn)都是連通的,則稱此圖是連通圖。連通分量：非連通圖的極大連通子圖叫做連通分量。1.含有極大頂點(diǎn)數(shù)；2.依附于這些頂點(diǎn)的所有邊。V0V1V2V3V426

例：非連通圖及其連通分量示例V1V2V4V5V3（a）非連通圖V1V2V4V5V3（b）G5的兩個(gè)連通分量H1和H227強(qiáng)連通圖：在有向圖中,若對于每一對頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。強(qiáng)連通分量：非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。ABCa：強(qiáng)連通圖ABCDEb：非強(qiáng)連通圖ABCDEc：（b）圖的兩個(gè)強(qiáng)連通分量28根據(jù)強(qiáng)連通圖的定義，可知強(qiáng)連通圖的唯一強(qiáng)連通分量是其自身，而非強(qiáng)連通的有向圖有多個(gè)強(qiáng)連通分量。例如，右圖所示的有向圖G4是一個(gè)具有4個(gè)頂點(diǎn)的強(qiáng)連通圖。v1v2v3v4有向完全圖G4

v1v2v3v4（a）非強(qiáng)連通圖G6下圖（a）所示的有向圖G6不是強(qiáng)連通圖（v2、v3、v4沒有到達(dá)v1的路徑），它的兩個(gè)強(qiáng)連通分量H3與H4如圖下圖（b）所示。v1v2v3v4（b）G6的兩個(gè)強(qiáng)連通分量H3和H4

299）生成樹，生成深林生成樹：n個(gè)頂點(diǎn)的連通圖G的生成樹是包含G中全部頂點(diǎn)的一個(gè)極小連通子圖。生成森林：在非連通圖中，由每個(gè)連通分量都可以得到一棵生成樹，這些連通分量的生成樹就組成了一個(gè)非連通圖的生成森林。多——構(gòu)成回路少——不連通含有n-1條邊30V0V1V3V4V2V6V5V0V1V3V4V2V6V5V0V1V2V3V4V0V1V2V3V4生成樹生成森林317.2圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)至少要保存兩類信息：

1)頂點(diǎn)的數(shù)據(jù)

2)頂點(diǎn)間的關(guān)系約定:G=<V,E>是圖,V={v0,v1,v2,…vn-1},設(shè)頂點(diǎn)的下標(biāo)為它的編號(hào)。如何表示頂點(diǎn)間的關(guān)系？V0V1V2V3V4V0V1V2V37.2圖的存儲(chǔ)結(jié)構(gòu)32由于圖結(jié)構(gòu)中任意兩個(gè)頂點(diǎn)之間都可能存在“關(guān)系”，因此無法以簡單的順序存儲(chǔ)映象表示這種關(guān)系。常用的圖的存儲(chǔ)方法鄰接矩陣鄰接鏈表十字鏈表多重鏈表337.2.1鄰接矩陣圖的鄰接矩陣表示法，也稱為數(shù)組表示法。它采用兩個(gè)數(shù)組來表示圖。頂點(diǎn)表:一個(gè)存儲(chǔ)各個(gè)頂點(diǎn)信息的一維數(shù)組。鄰接矩陣：一個(gè)存儲(chǔ)各個(gè)頂點(diǎn)之間的關(guān)系（邊或?。┑亩S數(shù)組。設(shè)圖G=(V,E)是一個(gè)有n個(gè)頂點(diǎn)的圖，則圖的鄰接矩陣A[n][n]定義為：A[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它34無向圖的鄰接矩陣的特點(diǎn)？無向圖的鄰接矩陣V0V2V3V1V0V1V2V3vertex=0101101101001100A=V0V1V2V3V0V1V2V3主對角線為0且一定是對稱矩陣。頂點(diǎn)表

鄰接矩陣35無向圖的鄰接矩陣V0V2V3V1如何求頂點(diǎn)i的度？鄰接矩陣的第i行（或第i列）非零元素的個(gè)數(shù)。V0V1V2V3vertex=0101101101001100A=V0V1V2V3V0V1V2V3頂點(diǎn)表

鄰接矩陣0101101101001100A=V0V1V2V3V0V1V2V336無向圖的鄰接矩陣V0V2V3V1如何判斷頂點(diǎn)Vi

和Vj

之間是否存在邊？測試鄰接矩陣中相應(yīng)位置的元素A[i][j]是否為1。V0V1V2V3vertex=頂點(diǎn)表

鄰接矩陣0101101101001100A=V0V1V2V3V0V1V2V337無向圖的鄰接矩陣V0V2V3V1如何求頂點(diǎn)i的所有鄰接點(diǎn)？將數(shù)組中第i行元素掃描一遍，若A[i][j]為1，則頂點(diǎn)j為頂點(diǎn)i的鄰接點(diǎn)。V0V1V2V3vertex=頂點(diǎn)表

鄰接矩陣38有向圖的鄰接矩陣V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V3有向圖的鄰接矩陣一定不對稱嗎？不一定，例如有向完全圖。39有向圖的鄰接矩陣V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V3如何求頂點(diǎn)i的出度？鄰接矩陣的第i行元素之和。40有向圖的鄰接矩陣V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V3如何求頂點(diǎn)i的入度？鄰接矩陣的第i列元素之和。41有向圖的鄰接矩陣V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V3如何判斷頂點(diǎn)i和j之間是否存在邊？測試鄰接矩陣中相應(yīng)位置的元素A[i][j]是否為1。42

約定：頂點(diǎn)的“第一個(gè)”鄰接點(diǎn)：該頂點(diǎn)所對應(yīng)的行中值為非零元素的最小列號(hào)所代表的頂點(diǎn)，其“下一個(gè)”鄰接點(diǎn)就是同行中離它次最近的值為非零元素的列號(hào)所代表的頂點(diǎn)。例如有向圖G1中頂點(diǎn)V0的第一個(gè)鄰接點(diǎn)為"頂點(diǎn)V1"，下一個(gè)鄰接點(diǎn)是"頂點(diǎn)V2"。V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V343網(wǎng)絡(luò)，鄰接矩陣元素A[i,j]可按以下規(guī)則取值：網(wǎng)絡(luò)的鄰接矩陣表示A[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他V0V1V2V32785025∞∞0∞

∞

∞

∞087∞∞0A=V0V1V2V3V0V1V2V344當(dāng)一個(gè)圖用鄰接矩陣表示時(shí)，可用以下數(shù)據(jù)類型來定義：#define n圖的頂點(diǎn)數(shù)

#define e圖的邊數(shù)

typedefcharvextype;//頂點(diǎn)的數(shù)據(jù)類型

typedeffloatadjtype;//頂點(diǎn)權(quán)值的數(shù)據(jù)類型

typedefstruct

{

vextypevexs[n];//頂點(diǎn)數(shù)組

adjtypearcs[n][n];//鄰接矩陣

}graph;頂點(diǎn)表和鄰接矩陣中結(jié)點(diǎn)的數(shù)據(jù)類型45無向網(wǎng)絡(luò)鄰接矩陣建立算法:voidCreatGraph(graphg)//建立無向網(wǎng)絡(luò){inti,j,k;floatw;

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

g->vexs[i]=getchar();//讀入頂點(diǎn)信息，建立頂點(diǎn)表

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

for(j=0;j<n;j++)g->arcs[i][j]=0;//鄰接矩陣初始化

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

{scanf(“%d,%d,%f”,&i,&j,&w);//讀入邊(vi,vj)上的權(quán)wg->arcs[i][j]=w;//寫入鄰接矩陣

g->arcs[j][i]=w;

}}//CreatGraph時(shí)間復(fù)雜度O(n2+e），由于e<<n2,所以時(shí)間復(fù)雜度是O(n2)建立無向圖，可以在算法中直接對鄰接矩陣的元素賦1建立有向網(wǎng)絡(luò)，只須將寫入矩陣的兩個(gè)語句中的后一個(gè)語句g->arcs[j][i]=w去掉即可467.2.2鄰接表鄰接表存儲(chǔ)的基本思想對于圖的每個(gè)頂點(diǎn)vi，將所有鄰接于vi的頂點(diǎn)鏈成一個(gè)單鏈表，稱為頂點(diǎn)vi的邊表（對于有向圖則稱為出邊表）。所有邊表的頭指針和存儲(chǔ)頂點(diǎn)信息的一維數(shù)組構(gòu)成了頂點(diǎn)表。圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的空間復(fù)雜度？如果為稀疏圖，會(huì)出現(xiàn)什么現(xiàn)象？

假設(shè)圖G有n個(gè)頂點(diǎn)e條邊，則存儲(chǔ)該圖需要O(n2)477.2.2鄰接表鄰接表包括：（1）頂點(diǎn)表；（2）鄰接鏈表鄰接表存儲(chǔ)方法是一種順序存儲(chǔ)（頂點(diǎn)表）與鏈?zhǔn)酱鎯?chǔ)（鄰接鏈表）相結(jié)合的存儲(chǔ)方法。

頂點(diǎn)表：頂點(diǎn)信息和單鏈表的頭指針一起存儲(chǔ)在一個(gè)一維數(shù)組中。一維數(shù)組要想表示兩類數(shù)據(jù)類型(頂點(diǎn)信息和頭指針)，則必須定義成結(jié)構(gòu)體的數(shù)組。

鄰接鏈表：將和同一頂點(diǎn)“相鄰接”的所有鄰接點(diǎn)鏈接在一個(gè)單鏈表中。48頂點(diǎn)表和鄰接鏈表中結(jié)點(diǎn)的數(shù)據(jù)類型typedefcharvextype;//定義頂點(diǎn)數(shù)據(jù)信息類型；typedefstructnode//鄰接鏈表結(jié)點(diǎn)，也叫弧結(jié)點(diǎn)的結(jié)構(gòu)；{

int

adjvex;//鄰接點(diǎn)域，該弧所指向的頂點(diǎn)的位置/下標(biāo)；

structnode*next;//鏈域，指向下一條弧的指針；

}edgenode;

typedefstruct//頂點(diǎn)的結(jié)構(gòu)

{

vextype

vertex;//頂點(diǎn)域，放置頂點(diǎn)信息；

edgenode

*link;//指針域，指向第一條依附于該頂點(diǎn)的弧

}vexnode;vexnodega[n];//頂點(diǎn)表49頂點(diǎn)表和鄰接鏈表中結(jié)點(diǎn)的數(shù)據(jù)類型鄰接表有兩種結(jié)點(diǎn)結(jié)構(gòu)：頂點(diǎn)表結(jié)點(diǎn)和鄰接鏈表結(jié)點(diǎn)vertexlink

adjvex

next

頂點(diǎn)表鄰接鏈表vertex：數(shù)據(jù)域，存放頂點(diǎn)信息。link：指針域，指向邊表中第一個(gè)結(jié)點(diǎn)。adjvex：鄰接點(diǎn)域，邊的終點(diǎn)在頂點(diǎn)表中的下標(biāo)。next：指針域，指向邊表中的下一個(gè)結(jié)點(diǎn)。50邊表，出邊表，入邊表邊表：對于無向圖，Vi的鄰接鏈表中每個(gè)結(jié)點(diǎn)都對應(yīng)與Vi相關(guān)聯(lián)的一條邊，所以將此鄰接鏈表稱為邊表。出邊表：對于有向圖，Vi的鄰接鏈表中每個(gè)結(jié)點(diǎn)都對應(yīng)于以Vi為起始點(diǎn)射出的一條邊（?。?，所以有向圖的鄰接鏈表也稱為出邊表。入邊表：有向圖還有另外一種表示法，叫入邊表。即Vi鄰接鏈表中的每個(gè)結(jié)點(diǎn)對應(yīng)于以Vi為終點(diǎn)的一條邊。51103∧23∧1∧01∧V0V1

V2V30123vertexlinkV0V2V3V1無向圖的鄰接表邊表中的結(jié)點(diǎn)表示什么？每個(gè)結(jié)點(diǎn)對應(yīng)圖中的一條邊，鄰接表的空間復(fù)雜度為O(n+e)。頂點(diǎn)表邊表52103∧23∧1∧01∧V0V1

V2V30123vertexlinkV0V2V3V1無向圖的鄰接表如何求頂點(diǎn)i的度？頂點(diǎn)i的邊表中結(jié)點(diǎn)的個(gè)數(shù)。頂點(diǎn)表邊表頂點(diǎn)v的度D(v)：與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目53103∧23∧1∧01∧V0V1

V2V30123vertexlinkV0V2V3V1無向圖的鄰接表如何判斷頂點(diǎn)i和頂點(diǎn)j之間是否存在邊?測試頂點(diǎn)i的邊表中是否存在終點(diǎn)為j的結(jié)點(diǎn)。(或測試頂點(diǎn)j的邊表中是否存在終點(diǎn)為i的結(jié)點(diǎn)。)頂點(diǎn)表邊表54有向圖的鄰接表V0V1V2V312∧3∧0∧V0V1

V2V30123vertexlink∧如何求頂點(diǎn)i的出度？頂點(diǎn)i的出邊表中結(jié)點(diǎn)的個(gè)數(shù)。頂點(diǎn)表出邊表55有向圖的鄰接表V0V1V2V312∧3∧0∧V0V1

V2V30123vertexlink∧如何求頂點(diǎn)i的入度？各頂點(diǎn)的出邊表中以頂點(diǎn)i為終點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)之和。頂點(diǎn)表出邊表56有向圖的鄰接表V0V1V2V312∧3∧0∧V0V1

V2V30123vertexlink∧如何判斷頂點(diǎn)i和頂點(diǎn)j之間是否存在邊?搜索兩個(gè)結(jié)點(diǎn)對應(yīng)的單鏈表頂點(diǎn)表出邊表57網(wǎng)圖的鄰接表V0V1V2V3278521V0V1

V2V30123vertexlink∧52∧83∧70∧邊表中，添加一個(gè)“權(quán)值域”58無向圖鄰接表的建立算法1.確定圖的頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)；2.輸入頂點(diǎn)信息，初始化該頂點(diǎn)的邊表；3.依次輸入邊的信息并存儲(chǔ)在邊表中；

3.1輸入邊所依附的兩個(gè)頂點(diǎn)的序號(hào)i和j；

3.2生成鄰接點(diǎn)序號(hào)為j的邊表結(jié)點(diǎn)s；

3.3將結(jié)點(diǎn)s插入到第i個(gè)邊表的頭部；

3.4生成鄰接點(diǎn)序號(hào)為i的邊表結(jié)點(diǎn)s；

3.5將結(jié)點(diǎn)s插入到第j個(gè)邊表的頭部；59建立鄰接表的主要操作是在鏈表中插入一個(gè)結(jié)點(diǎn)，以下是輸入圖的頂點(diǎn)和邊建立鄰接表的算法。

voidCreatgraphlist(vexnodega[])//建立無向圖的鄰接表{inti,j,k;

edgenode

*s;

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

{ga[i].vertex=getchar();

//讀入頂點(diǎn)信息

ga[i].link=NULL;

//對邊表的頭指針初始化

}//頂點(diǎn)表初始化頂點(diǎn)表數(shù)組的基地址無向圖鄰接表的建立算法60for(k=0;k<e;k++)//采用頭插法建立邊表{scanf(“%d%d”,&i,&j);//讀入邊(vi,vj)的頂點(diǎn)序號(hào)（數(shù)組下標(biāo)）

s=(edgenode*)malloc(sizeof(edgenode));//生成鄰接點(diǎn)序號(hào)為j的邊表結(jié)點(diǎn)s

s->adjvex=j;

s->next=ga[i].link;//①將s插入頂點(diǎn)vi的邊表頭部

ga[i].link=s;//②

s=(edgenode*)malloc(sizeof(edgenode));//生成鄰接點(diǎn)序號(hào)為i的邊表結(jié)點(diǎn)s

s->adjvex=i;

s->next=ga[j].link;

//①將s插入頂點(diǎn)vj的邊表頭部

ga[j].link=s;//②

}}//Creatgraphlist時(shí)間復(fù)雜度O(n+e)12V0V1

V2V30123∧∧∧∧①②s鄰接表的建立算法說明對于無向圖，每輸入一條邊需要生成兩個(gè)結(jié)點(diǎn)，分別插入在這條邊的兩個(gè)頂點(diǎn)的鏈表中。即無向圖的鄰接表中邊結(jié)點(diǎn)的個(gè)數(shù)為圖中邊的數(shù)目的兩倍。對于有向圖，鄰接表中弧結(jié)點(diǎn)的個(gè)數(shù)與圖中邊的數(shù)目相等。61圖的存儲(chǔ)結(jié)構(gòu)的比較:鄰接矩陣和鄰接表62O(n2)O(n+e)O(n2)O(n+e)空間性能時(shí)間性能適用范圍唯一性鄰接矩陣鄰接表稠密圖稀疏圖唯一不唯一7.3圖的遍歷圖的遍歷是指從圖中某一頂點(diǎn)出發(fā)，沿著某條搜索路徑使圖中每個(gè)頂點(diǎn)僅被訪問一次。圖的遍歷操作要解決的關(guān)鍵問題

①在圖中，如何選取遍歷的起始頂點(diǎn)？解決方案：從編號(hào)小的頂點(diǎn)開始。在圖中，任何兩個(gè)頂點(diǎn)之間都可能存在邊，頂點(diǎn)是沒有確定的先后次序的，所以，頂點(diǎn)的編號(hào)不唯一。為了定義操作的方便，將圖中的頂點(diǎn)按任意順序排列起來，比如，按頂點(diǎn)的存儲(chǔ)順序。6364②從某個(gè)起點(diǎn)始可能到達(dá)不了所有其它頂點(diǎn)，怎么辦？

解決方案：多次調(diào)用從某頂點(diǎn)出發(fā)遍歷圖的算法。僅討論從某頂點(diǎn)出發(fā)遍歷圖的算法。③因圖中可能存在回路，某些頂點(diǎn)可能會(huì)被重復(fù)訪問，那么如何避免遍歷不會(huì)因回路而陷入死循環(huán)?解決方案：附設(shè)訪問標(biāo)志數(shù)組visited[n]。④在圖中，一個(gè)頂點(diǎn)可以和其它多個(gè)頂點(diǎn)相連，當(dāng)這樣的頂點(diǎn)訪問過后，如何選取下一個(gè)要訪問的頂點(diǎn)？解決方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。7.3.1深度優(yōu)先搜索遍歷基本思想

：⑴訪問頂點(diǎn)v；⑵從v的未被訪問的鄰接點(diǎn)中選取一個(gè)頂點(diǎn)w，從w出發(fā)進(jìn)行深度優(yōu)先遍歷；⑶重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。65深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?深度優(yōu)先搜索遍歷V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5

V5棧深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8

V8深度優(yōu)先搜索遍歷棧深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8深度優(yōu)先搜索遍歷棧深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1

V7V2V4V5V8V3

V3V6

V6V7深度優(yōu)先搜索遍歷棧7.3.1深度優(yōu)先搜索遍歷對于一個(gè)圖，按深度優(yōu)先搜索遍歷先后順序得到的頂點(diǎn)序列稱為圖的深度優(yōu)先搜索遍歷序列（簡稱DFS序列,depth-firstsearch）。一個(gè)圖的DFS序列并不唯一，它與遍歷算法（選擇Vj的原則）、圖的存儲(chǔ)結(jié)構(gòu)和初始出發(fā)點(diǎn)有關(guān)。707.3.1深度優(yōu)先搜索遍歷從頂點(diǎn)V0出發(fā)的深度遍歷序列：

A、B、C、E、D從頂點(diǎn)V1出發(fā)的深度遍歷序列：

B、A、D、E、C從頂點(diǎn)V2出發(fā)的深度遍歷序列：

C、B、A、D、E717.3.1深度優(yōu)先搜索遍歷當(dāng)確定了按照鄰接點(diǎn)的序號(hào)從小到大進(jìn)行選擇鄰接點(diǎn)時(shí)，確定了初始出發(fā)點(diǎn)，同時(shí)鄰接矩陣或者鄰接表也確定后，DFS就唯一了。對于鄰接表存儲(chǔ)，也就是要確定鄰接表中結(jié)點(diǎn)的鏈接次序。727.3.1深度優(yōu)先搜索遍歷DFS:ABCED7373頂點(diǎn)表邊表/鄰接鏈表

A

B

C

D

1

3

1

0

4

0

E

0

2

4

1

∧

∧

∧

∧

∧

74鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，深度優(yōu)先遍歷算法：intvisited[n];//定義visited為全局變量，n為頂點(diǎn)數(shù)graphg;//g為全局變量voidDFSA(inti)//從vi出發(fā)深度優(yōu)先搜索圖g，g用鄰接矩陣表示{intj;printf(“node:%c\n”,g.vexs[i]);//訪問出發(fā)點(diǎn)vi

visited[i]=1;//標(biāo)記vi已被訪問

for(j=0;j<n;j++)//按頂點(diǎn)序號(hào)從小到大依次搜索vi的某個(gè)鄰接點(diǎn)

if((g.arcs[i][j]==1)&&(visited[j]==0))

DFSA(j);//若vi的鄰接點(diǎn)vj未被訪問過，則從vj出發(fā)進(jìn)行深度優(yōu)先搜索遍歷}//DFSA時(shí)間復(fù)雜度O(n2)75鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)，深度優(yōu)先搜索遍歷算法：voidDFSL(inti)//從vi出發(fā)深度優(yōu)先搜索遍歷圖ga，用鄰接表表示{edgenodep;

printf(“node:%c\n”,ga[i].vertex);//訪問頂點(diǎn)vi

visited[i]=1;//標(biāo)記vi已被訪問

p=ga[i].link;//取vi的邊表頭指針

while(p!=NULL)//依次搜索vi的鄰接點(diǎn)

{if(visited[p->adjvex]==0)

DFSL(p->adjvex);//從vi的未曾訪問過的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷

p=p->next;

}}//DFSL

時(shí)間復(fù)雜度O(n+e)注：由于圖的鄰接表表示不唯一，所以DFSL算法得到的DFS序列也不唯一。7.3.2廣度優(yōu)先搜索遍歷基本思想：⑴訪問頂點(diǎn)v；⑵依次訪問v的各個(gè)未被訪問的鄰接點(diǎn)v1,v2,…,vk；⑶分別從v1，v2，…，vk出發(fā)依次訪問它們未被訪問的鄰接點(diǎn)，并使“先被訪問頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問頂點(diǎn)的鄰接點(diǎn)”被訪問。(4)直至圖中所有與頂點(diǎn)v有路徑相通的頂點(diǎn)都被訪問到。767.3.2廣度優(yōu)先搜索遍歷注：廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過程，其算法也不是遞歸的。和樹的廣度優(yōu)先搜索一樣，用隊(duì)列實(shí)現(xiàn)。7778廣度優(yōu)先搜索遍歷的順序和結(jié)束條件:根據(jù)廣度遍歷思想，先遍歷的結(jié)點(diǎn)，其相鄰結(jié)點(diǎn)一定首先被遍歷。

故采用隊(duì)列來構(gòu)造遍歷順序。對于連通圖，結(jié)束條件是隊(duì)列為空；對于非連通圖，結(jié)束條件是隊(duì)列為空并且圖的所有結(jié)點(diǎn)都被遍歷。7.3.2廣度優(yōu)先搜索遍歷廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V1廣度優(yōu)先搜索遍歷廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V3廣度優(yōu)先搜索遍歷廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V5廣度優(yōu)先搜索遍歷廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V7廣度優(yōu)先搜索遍歷廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V8廣度優(yōu)先搜索遍歷84BFSA：以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)時(shí)的廣度優(yōu)先搜索遍歷算法。BFSL：以鄰接表為存儲(chǔ)結(jié)構(gòu)時(shí)的廣度優(yōu)先搜索遍歷算法。一個(gè)圖的BFSA和BFSL序列都不唯一，它與算法、存儲(chǔ)結(jié)構(gòu)和初始出發(fā)點(diǎn)有關(guān)。當(dāng)確定了按照序號(hào)（下標(biāo)）從小到大的方式進(jìn)行選擇鄰接點(diǎn)，確定了初始出發(fā)點(diǎn)后，以鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)得到的BFSA就唯一了。當(dāng)采用鄰接表存儲(chǔ)時(shí)還必須確定邊表結(jié)點(diǎn)的鏈接次序，BFSL才唯一。85鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，廣度優(yōu)先搜索遍歷算法如下：voidBFSA(intk)//從vk出發(fā)廣度優(yōu)先搜索遍歷圖g，g用鄰接矩陣表示{ int i,j;

SETNULL(*sq);//sq置為空隊(duì)

printf(“%c\n”,g.vexs[k]);//訪問出發(fā)點(diǎn)vk

visited[k]=1;//標(biāo)記vk已被訪問

ENQUEUE(*sq);//訪問過的頂點(diǎn)序號(hào)入隊(duì),為訪問它的鄰接點(diǎn)作準(zhǔn)備

while(!EMPTY(*sq))//隊(duì)非空時(shí)執(zhí)行下列操作

{i=DEQUEUE(*sq);//隊(duì)頭元素序號(hào)出隊(duì)

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

if((g.arcs[i][j]==1)&&(visited[j]!=1))

{printf(“%c\n”,g.vexs[j]);visited[j]=1;

ENQUEUE(sq,j);//訪問過的頂點(diǎn)入隊(duì)

}//按頂點(diǎn)序號(hào)從小到大的順序，訪問未曾訪問的vi的鄰接點(diǎn)vj

}}//BFSA86鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)，廣度優(yōu)先搜索遍歷算法如下：voidBFSL(intk)//從vk出發(fā)廣度優(yōu)先搜索遍歷鄰接表圖ga{ inti;edgenodep;

SETNULL(sq);//置空隊(duì)

printf(“%c\n”,ga[k].vertex);//訪問出發(fā)點(diǎn)vk

visited[k]=1;//標(biāo)記vk已被訪問

ENQUEUE(sq,k);//訪問過的頂點(diǎn)序號(hào)入隊(duì),為訪問它的鄰接點(diǎn)作準(zhǔn)備

while(!EMPTY(sq))

{i=DEQUEUE(sq);//隊(duì)頭元素序號(hào)出隊(duì)

p=ga[i].link;//取vi的邊表頭指針

while(p!=NULL)//依次搜索vi的鄰接點(diǎn)

{if(visited[p->adjvex]!=1)//vi的鄰接點(diǎn)未曾訪問

{printf(“%c\n”,ga[p->adjvex].vertex);

visited[p->adjvex]=1;

ENQUEUE(sequeue*sq,p->adjvex);//訪問過的頂點(diǎn)入隊(duì)

}p=p->next;

}

}}//BFSL87圖的廣度優(yōu)先遍歷實(shí)例:以下圖為例說明，從結(jié)點(diǎn)A開始ADBCEFG01324560123456visited[]queue初始狀態(tài)frADBCEFG01324560123456visited[]queuefr訪問開始結(jié)點(diǎn)A，并將A的序號(hào)入隊(duì)10r880123456visited[]1queue0fr0123456visited[]1queue0frfADBCEFG0132456ADBCEFG0132456A的序號(hào)出隊(duì)，同時(shí)訪問其所有的鄰接點(diǎn)：B,C并將B,C的下標(biāo)按照次序依次入隊(duì)1rr2111211序號(hào)為1的B出隊(duì)，同時(shí)訪問其所有的鄰接點(diǎn)：D,E并將D,E的下標(biāo)按照次序依次入隊(duì)f11rr34890123456visited[]1queue0ADBCEFG01324561211序號(hào)為2的C出隊(duì)，同時(shí)訪問其未被訪問的鄰接點(diǎn)：F并將F的下標(biāo)按照次序依次入隊(duì)f11r34f1r50123456visited[]1queue0ADBCEFG01324561211序號(hào)為3的D出隊(duì)，D鄰接點(diǎn)B已訪問過，不執(zhí)行入隊(duì)操作1134f1r5f900123456visited[]1queue0ADBCEFG01324561211序號(hào)為4的E出隊(duì)同時(shí)訪問其未被訪問的鄰接點(diǎn)：G并將G的下標(biāo)按照次序依次入隊(duì)11341r5ff1r60123456visited[]1queue0ADBCEFG01324561211序號(hào)為5的F出隊(duì)F鄰接點(diǎn)C，G已訪問過，不執(zhí)行入隊(duì)操作113415f1r6f910123456visited[]1queue0ADBCEFG01324561211序號(hào)為6的G出隊(duì)G的鄰接點(diǎn)E,F已訪問過，不執(zhí)行入隊(duì)操作1134151r6ff此時(shí)，隊(duì)列已空。搜索過程結(jié)束。根據(jù)訪問的順序，得到的BFS序列為A，B，C，D，E，F(xiàn)，G7.4生成樹和最小生成樹樹：圖論中的樹是指一個(gè)沒有回路的連通圖。生成樹：一個(gè)連通圖G的生成樹指的是一個(gè)包含了G的所有頂點(diǎn)的樹，是一個(gè)具有n個(gè)頂點(diǎn)n-1條邊的極小連通子圖.92多——構(gòu)成回路少——不連通含有n-1條邊V0V1V2V3V4V0V1V2V3V4生成樹7.4生成樹和最小生成樹構(gòu)造無向圖的生成樹的方法：

給定一個(gè)無向連通圖G，從G的任意頂點(diǎn)Vi出發(fā)，作一次深度優(yōu)先或廣度優(yōu)先搜索遍歷，遍歷過程中所經(jīng)歷過的n-1條邊就構(gòu)成了G的生成樹，頂點(diǎn)Vi是生成樹的根。937.4生成樹和最小生成樹94

深度優(yōu)先搜索生成樹（DFS生成樹）

廣度優(yōu)先搜索生成樹（BFS生成樹）生成樹連通圖的生成樹不是唯一的，它取決于遍歷算法和遍歷的起始頂點(diǎn)。在遍歷算法確定之后，從不同頂點(diǎn)出發(fā)進(jìn)行遍歷得到的生成樹可能不同。對于非連通圖，生成的是包含若干棵樹的森林。95鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，構(gòu)造DFS生成樹的算法intvisited[n];//定義visited為全局變量，n為頂點(diǎn)數(shù)

graph*g=(graph*)malloc((sizeof(graph));//產(chǎn)生圖的存儲(chǔ)空間voidDFSA(inti)//從vi出發(fā)，構(gòu)造*g的DFS生成樹{intj;printf(“node:%c\n”,g->vexs[i]);//訪問出發(fā)點(diǎn)vi

visited[i]=1;//標(biāo)記vi已被訪問

for(j=0;j<n;j++)//按頂點(diǎn)序號(hào)從小到大依次搜索vi的某個(gè)鄰接點(diǎn)

if((g->arcs[i][j]==1)&&(visited[j]==0)){printf(“(v%d,v%d)\n”,i,j);//輸出邊（vi，vj）

DFSA(j);}//若vi的鄰接點(diǎn)vj未被訪問過，則從vj出發(fā)進(jìn)行深度優(yōu)先搜索遍歷}//DFSA96鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，構(gòu)造BFS生成樹的算法voidBFSA(intk)//從vk出發(fā)廣度優(yōu)先搜索遍歷圖g，g用鄰接矩陣表示{ int i,j;

SETNULL(*sq);//sq置為空隊(duì)

printf(“%c\n”,g.vexs[k]);//訪問出發(fā)點(diǎn)vk

visited[k]=1;//標(biāo)記vk已被訪問

ENQUEUE(*sq);//訪問過的頂點(diǎn)序號(hào)入隊(duì),為訪問它的鄰接點(diǎn)作準(zhǔn)備

while(!EMPTY(*sq))//隊(duì)非空時(shí)執(zhí)行下列操作

{i=DEQUEUE(*sq);//隊(duì)頭元素序號(hào)出隊(duì)

for(j=0;j<n;j++)//if((g.arcs[i][j]==1)&&(visited[j]!=1))

{printf(“(v%d,v%d)\n”,i,j);//輸出邊（vi，vj）

printf(“%c\n”,g.vexs[j]);visited[j]=1;

ENQUEUE(sq,j);//訪問過的頂點(diǎn)入隊(duì)

}//按頂點(diǎn)序號(hào)從小到大的順序，訪問未曾訪問的vi的鄰接點(diǎn)vj

}}//BFSA例：從頂點(diǎn)A出發(fā)的DFS生成樹和BFS生成樹。977.4生成樹和最小生成樹ABDCEABDCEDFS生成樹ABDCEBFS生成樹98最小生成樹的應(yīng)用背景：例1：由于在n個(gè)居民點(diǎn)間構(gòu)建通訊網(wǎng)只需架設(shè)n-1條線路，則工程隊(duì)面臨的問題是架設(shè)哪幾條線路能使總的工程費(fèi)用最低？

例2：n個(gè)城市之間鋪設(shè)煤氣管道問題等。類似此類的問題很多。這些問題均等價(jià)于，在含有n個(gè)頂點(diǎn)的連通網(wǎng)中選擇n-1條邊，構(gòu)成一棵極小連通子圖，并使該連通子圖中n-1條邊上權(quán)值之和達(dá)到最小的問題。7.4生成樹和最小生成樹最小生成樹（MST）：對一個(gè)連通網(wǎng)絡(luò)構(gòu)造生成樹，可以得到一棵帶權(quán)的生成樹。我們把生成樹各邊的權(quán)值總和作為生成樹的權(quán)值，而具有最小權(quán)值的生成樹就是連通網(wǎng)絡(luò)的最小生成樹。構(gòu)造準(zhǔn)則:盡可能用網(wǎng)絡(luò)中權(quán)值最小的邊；必須使用且僅使用n-1條邊來連接網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)；不能使用產(chǎn)生回路的邊。997.4生成樹和最小生成樹構(gòu)造最小生成樹的兩種算法1.prim（普里姆）算法2.Kruskal(克魯斯卡爾)算法1007.4生成樹和最小生成樹1017.4.2prim（普里姆）算法設(shè)G(V,E)是有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)，T=(U,TE)是要構(gòu)造的生成樹。初始時(shí)U={φ}，TE={φ}。首先從V中取出一個(gè)頂點(diǎn)u0放入生成樹的頂點(diǎn)集U中作為第一個(gè)頂點(diǎn)(根結(jié)點(diǎn)），此時(shí)T=({u0},{φ})；然后從uU，vV-U的邊(u,v)中找一條代價(jià)最小的邊(u*,v*)放入TE中，且將v*放入U(xiǎn)中，此時(shí)T=({u0,v*},{(u0,v*)})；重復(fù)（2），直到U=V為止。這時(shí)T的TE中必有n-1條邊，構(gòu)成所要構(gòu)造的最小生成樹。關(guān)鍵:是如何找到連接U和V-U的最短邊。102在生成樹的構(gòu)造過程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的頂點(diǎn)集U和尚未落在生成樹上的頂點(diǎn)集V-U，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。

一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件:UV-U103Prim算法構(gòu)造最小生成樹實(shí)例以下圖為例說明構(gòu)造過程，從頂點(diǎn)0開始801234510321117657V012345UV-U012345TE801234510321117657V012345U0V-U12345TE0,220104801234510321117657V012345U02V-U1345TE0,2801234510321117657V012345U024V-U135TE0,22,42,42,141105801234510321117657V012345U0241V-U35TE0,22,42,14,3801234510321117657V012345U02413V-U5TE0,22,42,14,33,535106801234510321117657V012345U024135V-UTE0,22,42,14,33,5012345321157107顯然，prim算法的關(guān)鍵是如何找到連接U和V-U的最短邊來擴(kuò)充T。設(shè)當(dāng)前生成樹T中已有K個(gè)頂點(diǎn)，則U和V-U中可能存在的邊數(shù)最多為K（n-K）條，在如此多的邊總尋找一條代價(jià)最小的邊是困難的。由于尋找過程具有可重復(fù)性，所以可通過將前一次所尋找得到的最小邊存儲(chǔ)起來，然后與新找到的邊進(jìn)行比較，如果新邊短，則替換，否則不替換。7.4.2prim（普里姆）算法1087.4.2prim（普里姆）算法邊的存儲(chǔ)結(jié)構(gòu)：typedefstruct{intfromvex,endvex;//邊的起點(diǎn)和終點(diǎn)

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

T[n-1];//最小生成樹，有n-1條邊圖的存儲(chǔ)結(jié)構(gòu)：由于在算法執(zhí)行過程中，需要不斷讀取任意兩個(gè)頂點(diǎn)之間邊的權(quán)值，所以，圖采用鄰接矩陣存儲(chǔ)。float

dist[n][n];//連通網(wǎng)絡(luò)的帶權(quán)鄰接矩陣109算法7.7最小生成樹的Prim算法。voidPrim(inti) //i表示最小生成樹所選取的第一個(gè)頂點(diǎn)下標(biāo){intj,k,m,v,min,max=100000;

floatd;

edgee;v=i; //將選定頂點(diǎn)送入中間變量vfor(j=0;j<=n-2;j++) //構(gòu)造第一個(gè)頂點(diǎn)

{T[j].fromvex=v;if(j>=v)

{T[j].endvex=j+1;T[j].length=dist[v][j+1];}else

{T[j].endvex=j;T[j].length=dist[v][j];}}7.4.2prim（普里姆）算法11001234500103∞∞∞1100586∞2350∞2∞3∞8∞07114∞6270175∞∞∞11170鄰接矩陣dist[6][6];fromvexendvexlength01234T[5],n=60000012435103∞∞∞V=0;801234510321117657111for(k=0;k<n-1;k++)//求第k條邊{

min=max;for(j=k;j<n-1;j++)//找出最短的邊，并將最短邊的下標(biāo)記錄在m中

{if(T[j].length<min)

{min=T[j].length;m=j;}}e=T[m];T[m]=T[k];T[k]=e;//將最短的邊交換到T[k]單元中v=T[k].endvex;//存放新找到的最短邊在V-U中的頂點(diǎn)

for(j=K+1;j<n-1;j++)//修改所存儲(chǔ)的最小邊集

{d=dist[v][T[j].endvex];

if(d<T[j].length)

{T[j].length=d;T[j].fromvex=v;}}}}fromvexendvexlength01234112T[5],n=60000012435103∞∞∞max=10000;min=max;min=T[j].length<min?T[j].length:min;k=0;m=j;V=T[k].endvex=2V=0;113fromvexendvexlength012340000021435310∞∞∞k=0;d=dist[v][T[j].endvex]j=K+1,K+2,…,n-2V=2if(d<T[j].length)

{T[j].length=d;T[j].fromvex=v;}25d[2][1]=5新起點(diǎn)可能的終點(diǎn)d[2][3]=∞d[2][4]=222d[2][5]=∞修改存儲(chǔ)的最小邊集T[5],n=6114fromvexendvexlength01234000214353∞∞k=1;2522T[5],n=6時(shí)間復(fù)雜度O(n2)，與網(wǎng)的邊數(shù)無關(guān)。適合邊稠密網(wǎng)絡(luò)的最小生成樹1157.4.3Kruskal(克魯斯卡爾)算法克魯斯卡爾算法的基本思想：為使生成樹上總的權(quán)值之和達(dá)到最小，則應(yīng)使每一條邊上的權(quán)值盡可能地小。自然應(yīng)從權(quán)值最小的邊選起，直至選出n-1條互不構(gòu)成回路的權(quán)值最小邊為止。1167.4.3Kruskal(克魯斯卡爾)算法具體作法如下：首先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的森林V；然后依權(quán)值從小到大從連通網(wǎng)中選擇不使森林中產(chǎn)生回路的邊加入到森林中去直至該森林變成一棵樹為止這棵樹便是連通網(wǎng)的最小生成樹。

117

問題：由于生成樹上不允許有回路，因此并非每一條當(dāng)前權(quán)值最小的邊都可選。那么在算法中如何判別當(dāng)前權(quán)值最小邊的兩個(gè)頂點(diǎn)之間是否已經(jīng)連通？從生成樹的構(gòu)造過程可見，初始態(tài)為n個(gè)頂點(diǎn)分屬n棵樹，互不連通，每加入一條邊，就將兩棵樹合并為一棵樹，在同一棵樹上的兩個(gè)頂點(diǎn)之間自然相連通。由此判別當(dāng)前權(quán)值最小邊是否可取只要判別它的兩個(gè)頂點(diǎn)是否在同一棵樹（連通分量）上即可。

7.4.3Kruskal(克魯斯卡爾)算法118V012345TE21041321856101961451133041325初始連通分量T=（V,TE）0413255V012345TE加入（1,2）后的連通分量21041321856101961451133（1,2）119由于(2,3)和(1,3)的權(quán)值都是6，因此可以加入(2,3)或者(1,3)V012345TE（1,2）加入（2,3）后的連通分量2104132185610196145113304132556(2,3)V012345TE（1,2）（2,3）加入（0,5）后的連通分量210413218561019614511330413255610(0,5)120V012345TE（1,2）（2,3）（0,5）加入（1,5）后的連通分量21041321856101961451133041325561011V01234