《數(shù)據(jù)結(jié)構(gòu)》考研課程第五章圖

本節(jié)內(nèi)容圖圖ACEBD樹(shù)是N（N≥0）個(gè)結(jié)點(diǎn)的有限集合，N=0時(shí)，稱(chēng)為空樹(shù)，這是一種特殊情況。在任意一棵非空樹(shù)中應(yīng)滿(mǎn)足：1）有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)。2）當(dāng)N>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集合T1，T2，…，Tm，其中每一個(gè)集合本身又是一棵樹(shù)，并且稱(chēng)為根結(jié)點(diǎn)的子樹(shù)。F圖G由頂點(diǎn)集V和邊集E組成，記為G=(V，E)V(G)表示圖G中頂點(diǎn)的有限非空集。用|V|表示圖G中頂點(diǎn)的個(gè)數(shù)，也稱(chēng)為圖G的階。E(G)表示圖G中頂點(diǎn)之間的關(guān)系（邊）集合。用|E|表示圖G中邊的條數(shù)。VertexEdge圖不可為空，一個(gè)圖中就算是一條邊都沒(méi)有，也就是邊集為空，但是頂點(diǎn)集一定不為空。圖的基本概念A(yù)BCABC無(wú)向圖G2有向圖G1G1=(V1，E1)V1={A，B，C}E1={<A，B>，<B，A>，<A，C>}G2=(V2，E2)V2={A，B，C}E2={(A，B)，(A，C)，(B，C)}圖的基本概念A(yù)BCABC圖的基本概念A(yù)BCABC對(duì)于n個(gè)頂點(diǎn)每個(gè)頂點(diǎn)都與其他n-1個(gè)頂點(diǎn)有一條邊，由于重復(fù)，所以一共有n*(n-1)/2條邊每個(gè)頂點(diǎn)都與其他n-1個(gè)頂點(diǎn)有一條邊，由于有方向不重復(fù)，所以一共有n*(n-1)條邊圖的基本概念若有滿(mǎn)足V(G’)=V(G)的子圖G’，則為G的生成子圖ACA并非V和E的任何子集都能構(gòu)成G的子圖，因?yàn)檫@樣的子集可能不是圖，也就是說(shuō)，E的子集中的某些邊關(guān)聯(lián)的頂點(diǎn)可能不在這個(gè)V的子集中。G=(V，E)V={A，B，C}E={<A，B>，<B，A>，<A，C>}ABCG’=(V’，E’)V’={C}E’={<A，B>，<B，A>}子圖(a)子圖(b)B圖的基本概念A(yù)BDCEFG=(V，E)V={A，B，C，D，E，F(xiàn)}E={(A，B)，(B，C)，(C，D)，(D，A)，(E，F(xiàn))}如果右圖看成一個(gè)圖則是不連通的找連通分量的方法：從選取一個(gè)頂點(diǎn)開(kāi)始，以這個(gè)頂點(diǎn)作為一個(gè)子圖，然后逐個(gè)添加與這個(gè)子圖相連的頂點(diǎn)和邊直到所有相連的頂點(diǎn)都加入該子圖結(jié)論1:如果一個(gè)圖有n個(gè)頂點(diǎn)，并且有小于n-1條邊，則此圖必是非連通圖。圖的基本概念A(yù)BCDG=(V，E)V={A，B，C，D}E={<A，B>，<B，C>，<C，A>，<C，D>}不連通ABCD強(qiáng)連通分量圖的基本概念A(yù)BCDEF6個(gè)頂點(diǎn)，7條邊ABCDEF6個(gè)頂點(diǎn)，5條邊結(jié)論2:生成樹(shù)去掉一條邊則變成非連通圖，加上一條邊就會(huì)形成回路。圖的基本概念

ABC無(wú)向圖ABC有向圖無(wú)向圖：有向圖：TD(v)=ID(v)+OD(v)

ABC有向樹(shù)圖的基本概念A(yù)BCD1000A->B->C->D->A路徑長(zhǎng)度為4A->B->C->A->D和A->B->C->DB和D的距離為2圖的基本概念本節(jié)內(nèi)容圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)相比線性表和樹(shù)顯得更復(fù)雜圖中頂點(diǎn)沒(méi)有次序之分圖中邊和頂點(diǎn)的數(shù)量任意鄰接矩陣頂點(diǎn)：用一維數(shù)組來(lái)存儲(chǔ)邊或?。河枚S數(shù)組來(lái)存儲(chǔ)二維數(shù)組就是一維數(shù)組的拓展，相當(dāng)于一維數(shù)組中每個(gè)元素也是一個(gè)一維數(shù)組。二維數(shù)組也叫做鄰接矩陣a[0]a[1]a[2]a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]a[2][0]a[2][1]a[2][2]3*3二維數(shù)組ABCD頂點(diǎn)數(shù)組：ABCD邊或弧數(shù)組：ABCDABCD0000a[i][j]=1

