數(shù)據(jù)結(jié)構(gòu)與算法-圖

教學(xué)要求了解圖的定義及相關(guān)的術(shù)語，掌握圖的邏輯結(jié)構(gòu)及其特點(diǎn)；了解圖的存儲方法，重點(diǎn)掌握圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)；掌握圖的遍歷方法，重點(diǎn)掌握圖的兩種遍歷算法的實(shí)現(xiàn)；了解圖型結(jié)構(gòu)的應(yīng)用，關(guān)節(jié)點(diǎn)與雙連通性求解算法、強(qiáng)連通性判定與強(qiáng)連通分支求解算法，重點(diǎn)掌握最小生成樹算法、最短路徑算法、拓?fù)渑判蚝完P(guān)鍵路徑算法的基本思想、算法原理和實(shí)現(xiàn)過程?！締栴}3】有一個(gè)長方形的房間，鋪設(shè)了紅色或黑色的方型瓷磚。一名男子站在一個(gè)黑色的瓷磚上，從一個(gè)瓷磚，他可以轉(zhuǎn)移到四個(gè)相鄰瓷磚，他只能移動(dòng)在黑瓷磚上，不能站在紅瓷磚上，通過走過的黑瓷磚計(jì)算黑瓷磚的片數(shù)。

【問題4】計(jì)算國際象棋中騎士從一個(gè)指定的位置到達(dá)目的位置的最少步數(shù)。因?yàn)槊恳淮味加?種走法，要把可行的走法記錄下來，直到走到終點(diǎn)為止。輸出最少的步數(shù)?！締栴}2】給一堆格式為A

<

B

的關(guān)系式，判斷有沒有一個(gè)可以排列的順序。當(dāng)一個(gè)升序序列確定時(shí)，輸出處理到第幾個(gè)關(guān)系式和排好序的升序序列；當(dāng)不確定時(shí)，輸出也不確定；當(dāng)矛盾時(shí)，輸出發(fā)現(xiàn)矛盾時(shí)處理到第幾個(gè)關(guān)系。先提幾個(gè)問題：？【問題1】由于大道路網(wǎng)的維護(hù)成本高，需選擇停止維護(hù)一些道路，但要保證所有村莊之間都有路到達(dá)，即使路線并不如以前短，但要使得總的維護(hù)費(fèi)用最少。哥尼斯堡是東普魯士的首都，今俄羅斯加里寧格勒市，普萊格爾河橫貫其中。十八世紀(jì)在這條河上建有七座橋，將河中間的兩個(gè)島和河岸聯(lián)結(jié)起來。人們閑暇時(shí)經(jīng)常在這上邊散步，有人提出：能不能每座橋都只走一遍，最后又回到原來的位置？——哥尼斯堡城七橋問題1736年，大數(shù)學(xué)家歐拉首先把這個(gè)問題簡化，他把兩座小島和河的兩岸分別看作四個(gè)點(diǎn)，而把七座橋看作這四個(gè)點(diǎn)之間的連線，A、B、C，D表示陸地，形成了著名的——?dú)W拉圖。一筆畫問題：（1）由偶點(diǎn)組成的連通圖，可以一筆畫成。任一偶點(diǎn)為起點(diǎn)，一定能以這個(gè)點(diǎn)為終點(diǎn)畫完此圖；（2）只有兩個(gè)奇點(diǎn)的連通圖（其余都為偶點(diǎn)），可以一筆畫成。把一個(gè)奇點(diǎn)為起點(diǎn)，另一個(gè)奇點(diǎn)為終點(diǎn)；（3）其他情況的圖都不能一筆畫出。(奇點(diǎn)數(shù)除以二便可算出此圖需幾筆畫成)。【問題5】【問題6】簡化的格尼斯堡城問題設(shè)在4地（A，B，C，D）之間架設(shè)有6座橋，要求從某一地出發(fā)，經(jīng)過每座橋恰巧一次，最后仍回到原地。（1）此問題有解的條件是什么？

（2）描述與求解此問題有關(guān)的數(shù)據(jù)結(jié)構(gòu)并編寫一個(gè)算法，找出滿足要求的一條回路。C主要內(nèi)容4.1基本術(shù)語4.7強(qiáng)聯(lián)通圖4.2圖的表示4.8拓?fù)浞诸?.3圖的搜索算法*4.9關(guān)鍵路徑4.4圖與樹的聯(lián)系4.10單源最短路徑4.5無向圖的雙連通性實(shí)驗(yàn)3有向網(wǎng)建立及最短路徑*4.6

有向圖的搜索*4.11每一對頂點(diǎn)間的最短路徑4.1基本定義/術(shù)語【定義】一個(gè)圖G=（V，E）是一個(gè)由非空的有限集V和一個(gè)邊集E所組成的。若E中的每條邊都是頂點(diǎn)的有序?qū)Γ╲,w），就說該圖是有向圖（DirectedGraph，Digraph）。若E中的每條邊是兩個(gè)不同頂點(diǎn)無序?qū)?，就說該圖是無向圖，其邊仍表示成（v,w）?！続DT】GraphG=(V,R)數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：

R={VR}VR={<v,w>|v,w∈V,且P(v,w),<v,w>表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息}ADT操作：NodeNewNode(G,v)；VoidDelNode(G,v)；VoidSetSucc(G,v1,v2)；VoidDelSucc(G,v1,v2)；ListOfNodeSucc(G,v)；ListOfNodePred(G,v)；IntIsEdge(G,v1,v2)；//P27NodeFirstAdjVex(G,v)；NodeNextAdjVex(G,v,w)；術(shù)語：頂點(diǎn)弧/邊鄰接/相鄰依附路徑（路）簡單路徑環(huán)路帶標(biāo)號的圖（網(wǎng)）

連通連通圖

