數(shù)據(jù)結(jié)構(gòu)第七章 圖

數(shù)據(jù)結(jié)構(gòu)第七章圖第1頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

圖是由一個(gè)頂點(diǎn)集V和一個(gè)弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。Graph=(V,R)其中，VR＝{<v,w>|v,w∈V且P(v,w)}

<v,w>表示從v到w的一條弧，并稱v為弧頭，w為弧尾。

謂詞P(v,w)定義了弧<v,w>的意義或信息。7.1圖的定義和術(shù)語(yǔ)第2頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

由于“弧”是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖。

ABECD例如:G1=(V1,VR1)其中V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}第3頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月若<v,w>VR

必有<w,v>VR,則稱(v,w)為頂點(diǎn)v和頂點(diǎn)w之間存在一條邊。

BCADFE由頂點(diǎn)集和邊集構(gòu)成的圖稱作無(wú)向圖。例如:G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={<A,B>,<A,E>,<B,E>,<C,D>,<D,F>,<B,F>,<C,F>}第4頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月名詞和術(shù)語(yǔ)網(wǎng)、子圖

完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑、簡(jiǎn)單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹(shù)、生成森林第5頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月ABECFAEFBBC設(shè)圖G=(V,{VR})和圖

G=(V,{VR}),且

VV,VRVR,則稱

G為G的子圖。1597211132

弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無(wú)向網(wǎng)。第6頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月假設(shè)圖中有

n

個(gè)頂點(diǎn)，e

條邊，則

含有e=n(n-1)/2條邊的無(wú)向圖稱作完全圖；

含有e=n(n-1)條弧的有向圖稱作

有向完全圖；若邊或弧的個(gè)數(shù)e<nlogn，則稱作稀疏圖，否則稱作稠密圖。第7頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

假若頂點(diǎn)v和頂點(diǎn)w之間存在一條邊，則稱頂點(diǎn)v

和w

互為鄰接點(diǎn)，ACDFE例如:ID(B)=3ID(A)=2邊(v,w)

和頂點(diǎn)v和w

相關(guān)聯(lián)。

和頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目定義為邊的度。B第8頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月頂點(diǎn)的出度:以頂點(diǎn)v為弧尾的弧的數(shù)目；ABECF對(duì)有向圖來(lái)說(shuō)，頂點(diǎn)的入度:以頂點(diǎn)v為弧頭的弧的數(shù)目。頂點(diǎn)的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3第9頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月設(shè)圖G=(V,{VR})中的一個(gè)頂點(diǎn)序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,則稱從頂點(diǎn)u到頂點(diǎn)w之間存在一條路徑。路徑上邊的數(shù)目稱作路徑長(zhǎng)度。ABECF如:長(zhǎng)度為3的路徑{A,B,C,F}簡(jiǎn)單路徑:序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡(jiǎn)單回路:序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。第10頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月若圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖；若無(wú)向圖為非連通圖，則圖中各個(gè)極大連通子圖稱作此圖的連通分量。BACDFEBACDFE第11頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。ABECFABECF對(duì)有向圖，否則，其各個(gè)強(qiáng)連通子圖稱作它的強(qiáng)連通分量。第12頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

假設(shè)一個(gè)連通圖有n個(gè)頂點(diǎn)和e條邊，其中n-1條邊和n個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹(shù)。對(duì)非連通圖，則稱由各個(gè)連通分量的生成樹(shù)的集合為此非連通圖的生成森林。BACDFE第13頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月結(jié)構(gòu)的建立和銷毀插入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)頂點(diǎn)的訪問(wèn)操作遍歷插入和刪除弧基本操作第14頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月CreatGraph(&G,V,VR)://按定義(V,VR)構(gòu)造圖DestroyGraph(&G)://銷毀圖結(jié)構(gòu)的建立和銷毀第15頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月對(duì)頂點(diǎn)的訪問(wèn)操作LocateVex(G,u);

//若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在

//圖中“位置”

；否則返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//對(duì)v賦值value。第16頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月對(duì)鄰接點(diǎn)的操作FirstAdjVex(G,v);

//返回v的“第一個(gè)鄰接點(diǎn)”。若該頂點(diǎn)//在G中沒(méi)有鄰接點(diǎn)，則返回“空”。NextAdjVex(G,v,w);

//返回v的（相對(duì)于w的）“下一個(gè)鄰接//點(diǎn)”。若w是v的最后一個(gè)鄰接點(diǎn)，則//返回“空”。第17頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月插入或刪除頂點(diǎn)InsertVex(&G,v);