若(vi,vj)或<vi,vj>是E(G)中的邊0

若(vi,vj)或<vi,vj>不是E(G)中的邊111111111010無(wú)向圖的鄰接矩陣是一個(gè)對(duì)稱(chēng)矩陣1.判定兩個(gè)頂點(diǎn)是否有邊2.求某個(gè)頂點(diǎn)的度3.找到某個(gè)頂點(diǎn)的所有鄰接點(diǎn)因此可以只存儲(chǔ)上半部分矩陣鄰接矩陣ABCD頂點(diǎn)數(shù)組：ABCD邊或弧數(shù)組：ABCDABCD00001010111100001.頂點(diǎn)的入度是頂點(diǎn)所在這一列的各數(shù)之和；出度是頂點(diǎn)所在這一行的各數(shù)之和。2.判定兩個(gè)頂點(diǎn)是否有邊3.找到某個(gè)頂點(diǎn)的所有鄰接點(diǎn)對(duì)于帶權(quán)圖(網(wǎng))可以在矩陣中存儲(chǔ)邊的權(quán)值A(chǔ)BCD586732ABCDABCD00005∞86732∞∞∞∞∞1、帶權(quán)邊存儲(chǔ)權(quán)值2、行和列相同結(jié)點(diǎn)權(quán)值為03、不存在的邊權(quán)值為無(wú)限大鄰接矩陣#defineMaxVertexNuml00 //頂點(diǎn)數(shù)目的最大值typedef

charVertexType; //頂點(diǎn)的數(shù)據(jù)類(lèi)型不同情況不一樣typedefintEdgeType; //整數(shù)表示權(quán)值或者連通性typedefstruct{ VertexTypeVex[MaxVertexNum]; //頂點(diǎn)表

EdgeTypeEdge[MaxVertexNum][MaxVertexNum]; //鄰接矩陣(二維數(shù)組)，邊表

intvexnum,arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}MGraph;由于鄰接矩陣基于二維數(shù)組，所以利用二維數(shù)組創(chuàng)建圖的時(shí)間復(fù)雜度為O(n2)，其中n為圖的頂點(diǎn)數(shù)。所以當(dāng)頂點(diǎn)數(shù)較多時(shí)，鄰接矩陣的復(fù)雜度也會(huì)比較大。鄰接表對(duì)于稀疏圖(|E|遠(yuǎn)小于|V|2)ABCDABCDABCD0000100000000000浪費(fèi)存儲(chǔ)空間順序存儲(chǔ)結(jié)構(gòu)存在預(yù)先分配內(nèi)存可能浪費(fèi)的問(wèn)題，按照經(jīng)驗(yàn)會(huì)想到鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)adbcefdataabcdef下標(biāo)012345firstchild^^^13524^^^孩子表示法鄰接表dataABCD下標(biāo)0123firstedge1ABCD23^02^013^02^圖中的頂點(diǎn)用一個(gè)一維數(shù)組存儲(chǔ)。同時(shí)每個(gè)元素還要存儲(chǔ)指向第一個(gè)鄰接點(diǎn)的指針(鏈表的頭指針)。存儲(chǔ)頂點(diǎn)和頭指針的表叫頂點(diǎn)表圖中每個(gè)頂點(diǎn)的所有鄰接點(diǎn)構(gòu)成一個(gè)單鏈表。對(duì)于無(wú)向圖，這個(gè)表稱(chēng)為該結(jié)點(diǎn)的邊表，對(duì)于有向圖稱(chēng)為該結(jié)點(diǎn)的出邊表頂點(diǎn)表邊表鄰接表dataABCD下標(biāo)0123firstedge1ABCD2^2^3^0^注意是以頂點(diǎn)為弧尾需要設(shè)計(jì)兩種結(jié)點(diǎn)結(jié)構(gòu)類(lèi)型：一是頂點(diǎn)表的頂點(diǎn)，二是單鏈表的結(jié)點(diǎn)#defineMaxVertexNum100//圖中頂點(diǎn)數(shù)目的最大值typedefstructArcNode{ //邊表結(jié)點(diǎn)

intadjvex; //該弧所指向的頂點(diǎn)的位置

structArcNode*next;//指向下一條弧的指針}ArcNode;typedefstructVNode{ //頂點(diǎn)表結(jié)點(diǎn)

VertexTypedata; //頂點(diǎn)信息

ArcNode*firstedge; //單鏈表頭指針}VNode,AdjList[MaxVertexNum];//AdjList是結(jié)構(gòu)體數(shù)組類(lèi)型typedefstruct{ AdjListvertices; //鄰接表