強(qiáng)連通圖連通分量完全圖稀疏圖稠密圖子圖度入度出度生成樹V3V1V4V5V2G2V1V3V4V2G10110000000011000G1.arcs0101010101010111010001100G2.arcs126543545983516∞3∞∞∞1∞∞5∞3∞∞∞∞4∞∞98∞∞∞∞6∞∞5∞∞∞∞∞∞∞534.2圖的表示1、圖的順序存儲——鄰接矩陣設(shè)圖G=(V,E)，V={0，1，…，n-1}則表示G的鄰接矩陣A是其元素按下式定義的n×n矩陣:A[i][j]=1若（i,j）∈E0若（i,j）∈E網(wǎng)的鄰接矩陣可定義為：A[i][j]=wij

若（i,j）∈E∞

若（i,j）∈ETD(vi)=∑A[i][j]=∑A[i][j](n:頂點(diǎn)個(gè)數(shù)）j=0n-1i=0n-1TD(vi)=OD(vi)+ID(vi)=∑A[i][j]＋∑A[i][j](n:頂點(diǎn)個(gè)數(shù)）j=0n-1i=0n-1#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM

20Typedefenum{DG,DN,AG,AN}GraphKind;TypedefstructArcCell{VRTypeadj;InfoType*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{VertexTypevex[MAX_VERTEX_NUM];

AdjMatrixarcs;intvexnum,arcnum;

GraphKindkind;}Mgraph;【例4-1】圖類型變量：MGraphG;頂點(diǎn)個(gè)數(shù)：G.vexnum；弧/邊的個(gè)數(shù)：G.arcnum；圖的類型：G.kind=(DG,DN,AG,AN)；頂點(diǎn)i信息：G.vex[i]；頂點(diǎn)i和頂點(diǎn)j鄰接關(guān)系：G.arcs[i][j].adj；弧/邊附加信息：G.arcs[i][j].info->；圖的操作FirstAdjVex()和NextAdjVex()的實(shí)現(xiàn)存儲結(jié)構(gòu)：鄰接矩陣intFirstAdjVex(MGraphG,VertexTypev){//返回值為圖G中與頂點(diǎn)v鄰接的第一個(gè)鄰接點(diǎn)，0為沒有鄰接點(diǎn)VertexTypew=0;while((w<G.vexnum)&&!G.arcs[v][w].adj)w++;if((w<G.vexnum)&&G.arcs[v][w])return(w);elsereturn(0);}intNextAdjVex(MGraphG,VertexTypev,VertexTypew){//返回值為圖G中與頂點(diǎn)v鄰接的w之后的鄰接點(diǎn)，0為無下一個(gè)鄰接點(diǎn)w=v+1;while((w<G.vexnum)&&!G.arcs[v][w].adj)w++;if((w<G.vexnum)&&G.arcs[v][w])return(w);elsereturn(0);}v1

v2^v3

v4

2130^^^有向圖G2鄰接表0123v1

v2

v3

v4

3002^^^^G2的逆鄰接表0123無向圖G1鄰接表v5

v1

v2

v3

v4

314243202101^^^^^01234V3V1V4V5V2G1V1V3V4V2G2＋2、圖的鏈?zhǔn)酱鎯Α徑颖恚ˋdjacencyList）2、圖的鏈?zhǔn)酱鎯Γɡm(xù)）Adjvexnextarcinfo表結(jié)點(diǎn)datafirstarc頭結(jié)點(diǎn)#defineMAX_VERTEX_NUM20TypedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType*info;}ArcNode;TypedefstructVnode{VertexTypedata;ArcNode*firstarc;}Vnode,AdjList[MAX_VERTEX_NUM];Typedefstruct{AdjListvertices;Intvexnum;Intkind;}ALGraph;【例4-2】圖類型變量：ALGraphG;頂點(diǎn)個(gè)數(shù)：G.vexnum；圖的類型：G.kind=(DG,DN,AG,AN)；頂點(diǎn)i信息：G.vertices[i].dada；頂點(diǎn)i的第一個(gè)鄰接點(diǎn):G.vertices[i].firstarc->adjvex；G.vertices[G.vertices[i].firstarc->adjvex].data；G.vertices[i].firstarc->info；頂點(diǎn)i的第二個(gè)鄰接點(diǎn)：

G.vertices[i].firstarc->nextarc->adjvex；圖的操作FirstAdjVex()和NextAdjVex()的實(shí)現(xiàn)存儲結(jié)構(gòu)：鄰接表intFirstAdjVex(ALGraphG,VertexTypev){//返回值為圖G中與頂點(diǎn)v鄰接的第一個(gè)鄰接點(diǎn)，0為沒有鄰接點(diǎn)if(G.vertices[v].firstarc)return(G.vertices[v].firstarc->adjvex);elsereturn(0);}intNextAdjVex(ALGraphG,VertexTypev,VertexTypew){//返回值為圖G中與頂點(diǎn)v鄰接的w之后的鄰接點(diǎn)，0為無下一個(gè)鄰接點(diǎn)

ArcNode*p;p=G.vertices[v].firstarc;while(p!=NULL&&p->adjvex!=w)p=p->nextarc;if(p)return(0);else if(p->nextarc) return(p->nextarc->adjvex); elsereturn(0);}#defineMAX_VERTEX_NUM20 typedefstructArcBox{inttailvex,headvex; //該弧的尾和頭頂點(diǎn)的位置

structArcBox*hlink,*tlink;//分別為弧頭相同和弧尾相同的弧的鏈域

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

}ArcBox;typedefstructVexNode{VertexTypedata;

ArcBox*firstin,*firstout;//分別指向該頂點(diǎn)第一條入弧和出弧}VexNode;typedefstruct{

VexNodexlist[MAX_VERTEX_NUM]; //表頭向量int vexnum,arcnum;//有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}OLGraph;#defineMAX_VERTEX_NUM20typedefemnu{unvisited,visited}VisitIf;typedefstructEBox{VisitIfmark; //邊訪問標(biāo)記

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

structEBox*ilink,*jlink; //分別指向依附這兩個(gè)頂點(diǎn)的下一條邊

InfoType*info; //該邊信息指針}EBox;typedefstructVexBox{VertexTypedata;

EBox*firstedge; //指向第一條依附于該頂點(diǎn)的邊}VexBox;typedefstruct{

VexBoxadjmulist[MAX_VERTEX_NUM]; intvexnum,edgenum; //無向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)}AMLGraph;4.3圖的搜索算法深度優(yōu)先搜索DFS(Depth-FirstSearch)廣度優(yōu)先搜索BFS(Breadth-FirstSearch)圖的遍歷確定遍歷起點(diǎn)；為保證非連通圖的每一頂點(diǎn)都能被訪問到，應(yīng)輪換起點(diǎn)；為避免頂點(diǎn)的重復(fù)訪問，做訪問標(biāo)記。遍歷圖注意問題：1、深度優(yōu)先搜索DFS(Depth-FirstSearch)

首先訪問起點(diǎn)，然后依次訪問與該起點(diǎn)相關(guān)聯(lián)的每一個(gè)頂點(diǎn)，并以該關(guān)聯(lián)頂點(diǎn)為新的起點(diǎn)，繼續(xù)深度優(yōu)先遍歷。若圖中還有未被訪問的頂點(diǎn)，則換一個(gè)起點(diǎn)，繼續(xù)深度優(yōu)先遍歷，直到所有的頂點(diǎn)都被訪問。V1V2V3V4V5V6V7V8無向圖G3V1V2V3V4V5V6V7V8有向圖G4V1,V3,V6,V7,V2,V4,V8,V5V1,V2,V4,V8,V5,V3,V6,V7深度優(yōu)先遍歷：VoidDFSTravers(GRAPHG,v){For(v=0;v<G.vexnum;++v)visited[v]=FALSE;For(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);}VoidDFS(GRAPHG,intv){visited[v]=TRUE;visitfunc(v);for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w);if(!visited[w])DFS(G,w);}v13v2v3v4v544221^230^1^0101234^^無向圖G2鄰接表V3V1V4V5V2G2圖G2的深度優(yōu)先遍歷結(jié)果：V1,V4,V3,V5,V2{T=￠;/*樹邊集開始為空*/count=1;/*先深編號計(jì)數(shù)器*/for(allv∈V)while(thereexistsavertexv∈Vmarked“new”)dfs-search(v)}

voiddfs-search(v){dfn[v]=count;/*對v編號*/count=count+1;markv“old”/*訪問結(jié)點(diǎn)v*/for(eachvertexw∈L[v])if(wismarked“new”{add(v,w)toT;/*(v,w)是樹邊*/dfs-search(w);/*遞歸搜索*/}}輸入：L[v]表示無向圖G的關(guān)于v的鄰接表輸出：每個(gè)結(jié)點(diǎn)有先深編號的無向圖和樹邊集T2、廣度優(yōu)先搜索BFS(Breadth-FirstSearch)V1V2V3V4V5V6V7V8無向圖G3V1V2V3V4V5V6V7V8有向圖G4V1,V2,V3,V4,V5,V6,V7,V8V1,V2,V3,V4,V5,V6,V7,V8

首先訪問起點(diǎn)，依次訪問與該起點(diǎn)相關(guān)聯(lián)的每一個(gè)鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，若圖中還有未被訪問的頂點(diǎn)，則換一個(gè)起點(diǎn)，繼續(xù)廣度優(yōu)先遍歷,直到所有的頂點(diǎn)都被訪問。VoidBFSTravers(GRAPHG,v){For(v=0;v<G.vexnum;++v)visited[v]=FALSE;InitQueue(Q);For(v=0;v<G.vexnum;++v)if(!visited[v]){EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,u);for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)if(!visited[w]){visited[w]=TRUE;visit(w);EnQueue(Q,w);}}}}v13v2v3v4v54422123010101234^^無向圖G2鄰接表V3V1V4V5V2G2圖G2的廣度優(yōu)先遍歷結(jié)果：V1,V4,V2,V3,V5Voidbfs-search(v){MakeNull(Q);bfn[v]=count;/*先廣編號*/count=count+1;markv“old”EnQueue(v,Q);/*v入隊(duì)*/while(!Empty(Q)){v=Front(Q);DeQueue(Q);for(eachw∈L[v]){bfn[w]=count;/*先廣編號*/count=count+1;markw“old”;EnQueue(w,Q);Insert((v,w),T);}}/*樹邊入隊(duì)*/}輸入：L[v]表示無向圖G的關(guān)于v的鄰接表輸出：每個(gè)結(jié)點(diǎn)有先廣編號的無向圖和樹邊集T思考題:1、圖的路徑問題