//在圖G中增添新頂點(diǎn)v。DeleteVex(&G,v);//刪除G中頂點(diǎn)v及其相關(guān)的弧。第18頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月插入和刪除弧InsertArc(&G,v,w);//在G中增添弧<v,w>，若G是無(wú)向的，

//則還增添對(duì)稱弧<w,v>。DeleteArc(&G,v,w);

//在G中刪除弧<v,w>，若G是無(wú)向的，

//則還刪除對(duì)稱弧<w,v>。第19頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月遍歷DFSTraverse(G,v,Visit());//從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對(duì)每//個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit());

//從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對(duì)每//個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。第20頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月7.2圖的存儲(chǔ)表示一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示二、圖的鄰接表存儲(chǔ)表示三、有向圖的十字鏈表存儲(chǔ)表示四、無(wú)向圖的鄰接多重表存儲(chǔ)表示第21頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月Aij={0(i,j)VR1(i,j)VR一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示BACDFE定義:矩陣的元素為第22頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月有向圖的鄰接矩陣為非對(duì)稱矩陣ABECF第23頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

typedefstructArcCell{//弧的定義

VRTypeadj;//VRType是頂點(diǎn)關(guān)系類型。

//對(duì)無(wú)權(quán)圖，用1或0表示相鄰否；

//對(duì)帶權(quán)圖，則為權(quán)值類型。

InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];第24頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月typedefstruct{//圖的定義

VertexType//頂點(diǎn)信息

vexs[MAX_VERTEX_NUM];AdjMatrixarcs;//弧的信息

intvexnum,arcnum;//頂點(diǎn)數(shù)，弧數(shù)

GraphKindkind;//圖的種類標(biāo)志

}MGraph;第25頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月0A141B0452C353D254E015F123BACDFE二、圖的鄰接表存儲(chǔ)表示第26頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月142301201234

ABCDE有向圖的鄰接表ABECF可見(jiàn)，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。第27頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月ABECD有向圖的逆鄰接表ABCDE30342001234在有向圖的鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。第28頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月typedefstructArcNode{

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

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

InfoType*info;//該弧相關(guān)信息的指針}ArcNode;adjvexnextarcinfo弧的結(jié)點(diǎn)結(jié)構(gòu)第29頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月typedefstructVNode{

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

ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧

}VNode,AdjList[MAX_VERTEX_NUM];

datafirstarc頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)第30頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月typedefstruct{

AdjListvertices;

intvexnum,arcnum;

intkind;//圖的種類標(biāo)志

}ALGraph;圖的結(jié)構(gòu)定義第31頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月三、有向圖的十字鏈表存儲(chǔ)表示