intvexnum,arcnum; //圖的頂點(diǎn)數(shù)和弧數(shù)}ALGraph; //ALGraph是以鄰接表存儲(chǔ)的圖類(lèi)型十字鏈表dataABCD下標(biāo)0123firstedge1ABCD2^2^3^0^注意是以頂點(diǎn)為弧尾有向圖的鄰接表關(guān)心了有向圖的出邊問(wèn)題，我們通過(guò)有向圖很容易找到頂點(diǎn)的出邊比如從每個(gè)頂點(diǎn)表的firstedge指針找到第一條邊的頂點(diǎn)，再通過(guò)next指針依次找到下一條邊的頂點(diǎn)直到空指針。但是，如果要找到其他頂點(diǎn)到該頂點(diǎn)的邊，或者說(shuō)考慮一個(gè)頂點(diǎn)的入度問(wèn)題，則需要遍歷整個(gè)圖。這是鄰接表存儲(chǔ)有向圖的缺陷。十字鏈表十字鏈表是針對(duì)有向圖的存儲(chǔ)方式，對(duì)應(yīng)于有向圖中的每條弧有一個(gè)結(jié)點(diǎn)，對(duì)應(yīng)于每個(gè)頂點(diǎn)也有一個(gè)結(jié)點(diǎn)datafirstoutfirstin頂點(diǎn)結(jié)點(diǎn)headvextaillinkheadlinktailvex邊表結(jié)點(diǎn)圖中頂點(diǎn)的數(shù)據(jù)該頂點(diǎn)的入邊表的頭指針該頂點(diǎn)的出邊表的頭指針這條弧的弧尾(起點(diǎn))所在頂點(diǎn)表下標(biāo)這條弧的弧頭(終點(diǎn))所在頂點(diǎn)表下標(biāo)指向弧頭(終點(diǎn))相同的下一條邊指向弧尾(起點(diǎn))相同的下一條邊其實(shí)十字鏈表是在鄰接表的基礎(chǔ)上進(jìn)行了優(yōu)化。在十字鏈表中不僅包含了鄰接表本身就包含的結(jié)點(diǎn)出度結(jié)點(diǎn)，而且還包含了入度結(jié)點(diǎn)的信息。十字鏈表ABCDABCD01下標(biāo)0123入邊表出邊表02弧尾弧頭相同弧頭相同弧尾12^(A->B)(A->C)(B->C)21(C->B)30^(D->A)23(C->D)^^^^^^該頂點(diǎn)的出邊該頂點(diǎn)的入邊十字鏈表的存儲(chǔ)形式不唯一十字鏈表datafirstoutfirstin頂點(diǎn)結(jié)點(diǎn)headvextaillinkheadlinktailvex邊表結(jié)點(diǎn)圖中頂點(diǎn)的數(shù)據(jù)該頂點(diǎn)的入邊表的頭指針該頂點(diǎn)的出邊表的頭指針這條弧的弧尾(起點(diǎn))所在頂點(diǎn)表下標(biāo)這條弧的弧頭(終點(diǎn))所在頂點(diǎn)表下標(biāo)指向弧頭(終點(diǎn))相同的下一條邊指向弧尾(起點(diǎn))相同的下一條邊typedefstructArcNode{

inttailvex,headvex;