(1)無向圖兩點(diǎn)之間是否有路徑存在？

(2)有向圖兩點(diǎn)之間是否有路徑存在?

(3)如果有路徑,路徑經(jīng)過哪些頂點(diǎn)？2、圖的環(huán)路問題

(1)無向圖是否存在環(huán)路？

(2)有向圖是否存在環(huán)路？

(3)有幾條環(huán)路？

(4)環(huán)路經(jīng)過哪些點(diǎn),環(huán)路軌跡是什么？參考算法1-1：判斷是否存在從u到v的路徑，返回1或0intExistPathDfs1(ALGraphG,int*visited,intu,intv){ArcNode*p;intw;if(u==v)return1;else{visited[u]=1;//訪問標(biāo)志for(p=G.vertices[u].firstarc;p;p=p->nextarc){w=p->adjvex;if(!visited[w]&&ExistPathDfs1(G,visited,w,v))return1;}//for}//elsereturn(0);}//ExistPathDfs1參考算法1-2：判斷u到v是否有通路,返回1或0intExistPathDfs2(ALGraphG,int*visited,intu,intv){ArcNode*p;intw;intstaticflag=0;visited[u]=1;//訪問標(biāo)志

p=G.vertices[u].firstarc;//第一個(gè)鄰接點(diǎn)

while(p!=NULL){w=p->adjvex;if(v==w){flag=1; return(1);}//u和v有通路

if(!visited[w])

ExistPathDfs2(G,visited,w,v);p=p->nextarc;}//whileif(!flag)return(0);}//ExistPathDfs2參考算法2：求u到v所有簡單路徑intFindAllPath(ALGraphG,int*visited,int*path,intu,intv,intk)

{ArcNode*p;intstaticpaths=0;//paths控制指輸出第幾條有效路徑

intn,i;path[k]=u;visited[u]=1;if(u==v){if(path[1]){if(!paths)printf("找到如下路徑：\n");paths++;printf("路徑%d：%d",paths,path[0]);for(i=1;path[i];i++)printf("--%d",path[i]);printf("\n");}}elsefor(p=G.vertices[u].firstarc;p;p=p->nextarc){n=p->adjvex;if(!visited[n])

FindAllPath(G,visited,path,n,v,k+1);} for(i=1;i<=G.vexnum;i++) {visited[i]=0; path[i]=0; }return(paths);}//path[0]為路徑起點(diǎn)，從path[1]開始為路徑中個(gè)頂點(diǎn)，若不存在路徑，則從path[1]起均為0調(diào)用：FindAllPath(G,visited,path,u,v,0))參考算法3：判斷圖是否有回路存在voidIsCycle(ALGraphG){intvisited[MAX_VERTEX_NUM],u,CycleFlag;for(u=1;u<=G.vexnum;u++)visited[u]=0;for(u=1;u<=G.vexnum;u++) if(!visited[u]) { CycleFlag=IsCycle(G,visited,u); if(CycleFlag)break; }if(CycleFlag) printf("圖中存在回路！\n");elseprintf("圖中不存在回路！\n");}4.4圖與樹的聯(lián)系4.4.1先深生成森林和先廣生成森林abdecfg(a)abdecfg(b)abdecfg(c)樹邊(編號從小到大)與非樹邊：回退邊/橫邊(編號從大到小)先深(廣)搜索過程中，由樹邊和樹邊所連接的頂點(diǎn)組成的子圖，稱為圖的先深(廣)生成森林。無向連通圖通過先深(廣)搜索只能得到一個(gè)先深(廣)生成樹。非連通圖則可得到多個(gè)生成樹，連通子圖（連通分量）。4.4.3最小生成樹4.4.2無向圖與開放樹【定義】連通而無環(huán)路的無向圖稱作開放樹（FreeTree）。開放樹的性質(zhì)：（1）具有n≥1個(gè)頂點(diǎn)的開放樹包含n-1條邊；（2）如果在開放樹中任意加上一條邊，便得到一條回路。(證明見教材P133～134)

設(shè)G=(V,E)是一個(gè)連通圖，E中每一條邊(u,v)的權(quán)為C(u,v)，也叫做邊長。圖G的一株生成樹(spanningtree)是連接V中所有結(jié)點(diǎn)的一株開放樹。將生成樹中所有邊長之總和稱為生成樹的價(jià)(cost)。使這個(gè)價(jià)最小的生成樹稱為圖G的最小生成樹(minimum-costspanningtree)。MST性質(zhì)【描述1】設(shè)G=(V,E)是一個(gè)連通圖，在E上定義一個(gè)權(quán)函數(shù)，且{(V1,T1),(V2,T2),…,(Vk,Tk)}是G的任意生成森林。令:T=∪Ti(k>1)ki=1

又設(shè)e=(v,w)是E-T中這樣一條邊，其權(quán)C[v,w]最小，而且v∈V1和w∈V1。則圖G有一棵包含T∪{e}的生成樹，其價(jià)不大于包含T的任何生成樹的價(jià)?！久枋?】假設(shè)N=(V,{E})是一個(gè)連通網(wǎng)，U是頂點(diǎn)V的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值（代價(jià)）的邊，其中u∈U,v∈V-U,則必存在一棵包含邊(u,v)的最小生成樹。UV－Uuvu’v’MST性質(zhì)證明假設(shè)網(wǎng)N的任何一棵最小生成樹都不包含(u,v)min，設(shè)T是連通網(wǎng)上的一棵最小生成樹，當(dāng)將邊(u,v)min加入到T中時(shí)，由生成樹的定義，T中必包含一條(u,v)min的回路。另一方面，由于T是生成樹，則在T上必存在另一條邊(u’,v’)，且u和u’、v和v’之間均有路徑相同。刪去邊(u’,v’)便可消去上述回路，同時(shí)得到另一棵最小生成樹T’。但因?yàn)?u,v)min的代價(jià)不高于(u’,v’)，則T’的代價(jià)亦不高于T，T’是包含(u，v)min的一棵最小生成樹。（a）V3V1V4V5V2V66515536462V3V1V4V5V2（c）V614V3V1V4V5V2（d）V6142V3V1V4V5V2（e）V61542V3V1V4V5V2（f）V615342求最小生成樹V3V1V4V5V2（b）V61UV-U【問題1】高速公路問題：假設(shè)有N個(gè)城市，每條公路可以連接兩個(gè)城市。目前原有的公路有m條，但是不能實(shí)現(xiàn)所有城市之間的連通，因此需要繼續(xù)修建公路，在費(fèi)用最低的原則下，實(shí)現(xiàn)N個(gè)城市的連通，還需要修建哪些條公路。由于修路的費(fèi)用與公路的長短是成正比的，所以這個(gè)問題就可以轉(zhuǎn)化成求修建哪幾條公路能夠?qū)崿F(xiàn)所有城市的連通，同時(shí)滿足所修公路總長最短?！締栴}2】在n個(gè)城市間建立通信網(wǎng)絡(luò)，需架設(shè)n-1條線路。求解如何以最低經(jīng)濟(jì)代價(jià)建設(shè)此通信網(wǎng)。