弧的結(jié)點(diǎn)結(jié)構(gòu)弧尾頂點(diǎn)位置弧頭頂點(diǎn)位置弧的相關(guān)信息指向下一個(gè)有相同弧尾的結(jié)點(diǎn)指向下一個(gè)有相同弧頭的結(jié)點(diǎn)typedefstructArcBox{//弧的結(jié)構(gòu)表示

inttailvex,headvex;InfoType*info;structArcBox*hlink,*tlink;

}VexNode;第32頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)信息數(shù)據(jù)指向該頂點(diǎn)的第一條入弧指向該頂點(diǎn)的第一條出弧typedefstructVexNode{//頂點(diǎn)的結(jié)構(gòu)表示

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;第33頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//頂點(diǎn)結(jié)點(diǎn)(表頭向量)

intvexnum,arcnum;//有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}OLGraph;有向圖的結(jié)構(gòu)表示(十字鏈表)第34頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月四、無(wú)向圖的鄰接多重表存儲(chǔ)表示typedefstructEbox{VisitIfmark;//訪問(wèn)標(biāo)記

intivex,jvex;//該邊依附的兩個(gè)頂點(diǎn)的位置

structEBox*ilink,*jlink;InfoType*info;//該邊信息指針}EBox;邊的結(jié)構(gòu)表示第35頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月typedefstruct{//鄰接多重表

VexBoxadjmulist[MAX_VERTEX_NUM];

intvexnum,edgenum;

}AMLGraph;頂點(diǎn)的結(jié)構(gòu)表示typedefstructVexBox{VertexTypedata;EBox*firstedge;//指向第一條依附該頂點(diǎn)的邊}VexBox;無(wú)向圖的結(jié)構(gòu)表示第36頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月7.3圖的遍歷

從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問(wèn)一次的過(guò)程。深度優(yōu)先搜索廣度優(yōu)先搜索遍歷應(yīng)用舉例第37頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

從圖中某個(gè)頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從V0的各個(gè)未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問(wèn)到。一、深度優(yōu)先搜索遍歷圖連通圖的深度優(yōu)先搜索遍歷第38頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月Vw1SG1SG2SG3W1、W2和W3

均為V的鄰接點(diǎn)，SG1、SG2和SG3分別為含頂點(diǎn)W1、W2和W3

的子圖。訪問(wèn)頂點(diǎn)V：for(W1、W2、W3)

若該鄰接點(diǎn)W未被訪問(wèn)，

則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。w2w3w2第39頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月從上頁(yè)的圖解可見(jiàn):1.從深度優(yōu)先搜索遍歷連通圖的過(guò)程類似于樹(shù)的先根遍歷；解決的辦法是：為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪問(wèn)標(biāo)志visited[w]”。2.如何判別V的鄰接點(diǎn)是否被訪問(wèn)？第40頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月voidDFS(GraphG,intv){//從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖Gvisited[v]=TRUE;VisitFunc(v);

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

if(!visited[w])DFS(G,w);

//對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w//遞歸調(diào)用DFS}//DFS第41頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月首先將圖中每個(gè)頂點(diǎn)的訪問(wèn)標(biāo)志設(shè)為FALSE,之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪問(wèn)，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。非連通圖的深度優(yōu)先搜索遍歷第42頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月voidDFSTraverse(GraphG,

Status(*Visit)(intv)){

//對(duì)圖G作深度優(yōu)先遍歷。

VisitFunc=Visit;

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//訪問(wèn)標(biāo)志數(shù)組初始化

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

if(!visited[v])DFS(G,v);//對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用DFS}第43頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月abchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg訪問(wèn)標(biāo)志:訪問(wèn)次序:例如:012345678第44頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月二、廣度優(yōu)先搜索遍歷圖Vw1w8w3w7w6w2w5w4對(duì)連通圖，從起始點(diǎn)V到其余各頂點(diǎn)必定存在路徑。其中，V->w1,V->w2,V->w8

的路徑長(zhǎng)度為1；V->w7,V->w3,V->w5

的路徑長(zhǎng)度為2；V->w6,V->w4

的路徑長(zhǎng)度為3。w1Vw2w7w6w3w8w5w4第45頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪問(wèn)此頂點(diǎn)之后依次訪問(wèn)V0的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問(wèn)的先后次序依次訪問(wèn)它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。第46頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

voidBFSTraverse(GraphG,

Status(*Visit)(intv)){

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//初始化訪問(wèn)標(biāo)志

InitQueue(Q);

//置空的輔助隊(duì)列Q

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

if(

!visited[v]){

//v尚未訪問(wèn)

}

}//BFSTraverse……第47頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月visited[u]=TRUE;Visit(u);//訪問(wèn)uEnQueue(Q,v);

//v入隊(duì)列while(!QueueEmpty(Q)){

DeQueue(Q,u);//隊(duì)頭元素出隊(duì)并置為ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))

if(!visited[w])

{

visited[w]=TRUE;Visit(w);EnQueue(Q,w);

//訪問(wèn)的頂點(diǎn)w入隊(duì)列

}//if}//while第48頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月三、遍歷應(yīng)用舉例1.求一條從頂點(diǎn)i到頂點(diǎn)s的簡(jiǎn)單路徑2.

求兩個(gè)頂點(diǎn)之間的一條路徑長(zhǎng)度最短的路徑第49頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月1.

求一條從頂點(diǎn)i到頂點(diǎn)s的簡(jiǎn)單路徑abchdekfg求從頂點(diǎn)b到頂點(diǎn)k的一條簡(jiǎn)單路徑。從頂點(diǎn)b

出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。例如:假設(shè)找到的第一個(gè)鄰接點(diǎn)是a，則得到的結(jié)點(diǎn)訪問(wèn)序列為:b

adhce

kfg。假設(shè)找到的第一個(gè)鄰接點(diǎn)是c，則得到的結(jié)點(diǎn)訪問(wèn)序列為:

b

chdae

kfg，第50頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月1.

從頂點(diǎn)i到頂點(diǎn)s,若存在路徑，則從頂點(diǎn)

i出發(fā)進(jìn)行深度優(yōu)先搜索，必能搜索到頂點(diǎn)s。2.

遍歷過(guò)程中搜索到的頂點(diǎn)不一定是路徑上的頂點(diǎn)。結(jié)論:3.

由它出發(fā)進(jìn)行的深度優(yōu)先遍歷已經(jīng)完成的頂點(diǎn)不是路徑上的頂點(diǎn)。第51頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月voidDFSearch(intv,ints,char*PATH){//從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G，

//求得一條從v到s的簡(jiǎn)單路徑，并記錄在PATH中

visited[v]=TRUE;//訪問(wèn)第v個(gè)頂點(diǎn)

Append(PATH,getVertex(v));

//第v個(gè)頂點(diǎn)加入路徑

for(w=FirstAdjVex(v);w!=0&&!found;

w=NextAdjVex(v))

if(w=s){found=TRUE;Append(PATH,w);}

else

if(!visited[w])DFSearch(w,s,PATH);if(!found)Delete(PATH);

//從路徑上刪除頂點(diǎn)v

}第52頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月2.

求兩個(gè)頂點(diǎn)之間的一條路徑長(zhǎng)度最短的路徑

若兩個(gè)頂點(diǎn)之間存在多條路徑，則其中必有一條路徑長(zhǎng)度最短的路徑。如何求得這條路徑?第53頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月abchdekfg因此，求路徑長(zhǎng)度最短的路徑可以基于廣度優(yōu)先搜索遍歷進(jìn)行，但需要修改鏈隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu)及其入隊(duì)列和出隊(duì)列的算法。深度優(yōu)先搜索訪問(wèn)頂點(diǎn)的次序取決于圖的存儲(chǔ)結(jié)構(gòu)，而廣度優(yōu)先搜索訪問(wèn)頂點(diǎn)的次序是按“路徑長(zhǎng)度”漸增的次序。第54頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月例如:求下圖中頂點(diǎn)3至頂點(diǎn)5的一條最短路徑。鏈隊(duì)列的狀態(tài)如下所示:

312475

Q.front

Q.rear321475689第55頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月1)將鏈隊(duì)列的結(jié)點(diǎn)改為“雙鏈”結(jié)點(diǎn)。即結(jié)點(diǎn)中包含next和priou兩個(gè)指針；2)修改入隊(duì)列的操作。插入新的隊(duì)尾結(jié)點(diǎn)時(shí)，令其priou域的指針指向剛剛出隊(duì)列的結(jié)點(diǎn)，即當(dāng)前的隊(duì)頭指針?biāo)附Y(jié)點(diǎn)；3)修改出隊(duì)列的操作。出隊(duì)列時(shí)，僅移動(dòng)隊(duì)頭指針，而不將隊(duì)頭結(jié)點(diǎn)從鏈表中刪除。第56頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月typedef