structArcNode*hlink,*tlink; }ArcNode;typedefstructVNode{

VertexTypedata;

ArcNode*firstin,*firstout; }VNode;typedefstruct{ VNodexlist[MaxVertexNum]; //頂點(diǎn)依舊用順序存儲(chǔ)(數(shù)組)

intvexnum,arcnum; //圖的頂點(diǎn)數(shù)和弧數(shù)}GLGraph; //十字鏈表存儲(chǔ)的圖類(lèi)型鄰接多重表ABCDdataABCD下標(biāo)0123firstedge123^02^013^02^頂點(diǎn)表邊表鄰接表存儲(chǔ)的無(wú)向圖中查找頂點(diǎn)是比較容易的，但是如果要修改圖中的邊或者是查詢(xún)邊,則需要遍歷鏈表。這是鄰接表的缺陷。仿照十字鏈表，對(duì)鄰接表的邊表進(jìn)行改造，得到專(zhuān)門(mén)針對(duì)存儲(chǔ)無(wú)向圖的鄰接多重表鄰接多重表ABCDdataABCD下標(biāo)0123firstedge123^02^013^02^頂點(diǎn)表邊表ilinkjlinkjvexivex鄰接多重表邊表結(jié)點(diǎn)這條邊依附的兩個(gè)頂點(diǎn)在頂點(diǎn)表的下標(biāo)指向依附頂點(diǎn)ivex的下一條邊指向依附頂點(diǎn)jvex的下一條邊鄰接多重表ABCDilinkjlinkjvexivex這條邊依附的兩個(gè)頂點(diǎn)在頂點(diǎn)表的下標(biāo)指向依附頂點(diǎn)ivex的下一條邊指向依附頂點(diǎn)jvex的下一條邊ABCD下標(biāo)01230102301223datafirstedge（A-B）（A-C）（D-A）（B-C）（C-D）^^^^本節(jié)內(nèi)容圖的遍歷圖的遍歷圖的遍歷：從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問(wèn)一次，這個(gè)過(guò)程就叫做圖的遍歷。圖中頂點(diǎn)沒(méi)有特殊性，可能存在沿著某條路徑搜索后回到原起點(diǎn)，而有些頂點(diǎn)沒(méi)有訪問(wèn)到。解決辦法：設(shè)置一個(gè)訪問(wèn)數(shù)組,記錄遍歷過(guò)程中訪問(wèn)過(guò)的頂點(diǎn)。BFS廣度優(yōu)先搜索(BFS:Breadth-First-Search):廣度優(yōu)先搜索類(lèi)似于樹(shù)的層序遍歷算法ABCDEFGABCDEFG第一層第二層第三層第四層層序遍歷序列：ABCEFDGBFSvoidBFS(GraphG,intv){ArcNode*p;//工作指針pInitQueue(Q);//初始化一個(gè)隊(duì)列visit(v); //訪問(wèn)第一個(gè)頂點(diǎn)v具體可以是Print visited[v]=TRUE; //對(duì)v做已訪問(wèn)標(biāo)記

Enqueue(Q,v); //頂點(diǎn)v入隊(duì)列

while(!isEmpty(Q)){//只要隊(duì)列不空 DeQueue(Q,v); //頂點(diǎn)v出隊(duì)列

p=G->adjList[v].firstedge;//指針p指向當(dāng)前頂點(diǎn)的邊表鏈表頭指針while(p){

if(!visited[p->adjvex]){ //p所指向頂點(diǎn)如果未被訪問(wèn) visit(p->adjvex); //訪問(wèn)p所指向的頂點(diǎn) visited[p->adjvex]=TRUE;//對(duì)這個(gè)頂點(diǎn)做已訪問(wèn)標(biāo)記

EnQueue(Q,p->adjvex); //這個(gè)頂點(diǎn)入隊(duì)列

}p=p->next；//p指向該頂點(diǎn)的下一條邊 }}}voidBFSTraverse(GraphG){

inti;//單獨(dú)定義是為了方便多個(gè)循環(huán)中使用

for(i=0;i<G->vexnum;i++）visited[i]=false;//將標(biāo)志數(shù)組初始化(全局?jǐn)?shù)組)for(i=0;i<G->vexnum;i++){if(!visited[i])BFS(G,i);}//為了避免非連通圖一些頂點(diǎn)訪問(wèn)不到

若是連通圖只會(huì)執(zhí)行一次}}#defineMaxSize100;boolvisited[MaxSize]；BFSvoidBFS(GraphG,intv){ArcNode*p;InitQueue(Q);visit(v);visited[v]=TRUE;

Enqueue(Q,v);

while(!isEmpty(Q)){ DeQueue(Q,v);

p=G->adjList[v].firstedge;while(p){ If(!visited[p->adjvex]){visit(p->adjvex); visited[p->adjvex]=TRUE;

EnQueue(Q,p->adjvex); }p=p->next；}}}ABCD頂點(diǎn)訪問(wèn)序列：AABCD訪問(wèn)標(biāo)記數(shù)組是否訪問(wèn)falsefalsefalsefalse頂點(diǎn)truetruetruetrueAdataABCD下標(biāo)0123firstedge123^02013^02^BBCCDDE4E^1Efalse4^EtrueEpBFS空間復(fù)雜度：BFS需要借助一個(gè)隊(duì)列，n個(gè)頂點(diǎn)均需要入隊(duì)一次，所以最壞情況下n個(gè)頂點(diǎn)在隊(duì)列，那么則需要O(|V|)的空間復(fù)雜度。voidBFS(GraphG,intv){ArcNode*p;//工作指針pInitQueue(Q);//初始化一個(gè)隊(duì)列visit(v); //訪問(wèn)第一個(gè)頂點(diǎn)v具體可以是Print visited[v]=TRUE; //對(duì)v做已訪問(wèn)標(biāo)記

Enqueue(Q,v); //頂點(diǎn)v入隊(duì)列

while(!isEmpty(Q)){//只要隊(duì)列不空 DeQueue(Q,v); //頂點(diǎn)v出隊(duì)列

p=G->adjList[v].firstedge;//指針p指向當(dāng)前頂點(diǎn)的邊表鏈表頭指針while(p){

if(!visited[p->adjvex]){ //p所指向結(jié)點(diǎn)如果未被訪問(wèn) visit(p->adjvex); //訪問(wèn)p所指向的頂點(diǎn) visited[p->adjvex]=TRUE;//對(duì)這個(gè)頂點(diǎn)做已訪問(wèn)標(biāo)記

EnQueue(Q,p->adjvex); //這個(gè)頂點(diǎn)入隊(duì)列

}p=p->next；//指向該頂點(diǎn)的下一條邊 }}}BFS時(shí)間復(fù)雜度：1)鄰接表：每個(gè)頂點(diǎn)入隊(duì)一次，時(shí)間復(fù)雜度為O(|V|),對(duì)于每個(gè)頂點(diǎn)，搜索它的鄰接點(diǎn)，就需要訪問(wèn)這個(gè)頂點(diǎn)的所有邊，所以時(shí)間復(fù)雜度為O(|E|)。所以總的時(shí)間復(fù)雜度為O(|V|+|E|)2)鄰接矩陣：每個(gè)頂點(diǎn)入隊(duì)一次，時(shí)間復(fù)雜度為O(|V|),對(duì)于每個(gè)頂點(diǎn)，搜索它的鄰接點(diǎn)，需要遍歷一遍矩陣的一行，所以時(shí)間復(fù)雜度為O(|V|),所以總的時(shí)間復(fù)雜度為O(|V|2)voidBFS(GraphG,intv){ArcNode*p;//工作指針pInitQueue(Q);//初始化一個(gè)隊(duì)列visit(v); //訪問(wèn)第一個(gè)頂點(diǎn)v具體可以是Print visited[v]=TRUE; //對(duì)v做已訪問(wèn)標(biāo)記

Enqueue(Q,v); //頂點(diǎn)v入隊(duì)列

while(!isEmpty(Q)){//只要隊(duì)列不空 DeQueue(Q,v); //頂點(diǎn)v出隊(duì)列

p=G->adjList[v].firstedge;//指針p指向當(dāng)前頂點(diǎn)的邊表鏈表頭指針while(p){

if(!visited[p->adjvex]){ //p所指向結(jié)點(diǎn)如果未被訪問(wèn) visit(p->adjvex); //訪問(wèn)p所指向的頂點(diǎn) visited[p->adjvex]=TRUE;//對(duì)這個(gè)頂點(diǎn)做已訪問(wèn)標(biāo)記

EnQueue(Q,p->adjvex); //這個(gè)頂點(diǎn)入隊(duì)列

}p=p->next；//指向該頂點(diǎn)的下一條邊 }}}BFS應(yīng)用voidBFS_MIN_Distance(GraphG,intu){//d[i]表示從u到i結(jié)點(diǎn)的最短路徑

for(i=0;i<G.vexnum;++i)d[i]=∞;//初始化路徑長(zhǎng)度

visited[u]=TRUE;d[u]=0; EnQueue(Q,u); while(!isEmpty(Q)){

DeQueue(Q,u);

ArcNode*p=G->adjList[u].firstedge;while(p){ If(!visited[p->adjvex]){visited[p->adjvex]=TRUE;

//路徑長(zhǎng)度加1

d[p->adjvex]=d[u]+1;

EnQueue(Q,p->adjvex); }p=p->next；}} }ABCDEd[A]=0d[B]=d[A]+1=1d[C]=d[A]+1=1d[D]=d[A]+1=1d[E]=d[B]+1=2BFS解決單源非帶權(quán)圖最短路徑問(wèn)題：按照距離由近到遠(yuǎn)來(lái)遍歷圖中每個(gè)頂點(diǎn)廣度優(yōu)先生成樹(shù)ABCDE如果圖是鄰接矩陣存儲(chǔ)的，廣度優(yōu)先生成樹(shù)唯一。如果圖是鄰接矩陣存儲(chǔ)的，廣度優(yōu)先生成樹(shù)則不唯一。ABCDEACBDEDFS深度優(yōu)先搜索(DFS:Depth-First-Search):深度優(yōu)先搜索類(lèi)似于樹(shù)的先序遍歷算法首先訪問(wèn)圖中某一起始頂點(diǎn)v，然后由v出發(fā)，訪問(wèn)與v鄰接且未被訪問(wèn)的任一頂點(diǎn)w1，再訪問(wèn)與w1鄰接且未被訪問(wèn)的任一頂點(diǎn)w2，……重復(fù)上述過(guò)程。當(dāng)不能再繼續(xù)向下訪問(wèn)時(shí)，依次退回到最近被訪問(wèn)的頂點(diǎn)，若它還有鄰接頂點(diǎn)未被訪問(wèn)過(guò)，則從該點(diǎn)開(kāi)始繼續(xù)上述搜索過(guò)程，直到圖中所有頂點(diǎn)均被訪問(wèn)過(guò)為止ABCDEABECDDFSvoidDFS(GraphG,intv){ArcNode*p;//工作指針p visit(v); //訪問(wèn)頂點(diǎn)v(一般是打印，即printf) visited[v]=TRUE; //修改訪問(wèn)標(biāo)記

p=G->adjlist[v].firstarc;//指針p開(kāi)始指向該頂點(diǎn)的第一條邊

while(p!=NULL){//沒(méi)遍歷完頂點(diǎn)的所有鄰接頂點(diǎn)

if(!visited[p->adjvex]){//如果該頂點(diǎn)沒(méi)被訪問(wèn)

DFS(G,p->adjvex);//遞歸訪問(wèn)該頂點(diǎn)}p=p->nextarc;//看還有沒(méi)有其他未訪問(wèn)的頂點(diǎn)}voidDFSTraverse(GraphG){

inti;//單獨(dú)定義是為了方便多個(gè)循環(huán)中使用

for(i=0;i<G->vexnum;i++）visited[i]=false;//將標(biāo)志數(shù)組初始化(全局?jǐn)?shù)組)for(i=0;i<G->vexnum;i++){if(!visited[i])DFS(G,i);//對(duì)所有}#defineMaxSize100;boolvisited[MaxSize]；DFS#defineMaxSize100;boolvisited[MaxSize]；voidDFS(GraphG,intv){ArcNode*p; visit(v); visited[v]=TRUE;

p=G->adjlist[v].firstarc;

while(p!=NULL){

if(!visited[p->adjvex]){

DFS(G,p->adjvex);}p=p->nextarc;}}ABCDE頂點(diǎn)訪問(wèn)序列：AABCD訪問(wèn)標(biāo)記數(shù)組是否訪問(wèn)falsefalsefalsefalse頂點(diǎn)truetruetruetrueEfalsetruedataABCD0123firstedge123^02013^02^4E^14^下標(biāo)pBCDEDFSvoidDFS(GraphG,intv){ArcNode*p;//工作指針p visit(v); //訪問(wèn)頂點(diǎn)v(一般是遍歷，即printf) visited[v]=TRUE; //修改訪問(wèn)標(biāo)記

p=G->adjlist[v].firstarc;//指針p開(kāi)始指向該頂點(diǎn)的第一條邊

while(p!=NULL){//沒(méi)遍歷完頂點(diǎn)的所有鄰接頂點(diǎn)

if(!visited[p->adjvex]){//如果該頂點(diǎn)沒(méi)被訪問(wèn)

DFS(G,p->adjvex);//遞歸訪問(wèn)該頂點(diǎn)}p=p->nextarc;//看還有沒(méi)有其他未訪問(wèn)的頂點(diǎn)}空間復(fù)雜度：由于DFS是一個(gè)遞歸算法，遞歸是需要一個(gè)工作棧來(lái)輔助工作，最多需要圖中所有頂點(diǎn)進(jìn)棧，所以時(shí)間復(fù)雜度為O(|V|)時(shí)間復(fù)雜度：1)鄰接表：遍歷過(guò)程的主要操作是對(duì)頂點(diǎn)遍歷它的鄰接點(diǎn)，由于通過(guò)訪問(wèn)邊表來(lái)查找鄰接點(diǎn)，所以時(shí)間復(fù)雜度為O(|E|),訪問(wèn)頂點(diǎn)時(shí)間為O(|V|),所以總的時(shí)間復(fù)雜度為O(|V|+|E|)2)鄰接矩陣：查找每個(gè)頂點(diǎn)的鄰接點(diǎn)時(shí)間復(fù)雜度為O(|V|),對(duì)每個(gè)頂點(diǎn)都進(jìn)行查找，所以總的時(shí)間復(fù)雜度為O(|V|2)深度優(yōu)先生成樹(shù)ABCDEABECD如果是一個(gè)非連通圖，則是深度優(yōu)先森林ABCDEABEDC深度優(yōu)先生成樹(shù)深度優(yōu)先森林本節(jié)內(nèi)容圖的應(yīng)用(1)最小生成樹(shù)最小生成樹(shù)我們之前講過(guò)連通圖的生成樹(shù)，它是一個(gè)極小的連通子圖。它包含圖中全部的頂點(diǎn)，但只有足以構(gòu)成一棵樹(shù)的n-1條邊。ABCDEF生成樹(shù)不唯一6個(gè)頂點(diǎn)，7條邊最小生成樹(shù)ABCDEFG51122015841831224A鎮(zhèn)51122015841831224B鎮(zhèn)C鎮(zhèn)D鎮(zhèn)E鎮(zhèn)F鎮(zhèn)G鎮(zhèn)選擇總權(quán)值最小的修路成本自然最小普利姆算法普利姆(Prim)算法:①?gòu)膱D中找第一個(gè)起始頂點(diǎn)v0，作為生成樹(shù)的第一個(gè)頂點(diǎn)，然后從這個(gè)頂點(diǎn)到其他頂點(diǎn)的所有邊中選一條權(quán)值最小的邊。然后把這條邊的另一個(gè)頂點(diǎn)v和這條邊加入到生成樹(shù)中。②對(duì)剩下的其他所有頂點(diǎn)，分別檢查這些頂點(diǎn)與頂點(diǎn)v的權(quán)值是否比這些頂點(diǎn)在lowcost數(shù)組中對(duì)應(yīng)的權(quán)值小，如果更小，則用較小的權(quán)值更新lowcost數(shù)組。③從更新后的lowcost數(shù)組中繼續(xù)挑選權(quán)值最小而且不在生成樹(shù)中的邊，然后加入到生成樹(shù)。④反復(fù)執(zhí)行②③直到所有所有頂點(diǎn)都加入到生成樹(shù)中。需要維護(hù)兩個(gè)數(shù)組：lowcost[n]adjvex[n]（n是圖中的頂點(diǎn)數(shù)）普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹(shù)到剩余頂點(diǎn)的最小權(quán)值

lowcost[0]=0;//將0號(hào)頂點(diǎn)(以0號(hào)頂點(diǎn)作為第一個(gè)頂點(diǎn))加入生成樹(shù)adjvex[0]=0;//由于剛開(kāi)始生成樹(shù)只有一個(gè)頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

Lowcost[i]=0表示i號(hào)頂點(diǎn)在生成樹(shù)中下標(biāo)0123456lowcost0511∞∞∞∞adjvex0000000初始化初始化普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹(shù)到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號(hào)頂點(diǎn)(以0號(hào)頂點(diǎn)作為第一個(gè)頂點(diǎn))加入生成樹(shù)adjvex[0]=0;//由于剛開(kāi)始生成樹(shù)只有一個(gè)頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因?yàn)橐易钚≈担环料仍O(shè)取一個(gè)最大的值來(lái)比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號(hào)頂點(diǎn)開(kāi)始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹(shù)中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個(gè)頂點(diǎn)}printf(“(%d->%d)”,adjvex[k],k);//打印權(quán)值最小的邊lowcost[k]=0;//將這個(gè)頂點(diǎn)加入生成樹(shù)//生成樹(shù)加入了新的頂點(diǎn)從下標(biāo)為1的頂點(diǎn)開(kāi)始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){

//如果新加入樹(shù)的頂點(diǎn)k使得權(quán)值變小lowcost[j]=G.arc[k][j];//更新更小的權(quán)值

adjvex[j]=k;//修改這條邊鄰接的頂點(diǎn)也就是表示這條邊是

從選出的頂點(diǎn)k指過(guò)來(lái)的方便打印}}}}Lowcost[i]=0表示i號(hào)頂點(diǎn)在生成樹(shù)中下標(biāo)0123456lowcost0511∞∞∞∞adjvex0000000找頂點(diǎn)更新數(shù)組i=1普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹(shù)到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號(hào)頂點(diǎn)(以0號(hào)頂點(diǎn)作為第一個(gè)頂點(diǎn))加入生成樹(shù)adjvex[0]=0;//由于剛開(kāi)始生成樹(shù)只有一個(gè)頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因?yàn)橐易钚≈?，不妨先設(shè)取一個(gè)最大的值來(lái)比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號(hào)頂點(diǎn)開(kāi)始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹(shù)中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個(gè)頂點(diǎn)}printf(“(%d->%d)”,adjvex[k],k);//打印權(quán)值最小的邊lowcost[k]=0;//將這個(gè)頂點(diǎn)加入生成樹(shù)//生成樹(shù)加入了新的頂點(diǎn)從下標(biāo)為1的頂點(diǎn)開(kāi)始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){

//如果新加入樹(shù)的頂點(diǎn)k使得權(quán)值變小lowcost[j]=G.arc[k][j];//更新更小的權(quán)值

adjvex[j]=k;//修改這條邊鄰接的頂點(diǎn)也就是表示這條邊是

從選出的頂點(diǎn)k指過(guò)來(lái)的方便打印}}}}Lowcost[i]=0表示i號(hào)頂點(diǎn)在生成樹(shù)中下標(biāo)0123456lowcost0011∞∞∞∞adjvex0000000找頂點(diǎn)打?。?->1）更新數(shù)組i=1普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹(shù)到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號(hào)頂點(diǎn)(以0號(hào)頂點(diǎn)作為第一個(gè)頂點(diǎn))加入生成樹(shù)adjvex[0]=0;//由于剛開(kāi)始生成樹(shù)只有一個(gè)頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因?yàn)橐易钚≈?，不妨先設(shè)取一個(gè)最大的值來(lái)比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號(hào)頂點(diǎn)開(kāi)始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹(shù)中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個(gè)頂點(diǎn)}printf(“(%d->%d)”,adjvex[k],k);//打印權(quán)值最小的邊lowcost[k]=0;//將這個(gè)頂點(diǎn)加入生成樹(shù)//生成樹(shù)加入了新的頂點(diǎn)從下標(biāo)為1的頂點(diǎn)開(kāi)始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){

