數(shù)據(jù)結(jié)構(gòu) 4第4章：圖學(xué)習(xí)課件

問題1：有一個(gè)長方形的房間，鋪設(shè)了方型瓷磚。瓷磚顏色或是紅色或是黑色。一名男子站在一個(gè)黑色的瓷磚上。從一個(gè)瓷磚，他可以轉(zhuǎn)移到四個(gè)相鄰瓷磚。但是他不能站在紅瓷磚上，他只能移動(dòng)在黑瓷磚上。通過走過的黑瓷磚計(jì)算黑瓷磚的片數(shù)。

題目要求只能走黑格子而不能走紅格子，從其中一塊黑格子開始求出可以到達(dá)的黑格子數(shù)。問題2：計(jì)算國際象棋中騎士從一個(gè)指定位置到達(dá)目的位置的最少步數(shù)。因?yàn)槊恳淮味加?種走法，要把可行的走法記錄下來，直到走到終點(diǎn)為止。輸出最少的步數(shù)。問題3：給一堆格式為A

<

B

的關(guān)系式，然后判斷有沒有一個(gè)可以排列的順序，輸出判斷結(jié)果。當(dāng)一個(gè)升序序列確定時(shí)，輸出確定時(shí)處理到第幾個(gè)關(guān)系式和排好序的升序序列；當(dāng)不確定時(shí)，輸出不確定；當(dāng)矛盾時(shí)，輸出發(fā)現(xiàn)矛盾時(shí)處理到第幾個(gè)關(guān)系。先提幾個(gè)問題：？問題4：大道路網(wǎng)的維護(hù)成本太高了，必須選擇停止維持一些道路，當(dāng)然需要有一些辦法讓所有村莊之間都有路到達(dá)，即使路線并不像以前一樣短。寫一個(gè)程序，將解決選擇一些路，使得總的維護(hù)費(fèi)用最少。問題5：要用最快的方法將消息傳給你所有的客戶，而客戶只信任他們認(rèn)為信得過的人，按照此要求找出傳播最快的方法。4.1基本術(shù)語4.2圖的表示

4.3圖的搜索算法4.4圖與樹的聯(lián)系

4.5無向圖的雙連通性*4.6有向圖的搜索

4.7強(qiáng)連通圖

4.8拓?fù)浞诸?4.9關(guān)鍵路徑

4.10單源最短路徑*4.11每一對(duì)頂點(diǎn)間的最短路徑第4章圖以及與圖有關(guā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）。[ADT]GraphG=(V,R)

數(shù)據(jù)對(duì)象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>的意義或信息}操作：NodeNewNode(G,v)VoidDelNode(G,v)VoidSetSucc(G,v1,v2)VoidDelSucc(G,v1,v2)ListofnodeSucc(G,v)LisyofnodePred(G,v)IntIsEdge(G,v1,v2)NodeFirstAdjVex(G,v)NodeNextAdjVex(G,v,w)術(shù)語：頂點(diǎn)弧/邊鄰接/相鄰依附路徑（路）簡單路徑環(huán)路帶標(biāo)號(hào)的圖（網(wǎng)）

連通連通圖

強(qiáng)連通圖連通分量完全圖稀疏圖稠密圖子圖度入度出度生成樹V3V1V4V5V2G2V1V3V4V2G10110000000011000G1.arcs0101010101010111010001100G2.arcs126543545983516∞3∞∞∞1∞∞5∞3∞∞∞∞4∞∞98∞∞∞∞6∞∞5∞∞∞∞∞∞∞534.2圖的表示1、圖的順序存儲(chǔ)——鄰接矩陣設(shè)圖G=(V,E)，V={0，1，…，n-1}則表示G的鄰接矩陣A是其元素按下式定義的nxn矩陣: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[j][i](n頂點(diǎn)個(gè)數(shù)）j=0n-1j=0n-1TD(vi)=OD(vi)+ID(vi)=∑A[i][j]＋∑A[j][i](n頂點(diǎn)個(gè)數(shù)）j=0n-1j=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;例：圖類型變量：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)，存儲(chǔ)結(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)酱鎯?chǔ)——鄰接表（AdjacencyList）2、圖的鏈?zhǔn)酱鎯?chǔ)——鄰接表（AdjacencyList）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