很多關(guān)于最小成本的問題都可以通過求帶權(quán)圖的最小生成樹來解決?！締栴}3】某市區(qū)有七個(gè)住宅小區(qū)需要鋪設(shè)天然氣管道,各小區(qū)的位置及它們之間可修建管道路線與費(fèi)用如圖所示?，F(xiàn)要設(shè)計(jì)一個(gè)管道鋪設(shè)路線,要求天然氣能輸送到各個(gè)小區(qū)并且修建的總費(fèi)用為最小,這就是求最小生成樹的問題。（1）求最小生成樹——Prim算法輸入：加權(quán)無向圖（無向網(wǎng)）G=(V,E)，其中v=(1,2,…,n).輸出：G的最小生成樹要點(diǎn)：引入集合U和T。U準(zhǔn)備結(jié)點(diǎn)集，T為樹邊集。

初值U={1}，T=￠。選擇有最小權(quán)的邊(u,v)，

使u∈U,v∈(V-U),將v加入U(xiǎn),（u,v）加入T。

重復(fù)這一過程，直到U=V。

voidPrim(G,T){T=￠;U={1};while((U–V)!=￠){設(shè)(u,v)是使u∈U與v∈(V-U)且權(quán)最小的邊；

T=T∪{(u,v)};U=U∪{v};}};引入輔助向量：