//如果新加入樹(shù)的頂點(diǎn)k使得權(quán)值變小lowcost[j]=G.arc[k][j];//更新更小的權(quán)值

adjvex[j]=k;//修改這條邊鄰接的頂點(diǎn)也就是表示這條邊是

從選出的頂點(diǎn)k指過(guò)來(lái)的方便打印}}}}Lowcost[i]=0表示i號(hào)頂點(diǎn)在生成樹(shù)中下標(biāo)0123456lowcost00111228∞adjvex0001110找頂點(diǎn)更新數(shù)組i=1普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹(shù)到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號(hào)頂點(diǎn)(以0號(hào)頂點(diǎn)作為第一個(gè)頂點(diǎn))加入生成樹(shù)adjvex[0]=0;//由于剛開(kāi)始生成樹(shù)只有一個(gè)頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因?yàn)橐易钚≈担环料仍O(shè)取一個(gè)最大的值來(lái)比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號(hào)頂點(diǎn)開(kāi)始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹(shù)中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個(gè)頂點(diǎn)}printf(“(%d->%d)”,adjvex[k],k);//打印權(quán)值最小的邊lowcost[k]=0;//將這個(gè)頂點(diǎn)加入生成樹(shù)//生成樹(shù)加入了新的頂點(diǎn)從下標(biāo)為1的頂點(diǎn)開(kāi)始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){