;例：圖類型變量：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->adjvexG.vertices[G.vertices[i].firstarc->adjvex].dataG.vertices[i].firstarc->info頂點(diǎn)i的第二個(gè)鄰接點(diǎn)：

G.vertices[i].firstarc->nextarc->adjvex圖的操作FirstAdjVex(),NextAdjVex()的實(shí)現(xiàn)，存儲(chǔ)結(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);}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);}v13v2v3v4v54422123010101234^^無向圖G2鄰接表V3V1V4V5V2G2圖G2的深度優(yōu)先遍歷結(jié)果：V1,V4,V3,V5,V2{T=￠;/*樹邊集開始為空*/count=1;/*先深編號(hào)計(jì)數(shù)器*/for(allv∈V)while(thereexistsavertexv∈Vmarked“new”)search(v)}

voidsearch(v){dfn[v]=count;/*對(duì)v編號(hào)*/count=count+1;markv“old”/*訪問結(jié)點(diǎn)v*/for(eachvertexw∈L[v])if(wismarked“new”{add(v,w)toT;/*(v,w)是樹邊*/search(w);/*遞歸搜索*/}}輸入：L[v]表示無向圖G的關(guān)于v的鄰接表輸出：每個(gè)結(jié)點(diǎn)有先深編號(hào)的無向圖和樹邊集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){visited[u]=TRUE;visit(u);if(!visited[w])EnQueue(Q,w);}}}}v13v2v3v4v54422123010101234^^無向圖G2鄰接表V3V1V4V5V2G2圖G2的廣度優(yōu)先遍歷結(jié)果：V1,V4,V2,V3,V5Voidbsearch(v){MAKENULL(Q);bfn[v]=count;/*先廣編號(hào)*/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;/*先廣編號(hào)*/count=count+1;markw“old”;ENQUEUE(w,Q);INSERT((v,w),T);}}/*樹邊入隊(duì)*/}輸入：L[v]表示無向圖G的關(guān)于v的鄰接表輸出：每個(gè)結(jié)點(diǎn)有先廣編號(hào)的無向圖和樹邊集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)路軌跡是什么？intExistPathDfs1(ALGraphG,int*visited,intu,intv)//實(shí)現(xiàn)1：判斷是否存在從u到v的路徑，返回1或0{

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);}//ExistPathDfs1intExistPathDfs2(ALGraphG,int*visited,intu,intv)//實(shí)現(xiàn)2：判斷u到v是否有通路,返回1或0{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);}//ExistPathDfs2intFindAllPath(ALGraphG,int*visited,int*path,intu,intv,intk)//求u到v所有簡單路徑{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))intCycle(ALGraphG,int*visited,intu){/*判斷圖是否存在包含定點(diǎn)u的回路*/

ArcNode*p;intw,flag=0;visited[u]=1;p=G.vertices[u].firstarc;while(p&&!flag){w=p->adjvex;if(visited[w]!=1)//w未訪問過(0)或訪問且其鄰接點(diǎn)已訪問完(2)

{if(!visited[w])//w未訪問過，從w開始繼續(xù)dfsflag=Cycle(G,visited,w); }else//頂點(diǎn)w已經(jīng)訪問過，并且其鄰接點(diǎn)已經(jīng)訪問完

flag=1;p=p->nextarc;}visited[u]=2;return(flag);}Visited[i]=0：未訪問;1：已訪問但其鄰接點(diǎn)未訪問完;2：已訪問且其鄰接點(diǎn)已訪問完。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=Cycle(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)樹邊(編號(hào)小->大)與非樹邊：回退邊/橫邊(編號(hào)大->小)先深（廣）搜索過程中，由樹邊和樹邊所連接的頂點(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ì)