CloseST[]和LowCost，其中：CloseST[i]為U中的一個(gè)頂點(diǎn)邊(i,CloseST[i])具有最小的權(quán)LowCost[i]；集合如何實(shí)現(xiàn)？若頂點(diǎn)i∈U則LowCost[i]=INFINITY

否則LowCost[i]=0；CloseST和LowCost的初值是多少？開始調(diào)整LowCost,對非集合U中的頂點(diǎn)jLowCost[j]=min(C[k][j],LowCost[j])CloseST[j]=k;i++結(jié)束LowCost[i]為鄰接矩陣C的第一行值CloseST[i]的初值均為1從LowCost[i]中求值最小的頂點(diǎn)

k(k,CloseST[k])為求得的一條邊將頂點(diǎn)k加入到集合U定義：CloseST[i]為U中的一個(gè)頂點(diǎn)邊(i,CloseST[i])具有最小的權(quán)LowCost[i]Prim算法流程圖i=2i<=nYesNoVoidPrim(C)詳見P135-136CosttypeC[n+1][n+1];{costtypeLowCost[n+1];intCloseST[n+1];inti,j,k;costtypemin;

for(i=2;i<=n;i++){LowCost[i]=C[1][i];CloseST[i]=1;}//賦初值

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

{

min=LowCost[i];k=i;for(j=2;j<=n;j++)if(LowCost[j]<min){min=LowCost[j];k=j;}//求離U中某一頂點(diǎn)最近的頂點(diǎn)

Cout<<“(”<<k<<“,”<<CloseST[k]<<“)”<<end1;LowCost[k]=INFINITY;//將k加入集合U

for(j=2;j<=n;j++)if(C[k][j]<LowCost[j]&&LowCost[j]!=INFINITY){LowCost[j]=C[k][j];CloseST[j]=k;}//調(diào)整

}}CloseST[i]為U中的一個(gè)頂點(diǎn)邊(i,CloseST[i])具有最小的權(quán)LowCost[i]V3V1V4V5V2V66515536462C123456123456∞615∞∞6∞5∞3∞15∞5645∞5∞∞2∞36∞∞6∞∞426∞LowCost[i]i=123456123456--615∞-∞-5∞5645∞26∞5∞∞6∞∞∞∞3∞∞∞∞∞∞CloseST[i]i=123456123456--111113113331633316333162331622打印邊123456K(K,CloseST[K])3(3,1)6(6,3)4(4,6)2(2,3)5(5,2)for(j=2;j<=n;j++)if(C[k][j]<LowCost[j]&&LowCost[j]<INFINITY){LowCost[j]=C[k][j];CloseST[j]=k;}V3V1V4V5V2V66515536462【例4-3】K=?min(LowCost[])CloseST[i]為U中的一個(gè)頂點(diǎn)邊(i,CloseST[i])具有最小的權(quán)LowCost[i]UV-U123456615∞∞UV-U132

4565564算法要點(diǎn)：

令T=(V,E),(V=1,2,3,…,n),c是關(guān)于E中每條邊的權(quán)函數(shù)(1)T中每個(gè)頂點(diǎn)自身構(gòu)成一個(gè)連通分量；(2)按照邊的權(quán)不減的順序，依次考查E中的每條邊；(3)如果被考查的邊連接不同的分量中的兩個(gè)頂點(diǎn)，則合并兩個(gè)分量；(4)如果被考查的邊連接同一個(gè)分量中的頂點(diǎn)，則放棄，避免環(huán)路；(5)T中連通分量逐漸減少；當(dāng)T中的連通分量的個(gè)數(shù)為1時(shí)，說明V中的全部頂點(diǎn)通過E中權(quán)最小的那些邊，構(gòu)成了一個(gè)沒有環(huán)路的連通圖T，即為最小生成樹。（２）求最小生成樹——Kruskal算法輸入：連通圖G=(V,E)，其中v=(1,2,…,n)，C是關(guān)于E中的每條弧的權(quán)。輸出：G的最小生成樹VoidKruskal(V,T){T=V;ncomp=n;/*結(jié)點(diǎn)個(gè)數(shù)*/while(ncomp>1){從E中取出刪除權(quán)最小的邊（v,u）;if(v和u屬于T中不同的連通分量）

{T=T∪{(v,u)}ncomp--;}}}1264537182023122515851067412645371812158564【例4-4】求最小生成樹Prim算法與Kruskal算法的比較：都是貪心算法；Kruskal算法在效率上要比Prim算法快，因?yàn)镵ruskal只需要對權(quán)重邊做一次排序，而Prim算法則需要做多次排序。Prim算法是挨個(gè)找，而Kruskal是先排序再找。稀疏圖可以用Kruskal,因?yàn)镵ruskal算法每次查找最短的邊。稠密圖可以用Prim，因?yàn)樗敲看渭右粋€(gè)頂點(diǎn)，對邊數(shù)多的適用。egfhdbca2212121(b)egfhdbca2212121(c)egfhdbca23212412213(a)【例4-5】求最小生成樹*4.5無向圖的雙連通性(Biconnectivity)P1374.5.1無向圖的雙連通分量設(shè)G=(V,E)【定義】假若在刪去頂點(diǎn)v以及和v相關(guān)聯(lián)的邊之后，將圖的一個(gè)連同分量分割成兩個(gè)或兩個(gè)以上的連同分量，則稱該結(jié)點(diǎn)為關(guān)節(jié)點(diǎn)。abdecfg(a)bdecfg(b)abdefg(c)【定義】若對V中每個(gè)不同的三元組v,w,a；在v和w之間都存在一條不包含a的路，就說G是雙連通的（Biconnected）。先深搜索和先深編號的作用:

通過是否遇到回退邊，即可確定是否有環(huán)路。說V中的點(diǎn)a是一個(gè)關(guān)節(jié)點(diǎn)，若V中有結(jié)點(diǎn)v和w，使得v,w,a

各不相同且v

和w

之間的每條路都包含a

。

雙連通的無向圖是連通的，但連通的無向圖未必雙連通。一個(gè)連通的無向圖是雙連通的，當(dāng)且僅當(dāng)它沒有關(guān)節(jié)點(diǎn)?！径x】邊e1和e2等價(jià)，若e1=e2

或者有一條環(huán)路包含e1又包

含e2

，則稱邊e1

和e2

是等價(jià)的。【定義】設(shè)Vi

是

Ei

中各邊所連接的點(diǎn)集（1≤i≤k）,每個(gè)圖

Gi=(Vi,Ei)

叫做

G

的一個(gè)雙連通分量。雙連通分量的性質(zhì)：

性質(zhì)1：

Gi

是雙連通的（1≤i≤k）；

性質(zhì)2：對所有的i≠j,Vi∩Vj

最多包含一個(gè)點(diǎn)；

性質(zhì)3：

v

是G的關(guān)節(jié)點(diǎn)，當(dāng)且僅當(dāng)v∈Vi∩Vj(i≠j)。雙連通圖的研究意義：如通訊網(wǎng)絡(luò)。上述等價(jià)關(guān)系將E分成等價(jià)類E1,E2,…,Ek,兩條不同的邊屬于同一個(gè)類的充要條件是它們在同一個(gè)環(huán)路上。V1V2V3V4V5V6V9V7V8圖G圖G的雙連通分量V1V2V3（1）V4V6（4）V2V4V5（2）V6V9V7V8（3）【例4-6】雙連通分量(1)網(wǎng)狀網(wǎng)：結(jié)構(gòu)：所形成的網(wǎng)絡(luò)鏈路較多，形成的拓?fù)浣Y(jié)構(gòu)象網(wǎng)狀。優(yōu)點(diǎn)：線路冗余度大，網(wǎng)絡(luò)可靠性高，任意兩點(diǎn)間可直接通信；缺點(diǎn):線路利用率低(N值較大時(shí)傳輸鏈路數(shù)將很大)，網(wǎng)絡(luò)成本高，另外網(wǎng)絡(luò)的擴(kuò)容也不方便，每增加一個(gè)節(jié)點(diǎn)，就需增加N條線路。適用場合：通常用于節(jié)點(diǎn)數(shù)目少，又有很高可靠性要求的場合。(2)星形網(wǎng)又稱輻射網(wǎng)結(jié)構(gòu)：星形結(jié)構(gòu)由一個(gè)功能較強(qiáng)的轉(zhuǎn)接中心S以及一些各自連到中心的從節(jié)點(diǎn)組成。優(yōu)點(diǎn)：與網(wǎng)形網(wǎng)相比，降低了傳輸鏈路的成本，提高了線路的利用率缺點(diǎn):網(wǎng)絡(luò)的可靠性差，一旦中心轉(zhuǎn)接節(jié)點(diǎn)發(fā)生故障或轉(zhuǎn)接能力不足時(shí)，全網(wǎng)的通信都會受到影響。適用場合：傳輸鏈路費(fèi)用高于轉(zhuǎn)接設(shè)備、可靠性要求又不高的場合，以降低建網(wǎng)成本。局域網(wǎng)常見(3)樹型結(jié)構(gòu)分級結(jié)構(gòu)。在樹型結(jié)構(gòu)的網(wǎng)絡(luò)中，任意兩個(gè)結(jié)點(diǎn)之間不產(chǎn)生回路，每條通路都支持雙向傳輸。擴(kuò)充方便、靈活，成本低，易推廣適合于分主次或分等級的層次型管理系統(tǒng)。(4)總線型網(wǎng)屬于共享傳輸介質(zhì)型網(wǎng)絡(luò)結(jié)構(gòu)：網(wǎng)中的所有節(jié)點(diǎn)都連至一個(gè)公共的總線上，任何時(shí)候只允許一個(gè)用戶占用總線發(fā)送或接送數(shù)據(jù)。優(yōu)點(diǎn)：需要的傳輸鏈路少，節(jié)點(diǎn)間通信無需轉(zhuǎn)接節(jié)點(diǎn)，控制方式簡單，增減節(jié)點(diǎn)也很方便；缺點(diǎn)：網(wǎng)絡(luò)服務(wù)性能的穩(wěn)定性差，節(jié)點(diǎn)數(shù)目不宜過多，網(wǎng)絡(luò)覆蓋范圍也較小。適用場合：主要用于計(jì)算機(jī)局域網(wǎng)、電信接入網(wǎng)等網(wǎng)絡(luò)中。局域網(wǎng)常見(5)環(huán)形網(wǎng)結(jié)構(gòu)：網(wǎng)中所有節(jié)點(diǎn)首尾相連，組成一個(gè)環(huán)。優(yōu)點(diǎn)：是結(jié)構(gòu)簡單，容易實(shí)現(xiàn)，雙向自愈環(huán)結(jié)構(gòu)可以對網(wǎng)絡(luò)進(jìn)行自動(dòng)保護(hù)；缺點(diǎn)：是節(jié)點(diǎn)數(shù)較多時(shí)轉(zhuǎn)接時(shí)延無法控制，并且環(huán)形結(jié)構(gòu)不好擴(kuò)容。適用場合：目前主要用于計(jì)算機(jī)局域網(wǎng)、光纖接入網(wǎng)、城域網(wǎng)、光傳輸網(wǎng)等網(wǎng)絡(luò)中。(6)復(fù)合型網(wǎng)結(jié)構(gòu)：是由網(wǎng)狀網(wǎng)和星形網(wǎng)復(fù)合而成的。它以星形網(wǎng)為基礎(chǔ)，在業(yè)務(wù)量較大的轉(zhuǎn)接交換中心之間采用網(wǎng)狀網(wǎng)結(jié)構(gòu).優(yōu)點(diǎn)：兼并了網(wǎng)狀網(wǎng)和星形網(wǎng)的優(yōu)點(diǎn)。整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)比較經(jīng)濟(jì)，且穩(wěn)定性較好。適用場合：規(guī)模較大的局域網(wǎng)和電信骨干網(wǎng)中廣泛采用分級的復(fù)合型網(wǎng)絡(luò)結(jié)構(gòu)。4.5.2求關(guān)節(jié)點(diǎn)—對圖進(jìn)行一次先深搜索便可求出所有的關(guān)節(jié)點(diǎn)若生成樹的根有兩株或兩株以上子樹，則此根結(jié)點(diǎn)必為關(guān)節(jié)點(diǎn)（第一類關(guān)節(jié)點(diǎn)）。因圖中不存在連接不同子樹中頂點(diǎn)的邊，因此，若刪去根頂點(diǎn)，生成樹變成生成森林。若生成樹中非葉頂點(diǎn)v，其某株子樹的根和子樹中的其它結(jié)點(diǎn)均沒有指向v的祖先的回退邊，則v是關(guān)節(jié)點(diǎn)（第二類關(guān)節(jié)點(diǎn)）。因?yàn)閯h去v，則其子樹和圖的其它部分被分割開來。1abdecfg234567由先深生成樹可得出兩類關(guān)節(jié)點(diǎn)的特性：gcafedb定義low[v]：設(shè)對連通圖G＝（V,E）進(jìn)行先深搜索的先深編號