//如果新加入樹(shù)的頂點(diǎn)k使得權(quán)值變小lowcost[j]=G.arc[k][j];//更新更小的權(quán)值

adjvex[j]=k;//修改這條邊鄰接的頂點(diǎn)也就是表示這條邊是

從選出的頂點(diǎn)k指過(guò)來(lái)的方便打印}}}}Lowcost[i]=0表示i號(hào)頂點(diǎn)在生成樹(shù)中下標(biāo)0123456lowcost00111228∞adjvex0001110找頂點(diǎn)更新數(shù)組i=2普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹(shù)到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號(hào)頂點(diǎn)(以0號(hào)頂點(diǎn)作為第一個(gè)頂點(diǎn))加入生成樹(shù)adjvex[0]=0;//由于剛開(kāi)始生成樹(shù)只有一個(gè)頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因?yàn)橐易钚≈担环料仍O(shè)取一個(gè)最大的值來(lái)比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號(hào)頂點(diǎn)開(kāi)始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹(shù)中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個(gè)頂點(diǎn)}printf(“(%d->%d)”,adjvex[k],k);//打印權(quán)值最小的邊lowcost[k]=0;//將這個(gè)頂點(diǎn)加入生成樹(shù)//生成樹(shù)加入了新的頂點(diǎn)從下標(biāo)為1的頂點(diǎn)開(kāi)始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){