DuLinkListQueuePtr;

voidInitQueue(LinkQueue&Q){

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

Q.front->next=Q.rear->next=NULL}voidEnQueue(LinkQueue&Q,QelemTypee){p=(QueuePtr)malloc(sizeof(QNode));p->data=e;p->next=NULL;

p->priou=Q.front

Q.rear->next=p;Q.rear=p;}voidDeQueue(LinkQueue&Q,QelemType&e){

Q.front=Q.front->next;e=Q.front->data}第57頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月7.4(連通網(wǎng)的)最小生成樹(shù)

假設(shè)要在n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？問(wèn)題：第58頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月構(gòu)造網(wǎng)的一棵最小生成樹(shù)，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）該問(wèn)題等價(jià)于：算法一：（普里姆算法）第59頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

取圖中任意一個(gè)頂點(diǎn)v作為生成樹(shù)的根，之后往生成樹(shù)上添加新的頂點(diǎn)w。在添加的頂點(diǎn)w和已經(jīng)在生成樹(shù)上的頂點(diǎn)v之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)v和w之間的邊中取值最小。之后繼續(xù)往生成樹(shù)上添加頂點(diǎn)，直至生成樹(shù)上含有n-1個(gè)頂點(diǎn)為止。普里姆算法的基本思想:第60頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月abcdegf例如:195141827168213ae12dcbgf7148531621所得生成樹(shù)權(quán)值和=14+8+3+5+16+21=67第61頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月在生成樹(shù)的構(gòu)造過(guò)程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹(shù)上的頂點(diǎn)集U

和尚未落在生成樹(shù)上的頂點(diǎn)集V-U

，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。

一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件:第62頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月設(shè)置一個(gè)輔助數(shù)組，對(duì)當(dāng)前V－U集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)相連接的代價(jià)最小的邊：struct{VertexTypeadjvex;//U集中的頂點(diǎn)序號(hào)

VRTypelowcost;//邊的權(quán)值}closedge[MAX_VERTEX_NUM];第63頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd7213c55第64頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月voidMiniSpanTree_P(MGraphG,VertexTypeu){//用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)

k=LocateVex(G,u);

for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化

if(j!=k)

closedge[j]={u,G.arcs[k][j].adj};

closedge[k].lowcost=0;//初始，U＝{u}

for(i=0;i<G.vexnum;++i){}繼續(xù)向生成樹(shù)上添加頂點(diǎn);第65頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

k=minimum(closedge);

//求出加入生成樹(shù)的下一個(gè)頂點(diǎn)(k)

printf(closedge[k].adjvex,G.vexs[k]);//輸出生成樹(shù)上一條邊

closedge[k].lowcost=0;//第k頂點(diǎn)并入U(xiǎn)集

for(j=0;j<G.vexnum;++j)//修改其它頂點(diǎn)的最小邊

if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};