為dfn[v]，產(chǎn)生的先深生成樹為S＝（V,T），B是

回退邊之集。對每個(gè)頂點(diǎn)v，low[v]定義如下：gcafedbabdecfg12345671111555dfn

lowlow[v]=mindfn[v],dfn[w],low[y](v,w)∈B，w

是頂點(diǎn)v

在先深生成樹上有回退邊連接的祖先結(jié)點(diǎn)；(v,y)∈T，y

是頂點(diǎn)v

在先深生成樹上的孩子頂點(diǎn)Low[v]取頂點(diǎn)v和w的深度優(yōu)先編號的較小者，其中的w是從v點(diǎn)沿著零條或多條樹邊到v的后代x，之后沿著任意一條回退邊(x,w)所能達(dá)到的任何頂點(diǎn)。求無向圖的雙連通分量算法步驟：輸入：連通的無向圖G=(V,E)。L[v]表示關(guān)于v的鄰接表。輸出：G的所有雙連通分量，每個(gè)連通分量由一序列的邊組成。算法要點(diǎn)：(1)計(jì)算先深編號:對圖進(jìn)行先深搜索，計(jì)算每個(gè)結(jié)點(diǎn)v的先深編號

dfn[v]，形成先深生成樹S＝（V,T）。(2)計(jì)算low[v]:在先深生成樹上按后根順序進(jìn)行計(jì)算每個(gè)頂點(diǎn)v的

low[v]，low[v]取下述三個(gè)結(jié)點(diǎn)中的最小者：

1)dfn[v]:2)dfn[w]:凡是有回退邊（v,w）的任何結(jié)點(diǎn)w；

3)low[y]:對v的任何兒子(樹邊)y。(3)求關(guān)節(jié)點(diǎn):

1)樹根是關(guān)節(jié)點(diǎn)，當(dāng)且僅當(dāng)它有兩個(gè)或兩個(gè)以上的兒子

（第一類關(guān)節(jié)點(diǎn)）；

2)非樹根結(jié)點(diǎn)v是關(guān)節(jié)點(diǎn)當(dāng)且僅當(dāng)v有某個(gè)兒子y，使

low[y]≥dfn[v]（第二類關(guān)節(jié)點(diǎn)）。VoidsearchB(v){(1)makev“old”;(2)dfn[v]=count;(3)count++;(4)low[v]=dfn[v];(5)for(eachw∈L[v])(6)if(wismarked”new”)(7){add(v,w)toT;(8)father[w]=v;//w是v的兒子

(9)searchB(w);(10)if(low[w]>=dfn[v])Abiconnectedcomponenthasbeenfound;(11)low[v]=min(low[v],low[w]);}(12)elseif(wisnotfather[v])//(v,w)是回退邊

(13)low[v]=min(low[v],dfn[w]);}調(diào)用過程：T=￠;count=1;for(allv∈V)makev“new”;searchB(v0);//v0為任意頂點(diǎn)*4.6有向圖的搜索DFS和BFS搜索在有向圖和無向圖中的區(qū)別？有向圖搜索：樹邊、向前邊、回退邊、和橫邊。(1)若dfn[v]<dfn[w]，則(v,w)是樹邊或向前邊；

此時(shí)，visited[v]=“old”,visited[w]=“new”,(v,w)為樹邊；

visited[v]=“old”,visited[w]=“old”,(v,w)為向前邊。(2)若dfn[v]>dfn[w]，則(v,w)是回退邊或橫邊；

當(dāng)產(chǎn)生樹邊(i,j)時(shí)，同時(shí)記下j的父親：father[j]=i,于是對圖中任一條邊(v,w)，當(dāng)visited[v]=“old”,visited[w]=“old”且dfn[v]>dfn[w]時(shí)，由結(jié)點(diǎn)v沿著樹邊向上(father中)查找w（可能直到根）；若找到w,則(v,w)是回退邊，否則是橫邊。ABECDGHF(a)AECDGHFB12345678圖(a)先深生成森林ABECD(b)ABECD12345圖(b)先廣生成森林【例4-7】生成森林*4.7強(qiáng)連通性有向圖的強(qiáng)連通分量是滿足下列要求的最大子集：對任意兩個(gè)頂點(diǎn)x