//如果新加入樹(shù)的頂點(diǎn)k使得權(quán)值變小lowcost[j]=G.arc[k][j];//更新更小的權(quán)值

adjvex[j]=k;//修改這條邊鄰接的頂點(diǎn)也就是表示這條邊是

從選出的頂點(diǎn)k指過(guò)來(lái)的方便打印}}}}Lowcost[i]=0表示i號(hào)頂點(diǎn)在生成樹(shù)中下標(biāo)0123456lowcost00111208∞adjvex0001110找頂點(diǎn)更新數(shù)組打?。?->4）i=2普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹(shù)到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號(hào)頂點(diǎn)(以0號(hào)頂點(diǎn)作為第一個(gè)頂點(diǎn))加入生成樹(shù)adjvex[0]=0;//由于剛開(kāi)始生成樹(shù)只有一個(gè)頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因?yàn)橐易钚≈?，不妨先設(shè)取一個(gè)最大的值來(lái)比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號(hào)頂點(diǎn)開(kāi)始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹(shù)中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個(gè)頂點(diǎn)}printf(“(%d->%d)”,adjvex[k],k);//打印權(quán)值最小的邊lowcost[k]=0;//將這個(gè)頂點(diǎn)加入生成樹(shù)//生成樹(shù)加入了新的頂點(diǎn)從下標(biāo)為1的頂點(diǎn)開(kāi)始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){

//如果新加入樹(shù)的頂點(diǎn)k使得權(quán)值變小lowcost[j]=G.arc[k][j];//更新更小的權(quán)值

adjvex[j]=k;//修改這條邊鄰接的頂點(diǎn)也就是表示這條邊是

從選出的頂點(diǎn)k指過(guò)來(lái)的方便打印}}}}Lowcost[i]=0表示i號(hào)頂點(diǎn)在生成樹(shù)中下標(biāo)0123456lowcost0011120415adjvex0001144找頂點(diǎn)更新數(shù)組i=2普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹(shù)到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號(hào)頂點(diǎn)(以0號(hào)頂點(diǎn)作為第一個(gè)頂點(diǎn))加入生成樹(shù)adjvex[0]=0;//由于剛開(kāi)始生成樹(shù)只有一個(gè)頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因?yàn)橐易钚≈?，不妨先設(shè)取一個(gè)最大的值來(lái)比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號(hào)頂點(diǎn)開(kāi)始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹(shù)中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個(gè)頂點(diǎn)}