設(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)的最小生成樹。描述1：描述2：UV－Uuvu’v’MST性質(zhì)證明假設(shè)網(wǎng)N的任何一棵最小生成樹都不包含（u,v），設(shè)T是連通網(wǎng)上的一棵最小生成樹，當(dāng)將邊（u,v）加入到T中時(shí)，由生成樹的定義，T中必包含一條（u,v）的回路。另一方面，由于T是生成樹，則在T上必存在另一條邊（u’,v’），且u和u’、v和v’之間均有路徑相同。刪去邊(u’,v’)便可消去上述回路，同時(shí)得到另一棵最小生成樹T’。但因?yàn)?u,v)的代價(jià)不高于(u’,v’)，則T’的代價(jià)亦不高于T，T’是包含（u，v）的一棵最小生成樹。（a）V3V1V4V5V2V66515536462V3V1V4V5V2（c）V614V3V1V4V5V2（d）V6142V3V1V4V5V2（e）V61542V3V1V4V5V2（f）V615342求最小生成樹V3V1V4V5V2（b）V61UV-U高速公路問題：假設(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í)滿足所修公路總長最短在n個(gè)城市間建立通信網(wǎng)絡(luò)，需架設(shè)n-1條線路。求解如何以最低經(jīng)濟(jì)代價(jià)建設(shè)此通信網(wǎng)。

很多關(guān)于最小成本的問題都可以通過求帶權(quán)圖的最小生成樹來解決。某市區(qū)有七個(gè)住宅小區(qū)需要鋪設(shè)天然氣管道,各小區(qū)的位置及它們之間可修建管道路線與費(fèi)用如圖所示.現(xiàn)要設(shè)計(jì)一個(gè)管道鋪設(shè)路線,要求天然氣能輸送到各個(gè)小區(qū)并且修建的總費(fèi)用為最小,這就是求最小生成樹的問題１、求最小生成樹——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,（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[]和LOWCOSTCLOSEST[i]為U中的一個(gè)頂點(diǎn)則邊(i,CLOSEST[i])具有最小的權(quán)LOWCOST[i]集合如何實(shí)現(xiàn)？若頂點(diǎn)i∈U則LOWCOST[i]=INFINITYCLOSTST和LOWCOST的初值是多少？開始調(diào)整LOWCOST,對(duì)非集合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[例]K=?min(LOWCOST[])CLOSEST[i]為U中的一個(gè)頂點(diǎn)邊(i,CLOSEST[i])具有最小的權(quán)LOWCOST[i]算法要點(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--;}}}1264537182023122515851067412645371812158564egfhdbca2212121(b)egfhdbca2212121(c)egfhdbca23212412213(a)*4.5無向圖的雙連通性(Biconnectivity)P1374.4.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)[定義]

若對(duì)V中每個(gè)不同的三元組v,w,a；在v和w之間都存在一條不包含a的路，就說G是雙連通的（Biconnected）先深搜索和先深編號(hào)的作用:

通過是否遇到回退邊，即可確定是否有環(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)。[定義]

邊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：對(duì)所有的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è)類的充要條件是它們?cè)谕粋€(gè)環(huán)路上。V1V2V3V4V5V6V9V7V8無向圖和它的雙連通分量圖G圖G的雙連通分量V1V2V3（1）V4V6（4）V2V4V5（2）V6V9V7V8（3）(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)的通信都會(huì)受到影響。適用場合：傳輸鏈路費(fèi)用高于轉(zhuǎn)接設(shè)備、可靠性要求又不高的場合，以降低建網(wǎng)成本。局域網(wǎng)常見(3)樹型結(jié)構(gòu)分級(jí)結(jié)構(gòu)。在樹型結(jié)構(gòu)的網(wǎng)絡(luò)中，任意兩個(gè)結(jié)點(diǎn)之間不產(chǎn)生回路，每條通路都支持雙向傳輸。擴(kuò)充方便、靈活，成本低，易推廣適合于分主次或分等級(jí)的層次型管理系統(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)可以對(duì)網(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)中廣泛采用分級(jí)的復(fù)合型網(wǎng)絡(luò)結(jié)構(gòu)。4.4.2求關(guān)節(jié)點(diǎn)—對(duì)圖進(jìn)行一次先深搜索便可求出所有的關(guān)節(jié)點(diǎn)若生成樹的根有兩株或兩株以上子樹，則此根結(jié)點(diǎn)必為關(guān)節(jié)點(diǎn)

（第一類關(guān)節(jié)點(diǎn)）。因?yàn)閳D中不存在連接不同子樹中頂點(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è)對(duì)連通圖G＝（V,E）進(jìn)行先深搜索的先深編號(hào)

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