和y

，都存在一條有向路從x

到y(tǒng)

，也存在一條有向路從y

到x?！径x】設(shè)G=（V,E）是一個(gè)有向圖，稱頂點(diǎn)v,w∈V是等價(jià)的，要么v=w；要么從頂點(diǎn)v

到w

有一條有向路，并且從頂點(diǎn)w

到v

也有一條有向路?！径x】設(shè)Ei（1≤i≤r）是頭、尾均在Vi

中的邊集,則:Gi

=(Vi,Ei)稱為G的一個(gè)強(qiáng)連通分量，簡稱強(qiáng)分量。上述等價(jià)關(guān)系將V分成若干個(gè)等價(jià)類V1，V2,…,Vr強(qiáng)連通圖：只有一個(gè)強(qiáng)分量的有向圖稱為強(qiáng)連通圖。分支橫邊：不在任何強(qiáng)連通分支（量）中的邊，如：a→d,c→d【注】每個(gè)結(jié)點(diǎn)都是在某個(gè)強(qiáng)連通分支中出現(xiàn)，但有些邊可能

不在任何強(qiáng)分支中。歸約圖：用強(qiáng)分量代表頂點(diǎn)，用分支橫邊代表有向邊的圖稱為原圖的歸約圖。顯然，歸約圖是一個(gè)不存在環(huán)路的有向圖，它表示了強(qiáng)分量之間的連通性。adcb(a)adcb(b)a,b,cd歸約圖adcb(a)eabcd(b)e54321abcd(c)e54321求強(qiáng)連通圖的實(shí)例求強(qiáng)連通圖算法步驟（P145）：(1)對有向圖G進(jìn)行DFS并按樹的逆先根順序?qū)旤c(diǎn)編號；(2)將G中的每條邊取反方向，構(gòu)造一個(gè)新的有向圖Gr;(3)根據(jù)(1)的編號，從編號最大頂點(diǎn)對圖Gr進(jìn)行一次DFS搜索，凡是經(jīng)過樹

邊（(1)中的分支橫邊除外）能到達(dá)的所有頂點(diǎn)，都形成一個(gè)DFS生成

樹；若本次搜索沒有達(dá)到所有頂點(diǎn)，則下次DFS從余下頂點(diǎn)中編號最大

的頂點(diǎn)開始；(4)在Gr的DFS生成深林中，每棵樹對應(yīng)與G的一個(gè)強(qiáng)連通分量。4.8拓?fù)浞诸惤o定一個(gè)無環(huán)路有向圖G=(V,E),各結(jié)點(diǎn)的編號為v=(1,2,…,n)。要求對每一個(gè)結(jié)點(diǎn)i

重新進(jìn)行編號，使得若i

是j的前導(dǎo)，則有Label[i]<label[j]。即拓?fù)浞诸愂菍o環(huán)路有向圖排成一個(gè)線性序列，使當(dāng)從結(jié)點(diǎn)i

到結(jié)點(diǎn)j存在一條邊，則在線性序列中，將i排在j

的前面。*+***+e+*+ecdabb+cdcd((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)有向無環(huán)圖及其應(yīng)用*+**++ecbcd*【問題1】日常工作中，可能會將項(xiàng)目拆分成A、B、C、D四個(gè)子部分來完成，但A依賴于B和D，C依賴于D。為了計(jì)算這個(gè)項(xiàng)目進(jìn)行的順序，可對這個(gè)關(guān)系集進(jìn)行拓?fù)渑判颍贸鲆粋€(gè)線性的序列，則排在前面的任務(wù)就是需要先完成的任務(wù)?！締栴}2】有n個(gè)士兵（1≤n≤26），編號依次為A、B、C，…

隊(duì)列訓(xùn)練時(shí)，指揮官要把一些士兵從高到矮依次排成一行。但現(xiàn)在指揮官不能直接獲得每個(gè)人的身高信息，只能獲得“p1比p2高”這樣的比較結(jié)果:（p1，p2∈{'A'，?，'Z'}），記為p1>p2。課程代號課程名稱先修課代號1計(jì)算機(jī)原理82編譯原理4,53操作系統(tǒng)4,54程序設(shè)計(jì)無5數(shù)據(jù)結(jié)構(gòu)4,66離散數(shù)學(xué)97形式語言68電路基礎(chǔ)99高等數(shù)學(xué)無10計(jì)算機(jī)網(wǎng)絡(luò)1【例4-8】12435678910v1v2v4v3v6v5v1v2v4v3v5v2v4v3v5v2v3v5v2v5v5可輸出結(jié)點(diǎn)的入度為零，刪去該結(jié)點(diǎn)，并將與該頂點(diǎn)相鄰的頂點(diǎn)的入度減1。V6V1V4V3V2V5021230入度V1V2V3V4V5v6top=0(a)021231入度(b)021121入度(c)014021入度(d)044011入度(e)044011入度(f)toptoptoptoptopv6→v1→v3→v2→v4→044001入度(f)topv5→044001入度(g)top=0v14v2v3v4v555322^^v654021230^^^^v1v2v4v3v6v561^top鏈棧的初始狀態(tài)進(jìn)棧：ID[i]=top;top=i;退棧：i=top;top=ID[top]021230入度ID[i]123456top=0014021入度top021231入度ID[i]123456top=661^top算法主要步驟：計(jì)算每個(gè)頂點(diǎn)i的入度ID[i]；for(i=1;i<=n;i++)//初始化鏈棧；

if(ID[i]==0){ID[i]=top;top=i;}for(i=1;i<=n;i++){輸出top指針指向的頂點(diǎn)；

k=top;top=ID[top];

頂點(diǎn)k的每一個(gè)鄰接點(diǎn)j的入度-1if