第66頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月具體做法:先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開(kāi)始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止?？紤]問(wèn)題的出發(fā)點(diǎn):為使生成樹(shù)上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹(shù)中每一條邊的權(quán)值盡可能地小。克魯斯卡爾算法的基本思想：第67頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月abcdegf195141827168213ae12dcbgf7148531621例如:7121819第68頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月算法描述:構(gòu)造非連通圖ST=(V,{});k=i=0;//k計(jì)選中的邊數(shù)

while(k<n-1){++i;

檢查邊集E中第i條權(quán)值最小的邊(u,v);

若(u,v)加入ST后不使ST中產(chǎn)生回路，

則輸出邊(u,v);

且k++;}第69頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍比較兩種算法第70頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月7.7關(guān)鍵路徑問(wèn)題:

假設(shè)以有向網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時(shí)間。問(wèn)：哪些子工程項(xiàng)是“關(guān)鍵工程”？即：哪些子工程項(xiàng)將影響整個(gè)工程的完成期限的。第71頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月abcdefghk64521187244例如:“關(guān)鍵活動(dòng)”指的是：該弧上的權(quán)值增加

將使有向圖上的最長(zhǎng)路徑的長(zhǎng)度增加。整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑。源點(diǎn)匯點(diǎn)6174第72頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

如何求關(guān)鍵活動(dòng)？“事件(頂點(diǎn))”的最早發(fā)生時(shí)間ve(j)ve(j)=從源點(diǎn)到頂點(diǎn)j的最長(zhǎng)路徑長(zhǎng)度；“事件(頂點(diǎn))”的最遲發(fā)生時(shí)間vl(k)vl(k)=從頂點(diǎn)k到匯點(diǎn)的最短路徑長(zhǎng)度。第73頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

假設(shè)第i條弧為<j,k>

則對(duì)第i項(xiàng)活動(dòng)言“活動(dòng)(弧)”的最早開(kāi)始時(shí)間ee(i)ee(i)=ve(j)；“活動(dòng)(弧)”的最遲開(kāi)始時(shí)間el(i)el(i)=vl(k)–dut(<j,k>)；第74頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

事件發(fā)生時(shí)間的計(jì)算公式：

ve(源點(diǎn))=0；

ve(k)=Max{ve(j)+dut(<j,k>)}vl(匯點(diǎn))=ve(匯點(diǎn))；

vl(j)=Min{vl(k)–dut(<j,k>)}第75頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓?fù)溆行蛐蛄?a-d-f-c-b-e-h-g-k第76頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月0645771514181814161078660000645777151414160236688710第77頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

算法的實(shí)現(xiàn)要點(diǎn):顯然，求ve的順序應(yīng)該是按拓?fù)溆行虻拇涡颍?/p>

而求vl的順序應(yīng)該是按拓?fù)淠嫘虻拇涡?；因?yàn)橥負(fù)淠嫘蛐蛄屑礊橥負(fù)溆行蛐蛄械哪嫘蛄校虼藨?yīng)該在拓?fù)渑判虻倪^(guò)程中，另設(shè)一個(gè)“?！庇浵峦?fù)溆行蛐蛄小５?8頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

1.熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解實(shí)際問(wèn)題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系。

2.熟練掌握?qǐng)D的兩種搜索路徑的遍歷：遍歷的邏輯定義、深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。在學(xué)習(xí)中應(yīng)注意圖的遍歷算法與樹(shù)的遍歷算法之間的類似和差異。第79頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月

3.應(yīng)用圖的遍歷算法求解各種簡(jiǎn)單路徑問(wèn)題。

4.理解教科書中討論的各種圖的算法。第80頁(yè)，課件共88頁(yè)，創(chuàng)作于2023年2月作業(yè)一、選擇題1、鄰接表是圖的一種__________________。A）順序存儲(chǔ)結(jié)構(gòu)B）鏈接存儲(chǔ)結(jié)構(gòu)C）索引存儲(chǔ)結(jié)構(gòu)D）散列存儲(chǔ)結(jié)構(gòu)2、帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中_________________。A）第i行非∞的元素之和B）第