回退邊之集。對(duì)每個(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)先編號(hào)的較小者，其中的w是從v點(diǎn)沿著零條或多條樹邊到v的后代x，之后沿著任意一條回退邊(x,w)所能達(dá)到的任何頂點(diǎn)算法4.5求無向圖的雙連通分量輸入：連通的無向圖G=(V,E)。L[v]表示關(guān)于v的鄰接表。輸出：G的所有雙連通分量，每個(gè)連通分量由一序列的邊組成。算法要點(diǎn)：1.計(jì)算先深編號(hào)：對(duì)圖進(jìn)行先深搜索，計(jì)算每個(gè)結(jié)點(diǎn)v的先深編號(hào)

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]:對(duì)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,于是對(duì)圖中任一條邊(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強(qiáng)連通性有向圖的強(qiáng)連通分量是滿足下列要求的最大子集：對(duì)任意兩個(gè)頂點(diǎn)x

和y

，都存在一條有向路從x

到y(tǒng)

，也存在一條有向路從y

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

到w

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

到v

也有一條有向路。[定義]設(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算法:P145，(step1---step4)求強(qiáng)連通圖的實(shí)例4.8拓?fù)浞诸惤o定一個(gè)無環(huán)路有向圖G=(V,E),各結(jié)點(diǎn)的編號(hào)為v=(1,2,…,n)。要求對(duì)每一個(gè)結(jié)點(diǎn)i

重新進(jìn)行編號(hào)，使得若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：在日常工作中，可能會(huì)將項(xiàng)目拆分成A、B、C、D四個(gè)子部分來完成，但A依賴于B和D，C依賴于D。為了計(jì)算這個(gè)項(xiàng)目進(jìn)行的順序，可對(duì)這個(gè)關(guān)系集進(jìn)行拓?fù)渑判颍贸鲆粋€(gè)線性的序列，則排在前面的任務(wù)就是需要先完成的任務(wù)。例2：有n個(gè)士兵（1≤n≤26），編號(hào)依次為A、B、C，??

隊(duì)列訓(xùn)練時(shí)，指揮官要把一些士兵從高到矮依次排成一行。但現(xiàn)在指揮官不能直接獲得每個(gè)人的身高信息，只能獲得“p1比p2高”這樣的比較結(jié)果:（p1，p2∈{'A'，?，'Z'}），記為p1>p2。課程代號(hào)課程名稱先修課代號(hào)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例：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(ID[j]==0){ID[j]=top;top=j;}}進(jìn)棧：ID[i]=top;top=i;退棧：i=top;top=ID[top]StatusTopologicalsort(ALGRAPHG){FindInDegree(G,indegree);MakeNUlLL(S);for(v=0;v<n;++v)if(!indegree[v])push(v,S);count=0;while(!EMPTY(S)){v=pop(S);printf(v);++count;for(鄰接于v的每個(gè)頂點(diǎn)w){if(!(--indegree[w]))push(S,w);}}if(count<n)cout<<“圖中有環(huán)路”;elsereturnOK;}算法一：應(yīng)用棧StatusTopologicalsort(L){QUEUEQ;MakeNUlLL(Q);for(v=1;v<=n;++v)if(indegree[v]=0)ENQUEUE(v,Q);nodes=0;while(!EMPTY(Q)){v=FRONT(Q);DEQUEUE(Q);cout<<v;nodes++;for(鄰接于v的每個(gè)頂點(diǎn)w)if(!(--indegree[w]))ENQUEUE(w,Q);}if(nodes<n)cout<<“圖中有環(huán)路”;}算法二：應(yīng)用隊(duì)列算法三：DFS遍歷生成拓?fù)湫蛄蠽oidtopodfs(v){PUSH(v,S);mark[v]=TRUE;for(L[v]中的每一個(gè)頂點(diǎn)w)doif(mark[w]=FALSE)topodfs(w);printf(top(S));POP(S);}Voiddfs-topo(GRAPHL){MAKENULL(S);for(u=1;u<=n;u++)make[u]=FALSE;for(u=1;u<=n;u++)if(!mark[u])topodfs(u);}思想：借助棧，在DFS中，把第一次遇到的頂點(diǎn)入棧，到達(dá)某一頂點(diǎn)遞歸返回，從棧中彈出頂點(diǎn)并輸出。AOE網(wǎng)（ActivityOnEdgeNetwork）

在帶權(quán)的有向圖中，用結(jié)點(diǎn)表示事件，用邊表示活動(dòng)，邊上權(quán)表示活動(dòng)的開銷（