圖的定義和術(shù)語概要課件

第七章圖第七章圖

第七章圖7.1圖的定義和術(shù)語7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖及應(yīng)用7.6最短路徑第七章圖第七章圖本章介紹另一種非線性數(shù)據(jù)結(jié)構(gòu)——圖圖：是一種多對(duì)多的結(jié)構(gòu)關(guān)系，每個(gè)元素可以有零個(gè)或多個(gè)直接前趨；零個(gè)或多個(gè)直接后繼；第七章圖本章介紹另一種非線性數(shù)據(jù)結(jié)構(gòu)——圖第七章圖

學(xué)習(xí)要點(diǎn)1．熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解實(shí)際問題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系；2．熟練掌握?qǐng)D的兩種遍歷：深度優(yōu)先遍歷和廣度優(yōu)先遍歷的算法。在學(xué)習(xí)中應(yīng)注意圖的遍歷算法與樹的遍歷算法之間的類似和差異。樹的先根遍歷是一種深度優(yōu)先搜索策略，樹的層次遍歷是一種廣度優(yōu)先搜索策略3．理解課件中討論的各種圖的算法；

第七章圖

學(xué)習(xí)要點(diǎn)7.1圖的定義和術(shù)語一圖的概念

圖G由兩個(gè)集合構(gòu)成，記作G=<V,E>其中V是頂點(diǎn)的非空有限集合，E是邊的有限集合，其中邊是頂點(diǎn)的無序?qū)蛴行驅(qū)?。例G1=<V1,E1>V1={v1,v2,v3,v4,v5}E1={(v1,v2),(v1,v3),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}G1圖示無序?qū)?vi,vj)：用表示頂點(diǎn)vi、vj的線段，稱為無向邊；

V5V1

V2

V4

V37.1圖的定義和術(shù)語一圖的概念例G1=<V1,E17.1圖的定義和術(shù)語例G2=<V2,E2>V2={v1,v2,v3,v4}E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}G2圖示有序?qū)?lt;vi,vj>：用以表示以vi起點(diǎn)、以vj為終點(diǎn)的有向線段，稱為有向邊或??；無向圖：在圖G中，若所有邊是無向邊，則稱G為無向圖；有向圖：在圖G中，若所有邊是有向邊，則稱G為有向圖；混和圖：在圖G中，即有無向邊也有有向邊，則稱G為混合圖；

V1

V2

V3

V4V1稱為弧尾(初始點(diǎn))V3稱為弧頭(終端點(diǎn))7.1圖的定義和術(shù)語例G2=<V2,E2>G2圖示有序7.1圖的定義和術(shù)語圖的應(yīng)用舉例例1交通圖（公路、鐵路）頂點(diǎn)：地點(diǎn)邊：連接地點(diǎn)的公路交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；例2電路圖頂點(diǎn)：元件邊：連接元件之間的線路例3通訊線路圖頂點(diǎn)：地點(diǎn)邊：地點(diǎn)間的連線例4各種流程圖如產(chǎn)品的生產(chǎn)流程圖頂點(diǎn)：工序邊：各道工序之間的順序關(guān)系

V5V1

V2

V4

V37.1圖的定義和術(shù)語圖的應(yīng)用舉例V5V1V2V47.1圖的定義和術(shù)語三圖的基本操作1CreateGraph(&G,V,VR);初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合操作結(jié)果：按V和VR的定義構(gòu)造圖G2DestroyGraph(&G);初始條件：圖G存在操作結(jié)果：銷毀圖G3LocateVex(G,u);初始條件：圖G存在，u和G中頂點(diǎn)有相同特征操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回其它信息。4GetVex(G,v);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)操作結(jié)果：返回v的值5PutVex(&G,v,value);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)操作結(jié)果：對(duì)v賦值value7.1圖的定義和術(shù)語三圖的基本操作7.1圖的定義和術(shù)語6FirstAdjVex(G,v);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)操作結(jié)果：返回v的第一個(gè)鄰接頂點(diǎn)。若頂點(diǎn)在G中沒有鄰接頂點(diǎn)，則返回“空”。7NextAdjVex(G,v,w);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)。操作結(jié)果：返回v的（相對(duì)于w的）下一個(gè)鄰接頂點(diǎn)。若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”。8InsertVex(&G,v);初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征。操作結(jié)果：在圖G中增添新頂點(diǎn)v9DeleteVex(&G,v);初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征操作結(jié)果：刪除G中頂點(diǎn)v及相關(guān)的弧7.1圖的定義和術(shù)語6FirstAdjVex(G,v7.1圖的定義和術(shù)語10InsertArc(&G,v,w);初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中增添弧<v,w>，若G是無向的，則還增添對(duì)稱弧<w,v>11DeleteArc(&G,v,w);初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中刪除弧<v,w>，若G是無向的，則還刪除對(duì)稱弧<w,v>12DFSTraverse(G,v,Visit());初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：從頂點(diǎn)v起深度優(yōu)先遍歷圖G，對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗13BFSTraverse(G,v,Visit());初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且一次。一旦visit()失敗，則操作失敗7.1圖的定義和術(shù)語10InsertArc(&G,v7.1圖的定義和術(shù)語圖的基本術(shù)語1鄰接點(diǎn)及關(guān)聯(lián)邊

鄰接點(diǎn)：邊的兩個(gè)頂點(diǎn)

關(guān)聯(lián)邊：若邊e=(v,u),則稱頂點(diǎn)v、u關(guān)聯(lián)邊e（邊e依附于頂點(diǎn)v,u)2頂點(diǎn)的度、入度、出度

頂點(diǎn)V的度=與V相關(guān)聯(lián)的邊的數(shù)目在有向圖中：頂點(diǎn)V的出度=以V為起點(diǎn)有向邊數(shù)

頂點(diǎn)V的入度=以V為終點(diǎn)有向邊數(shù)頂點(diǎn)V的度=V的出度+V的入度設(shè)圖G的頂點(diǎn)數(shù)為n，邊數(shù)為e

圖的所有頂點(diǎn)的度數(shù)和=2*e（每條邊對(duì)圖的所有頂點(diǎn)的度數(shù)和“貢獻(xiàn)”2度）

e1

V1

V2

V3

V4

V5V1

V2

V4

V37.1圖的定義和術(shù)語圖的基本術(shù)語e1V1V2V33有向完全圖、無向完全圖有向完全圖——n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)無向完全圖——n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是n(n-1)/2權(quán)(weight)——與圖的邊或弧相關(guān)的數(shù)叫~網(wǎng)——帶權(quán)的圖叫~7.1圖的定義和術(shù)語3有向完全圖、無向完全圖7.1圖的定義和術(shù)語7.1圖的定義和術(shù)語

路徑、回路

無向圖中的頂點(diǎn)序列v1,v2,…,vk,若(vi,vi+1)E(i=1,2,…k-1),v=v1,u=vk,

則稱該序列是從頂點(diǎn)v到頂點(diǎn)u的路徑；若v=u，則稱該序列為回路；

有向圖D=(V，E）中的頂點(diǎn)序列v1,v2,…,vk,若<vi,vi+1>E(i=1,2,…k-1),v=v1,u=vk,則稱該序列是從頂點(diǎn)v到頂點(diǎn)u的路徑；若v=u，則稱該序列為回路；

例在圖1中，V1,V2,V3,V4是V1到V4的路徑；V1,V2,V3,V4,V1是回路；在圖2中，V1,V3,V4是V1到V4的路徑；V1,V3,V4,V1是回路；

V5V1

V2

V4

V3

V1

V2

V3

V4圖1圖27.1圖的定義和術(shù)語路徑、回路V5V1V2V47.1圖的定義和術(shù)語連通圖、（強(qiáng)連通圖）

在無（有）向圖G=<V,E>中，若對(duì)任何兩個(gè)頂點(diǎn)v、u都存在從v到u的路徑，則稱G是連通圖（強(qiáng)連通圖）

V5

V6

V3

V1

V2

V4連通圖非連通圖

V5V1

V2

V4

V37.1圖的定義和術(shù)語連通圖、（強(qiáng)連通圖）V5V6V7.1圖的定義和術(shù)語子圖

設(shè)有兩個(gè)圖G=（V，E）、G1=（V1，E1），若V1V，E1E，E1關(guān)聯(lián)的頂點(diǎn)都在V1中，則稱G1是G的子圖；例圖2、圖3是圖1的子圖

V5V1

V2

V4

V3

V5V1

V2

V3

V5V1

V2

V4

V3圖1圖2圖37.1圖的定義和術(shù)語子圖V5V1V2V4V37.1圖的定義和術(shù)語連通分圖（強(qiáng)連通分量）

無向圖G的極大連通子圖稱為G的連通分量極大連通子圖意思是：該子圖是G連通子圖，將G的任何不在該子圖中的頂點(diǎn)加入，子圖不再連通；有向圖D的極大強(qiáng)連通子圖稱為D的強(qiáng)連通分量極大強(qiáng)連通子圖意思是：該子圖是D強(qiáng)連通子圖，將D的任何不在該子圖中的頂點(diǎn)加入，子圖不再是強(qiáng)連通的；

V5

V6

V3

V1

V2

V4連通分圖7.1圖的定義和術(shù)語連通分圖（強(qiáng)連通分量）V5V67.1圖的定義和術(shù)語

V5V1

V2

V4

V3

V5V1

V2

V4

V38生成樹（

包含無向圖G所有頂點(diǎn)的的極小連通子圖稱為G生成樹極小連通子圖意思是：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通，若T是G的生成樹當(dāng)且僅當(dāng)T滿足如下條件T是G的連通子圖T包含G的所有頂點(diǎn)T中無回路只有足以構(gòu)成一棵樹的n-1條邊7.1圖的定義和術(shù)語V5V1V2V4V3V5例213213有向完全圖無向完全圖356例245136圖與子圖例245136G1頂點(diǎn)2入度：1出度：3頂點(diǎn)4入度：1出度：0例157324G26頂點(diǎn)5的度：3頂點(diǎn)2的度：4例213213有向完全圖無向完全圖356例245136圖與子例157324G26例245136G1路徑：1，2，3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡單回路：1，2，3，1例157324G26例245136G1路徑：1，2，3，5，連通圖例245136強(qiáng)連通圖356例非連通圖連通分量例245136連通圖例245136強(qiáng)連通圖356例非連通圖連通分量例245第七章圖7.2圖的存儲(chǔ)結(jié)構(gòu)數(shù)組表示法鄰接表第七章圖7.2圖的存儲(chǔ)結(jié)構(gòu)7.2圖的存儲(chǔ)結(jié)構(gòu)

圖是多對(duì)多的結(jié)構(gòu)，比線性結(jié)構(gòu)、樹結(jié)構(gòu)復(fù)雜，所以其存儲(chǔ)結(jié)構(gòu)也要復(fù)雜些。與線性結(jié)構(gòu)、樹結(jié)構(gòu)一樣，圖的存儲(chǔ)結(jié)構(gòu)至少要保存兩類信息： 1)頂點(diǎn)的數(shù)據(jù)2) 頂點(diǎn)間的關(guān)系頂點(diǎn)的編號(hào)

為了使圖的存儲(chǔ)結(jié)構(gòu)與圖一一對(duì)應(yīng)，在討論圖的存儲(chǔ)結(jié)構(gòu)時(shí)，首先要給圖的所有頂點(diǎn)編號(hào)。

本課程介紹兩類圖的存儲(chǔ)結(jié)構(gòu)

數(shù)組表示法 鄰接表（鄰接表，逆鄰接表）

設(shè)G=<V,E>是圖,V={v1,v2,v3,…

vn},設(shè)頂點(diǎn)的的角標(biāo)為它的編號(hào)如何表示頂點(diǎn)間的關(guān)系？？7.2圖的存儲(chǔ)結(jié)構(gòu)圖是多對(duì)多的結(jié)構(gòu)，比線7.2圖的存儲(chǔ)結(jié)構(gòu)

鄰接矩陣：G的鄰接矩陣是滿足如下條件的n階矩陣：

一數(shù)組表示法數(shù)組表示法是圖的一種順序存儲(chǔ)結(jié)構(gòu)在數(shù)組表示法中，用鄰接矩陣表示頂點(diǎn)間的關(guān)系A(chǔ)[i][j]=1若(vi,vi+1)E或<vi,vi+1>E0否則

V5V1

V2

V4

V301010010101011010001100011000000001000

V1

V2

V3

V47.2圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣：G的鄰接矩陣是滿足如下條7.2圖的存儲(chǔ)結(jié)構(gòu)數(shù)組表示法頂點(diǎn)的存儲(chǔ)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）頂點(diǎn)間關(guān)系：用二維數(shù)組存儲(chǔ)圖的鄰接矩陣；012345m-1V1V2V3V4V5存儲(chǔ)頂點(diǎn)的一維數(shù)組存儲(chǔ)鄰接矩陣的二維數(shù)組010101010101234mm+1m+2m+3m+47.2圖的存儲(chǔ)結(jié)構(gòu)數(shù)組表示法0V1存儲(chǔ)頂點(diǎn)的存儲(chǔ)鄰接矩陣7.2圖的存儲(chǔ)結(jié)構(gòu)數(shù)組表示法類型定義#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20typedefenum{DG,DN,AG,AN}GraphKind;typedefstructArcCell{VRTypeadj;InfoType*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]typedefstruct{VetexTypevexs[MAX_VERTEX_NUM];AdjMatrixarc;intvexnum,arcnum;GraphKindkind;}MGraph;7.2圖的存儲(chǔ)結(jié)構(gòu)數(shù)組表示法類型定義7.2圖的存儲(chǔ)結(jié)構(gòu)設(shè)G是Mgraph類型的變量，用于存儲(chǔ)無向圖，該圖有n個(gè)頂點(diǎn)，e條邊G的圖示如下：G.vexsG.arcsG.vexnumG.arcnuG.kindV10neAG頂點(diǎn)數(shù)組存儲(chǔ)鄰接矩陣的二維數(shù)組7.2圖的存儲(chǔ)結(jié)構(gòu)設(shè)G是Mgraph類型的變量，用于存7.2圖的存儲(chǔ)結(jié)構(gòu)無向圖數(shù)組表示法特點(diǎn)：1）無向圖鄰接矩陣是對(duì)稱矩陣，同一條邊表示了兩次；2）頂點(diǎn)v的度：等于二維數(shù)組對(duì)應(yīng)行（或列）中1的個(gè)數(shù)；3）判斷兩頂點(diǎn)v、u是否為鄰接點(diǎn)：只需判二維數(shù)組對(duì)應(yīng)分量是否為1；4）頂點(diǎn)不變，在圖中增加、刪除邊：只需對(duì)二維數(shù)組對(duì)應(yīng)分量賦值1或清0；5）設(shè)存儲(chǔ)頂點(diǎn)的一維數(shù)組大小為m(m圖的頂點(diǎn)數(shù)n),G占用存儲(chǔ)空間：m+m2；G占用存儲(chǔ)空間只與它的頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān)；適用于邊稠密的圖；對(duì)有向圖的數(shù)組表示法可做類似的討論

7.2圖的存儲(chǔ)結(jié)構(gòu)無向圖數(shù)組表示法特點(diǎn)：7.2圖的存儲(chǔ)結(jié)構(gòu)鄰接表鄰接表是圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1無向圖的鄰接表頂點(diǎn)：通常按編號(hào)順序?qū)㈨旤c(diǎn)數(shù)據(jù)存儲(chǔ)在一維數(shù)組中；關(guān)聯(lián)同一頂點(diǎn)的邊：用線性鏈表存儲(chǔ)

V5V1

V2

V4

V3例

01234m-1V1V2V3V4V513422110043該結(jié)點(diǎn)表示邊（V1V2）,其中的1是V2在一維數(shù)組中的位置7.2圖的存儲(chǔ)結(jié)構(gòu)鄰接表V5V1V2V4V3例7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表類型定義#defineMAX_VERTEX_NUM20typedefstructArcNode{//邊（?。┙Y(jié)點(diǎn)的類型定義intadjvex;//邊（?。┑牧硪豁旤c(diǎn)的在數(shù)組中的位置structArcNode*nextarc;//指向下一條邊（?。┙Y(jié)點(diǎn)的指針I(yè)nfoType*info;}ArcNode;typedefstructVNode{//頂點(diǎn)結(jié)點(diǎn)和數(shù)組的類型定義VertexTypedata;//頂點(diǎn)信息ArcNode*finrstarc;//指向關(guān)聯(lián)該頂點(diǎn)的邊（?。╂湵韢VNode,AjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)intkind;//圖的種類標(biāo)志}ALGraph;7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表類型定義7.2圖的存儲(chǔ)結(jié)構(gòu)設(shè)G是ALGraph類型的變量，用于存儲(chǔ)無向圖G1，該圖有n個(gè)頂點(diǎn)，e條邊G的圖示如下：

V5V1

V2

V4

V3無向圖G1該結(jié)點(diǎn)表示邊（V5,V2）,其中的1是V2在一維數(shù)組中的位置G.verticesG.vexnumG.arcnuG.kind

012

4m-1V1V2V3V4V5neAatafirstarcadjvexnextarc7.2圖的存儲(chǔ)結(jié)構(gòu)設(shè)G是ALGraph類型的變量，用于7.2圖的存儲(chǔ)結(jié)構(gòu)無向圖的鄰接表的特點(diǎn)1）在G鄰接表中，同一條邊對(duì)應(yīng)兩個(gè)結(jié)點(diǎn)；

2）頂點(diǎn)v的度：等于v對(duì)應(yīng)線性鏈表的長度；3）判定兩頂點(diǎn)v，u是否鄰接：要看v對(duì)應(yīng)線性鏈表中有無對(duì)應(yīng)的結(jié)點(diǎn)4）在G中增減邊：要在兩個(gè)單鏈表插入、刪除結(jié)點(diǎn)；

7.2圖的存儲(chǔ)結(jié)構(gòu)無向圖的鄰接表的特點(diǎn)7.2圖的存儲(chǔ)結(jié)構(gòu)D.verticesD.vexnumD.arcnuD.kind

V1V2V3V4neDG1230

V1

V2

V3

V4例2有向圖的鄰接表和逆鄰接表1）有向圖的鄰接表頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）以同一頂點(diǎn)為起點(diǎn)的弧：用線性鏈表存儲(chǔ)類似于無向圖的鄰接表，所不同的是：以同一頂點(diǎn)為起點(diǎn)的弧：用線性鏈表存儲(chǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)D.verticesV1n12307.2圖的存儲(chǔ)結(jié)構(gòu)2）有向圖的逆鄰接表頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）以同一頂點(diǎn)為終點(diǎn)的?。河镁€性鏈表存儲(chǔ)表類似于無向圖的鄰接表，所不同的是：以同一頂點(diǎn)為終點(diǎn)的?。河镁€性鏈表存儲(chǔ)D.verticesD.vexnumD.arcnuD.kind

V1V2V3V4neDG0023

V1

V2

V3

V47.2圖的存儲(chǔ)結(jié)構(gòu)2）有向圖的逆鄰接表類似于無向圖的鄰接7.2圖的存儲(chǔ)結(jié)構(gòu)

在不同的存儲(chǔ)結(jié)構(gòu)下，實(shí)現(xiàn)各種操作的效率可能是不同的。所以在求解實(shí)際問題時(shí)，要根據(jù)求解問題所需操作，選擇合適的存儲(chǔ)結(jié)構(gòu)。7.2圖的存儲(chǔ)結(jié)構(gòu)在不同的存儲(chǔ)結(jié)構(gòu)下，實(shí)第七章圖7.3圖的遍歷一深度優(yōu)先遍歷二廣度優(yōu)先遍歷

第七章圖7.3圖的遍歷7.3圖的遍歷

圖的遍歷：從圖的某頂點(diǎn)出發(fā)，訪問圖中所有頂點(diǎn)，并且每個(gè)頂點(diǎn)僅訪問一次。圖中可能有回路，遍歷可能沿回路又回到已遍歷過的結(jié)點(diǎn)。為避免同一頂點(diǎn)被多次訪問，必須為每個(gè)被訪問的頂點(diǎn)作一標(biāo)志。為此引入一輔助數(shù)組，記錄每個(gè)頂點(diǎn)是否被訪問過。

有兩種遍歷方法（它們對(duì)無向圖，有向圖都適用）：深度優(yōu)先遍歷廣度優(yōu)先遍歷7.3圖的遍歷圖的遍歷：從圖的某7.3圖的遍歷一深度優(yōu)先遍歷從圖中某頂點(diǎn)v出發(fā)：1）訪問頂點(diǎn)v；

2）從v的未被訪問的鄰接點(diǎn)出發(fā)，繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先遍歷；例

圖G中，以V1起點(diǎn)的的深度優(yōu)先序列：（1）V1,V2,V4,V5,V8,V3,V6,V7,（2）V1,V2,V5,V8,V4,V3,V6,V7

V8

V7

V6

V5

V4

V3

V2

V1由于沒為有規(guī)定訪問鄰接點(diǎn)的順序，深度優(yōu)先序列不是唯一的這是序列（1）在遍歷過程中所經(jīng)過的路徑注：為簡單起見，只討論非空連通圖的遍歷7.3圖的遍歷一深度優(yōu)先遍歷例圖G中，以V1起點(diǎn)的7.3圖的遍歷深度優(yōu)先遍歷(設(shè)圖為非空連通圖）從圖中某頂點(diǎn)v出發(fā)：1）訪問頂點(diǎn)v；

2）從v的未被訪問的鄰接點(diǎn)出發(fā)，繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先遍歷；

先序遍歷（DLR）

若二叉樹非空

（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；

（3）先序遍歷右子樹；如果將圖頂點(diǎn)的鄰接點(diǎn)看作二叉樹結(jié)點(diǎn)的左、右孩子深度優(yōu)先遍歷與先序遍歷是不是很類似？

V8

V7

V6

V5

V4

V3

V2

V17.3圖的遍歷深度優(yōu)先遍歷(設(shè)圖為非空連通圖）先序遍歷7.3圖的遍歷深度優(yōu)先遍歷算法voidDFS(GraphG,intv,Status(*Visit(intv)){//從第v個(gè)頂點(diǎn)出發(fā)，遞歸地深度優(yōu)先遍歷圖G。//v是頂點(diǎn)在一維數(shù)組中的位置，假設(shè)G是非空?qǐng)Dvisited[v]=TRUE;Visit(v);//訪問第v個(gè)頂點(diǎn)for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//對(duì)v的尚未訪問的鄰接頂點(diǎn)w遞歸調(diào)用DFSBooleanvisited[MAX_VERTEX_NUM]//訪問標(biāo)志數(shù)組,全局變量，初始值：所有分量全為False(0)//visited[v]=TRUE表示頂點(diǎn)v已被訪問visited01234m-1000007.3圖的遍歷深度優(yōu)先遍歷算法Booleanvisit7.3圖的遍歷先序遍歷遞歸算法

voidPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//本算法先序遍歷以T為根結(jié)點(diǎn)指針的二叉樹。

if(T){//若二叉樹為空，結(jié)束返回

Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//PreOrderTraverse如果將圖頂點(diǎn)的鄰接點(diǎn)看作二叉樹結(jié)點(diǎn)的左、右孩子深度優(yōu)先遍歷算法與先序遍歷算法的結(jié)構(gòu)是不是很像？深度優(yōu)先遍歷算法voidDFS(GraphG,intv,Status(*Visit(intv)){//從第v個(gè)頂點(diǎn)出發(fā)，遞歸地深度優(yōu)先遍歷圖G。//v是頂點(diǎn)在一維數(shù)組中的位置，假設(shè)G是非空?qǐng)Dvisited[v]=TRUE;Visit(v);//訪問第v個(gè)頂點(diǎn)for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//對(duì)v的尚未訪問的鄰接頂點(diǎn)w遞歸調(diào)用DFS7.3圖的遍歷先序遍歷遞歸算法

voidPreOr7.3圖的遍歷廣度優(yōu)先遍歷（類似于樹的按層遍歷）

從圖中某頂點(diǎn)v出發(fā)：1）訪問頂點(diǎn)v；2）訪問v的所有未被訪問的鄰接點(diǎn)w1,w2,

…wk；3）依次從這些鄰接點(diǎn)出發(fā)，訪問它們的所有未被訪問的鄰接點(diǎn);依此類推，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問；例

圖G中，以V1起點(diǎn)的的廣度優(yōu)先序列：（1）V1,V2,V3,V4,V5,V6,V7,V8（2）V1,V3,V2,V6,V7,V4,V5,V8

V8

V7

V6

V5

V4

V3

V2

V1這是序列（1）在遍歷過程中所經(jīng)過的路徑由于沒為有規(guī)定訪問鄰接點(diǎn)的順序，廣度優(yōu)先序列不是唯一的7.3圖的遍歷廣度優(yōu)先遍歷（類似于樹的按層遍歷）V87.3圖的遍歷廣義優(yōu)先遍歷算法從圖中某頂點(diǎn)v出發(fā)：1）訪問頂點(diǎn)v；（容易實(shí)現(xiàn)）2）訪問v的所有未被訪問的鄰接點(diǎn)w1,w2,

…wk；（容易實(shí)現(xiàn)）3）依次從這些鄰接點(diǎn)（在步驟2）訪問的頂點(diǎn)）出發(fā)，訪問它們的所有未被訪問的鄰接點(diǎn);依此類推，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問；為實(shí)現(xiàn)3），需要保存在步驟(2）中訪問的頂點(diǎn)，而且訪問這些頂點(diǎn)鄰接點(diǎn)的順序?yàn)椋合缺４娴捻旤c(diǎn)，其鄰接點(diǎn)先被訪問。在廣度優(yōu)先遍歷算法中，需設(shè)置一隊(duì)列Q，保存已訪問的頂點(diǎn)，并控制遍歷頂點(diǎn)的順序。7.3圖的遍歷廣義優(yōu)先遍歷算法在廣度優(yōu)先遍歷算法中，需設(shè)7.3圖的遍歷voidBFSTraverse(GraphG,intv,Status(*Visit)(intv)){//從v出發(fā)，廣度優(yōu)先遍歷連通圖G。v是頂點(diǎn)在一維數(shù)組中的位置，使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visited。for(u=0;u<G.vexnum;++u)visited[u]=FALSE;InitQueue(Q);//建空的輔助隊(duì)列QVisited[v]=TRUE;Visit(v)，EnQueue(Q,v)//訪問v,v入隊(duì)While(!QueueEmpty(Q)){DeQueue(Q,u);//隊(duì)頭元素出隊(duì),并賦值給u//訪問u所有未被訪問的鄰接點(diǎn)for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!visited[w]){//若w尚未訪問Visited[w]=TRUE;Visit(w);EnQueue(Q,w);}//if}//while}//BFSTraverse7.3圖的遍歷voidBFSTraverse(Grap7.3圖的遍歷非連通圖的遍歷上面介紹了連通圖的深度優(yōu)先遍歷算法，對(duì)非連通圖,可從每個(gè)連通分量選一起點(diǎn)，調(diào)用遍歷算法（如DFS）完成各連通分量的深度先遍歷。例圖G的深度優(yōu)先序列：V1,V2,V3,V4,V5,V6,廣度優(yōu)先序列V1,V2,V3,V4,V5,V6,

V3

V1

V2

V4

V5

V6

V3

V1

V2

V4

V5

V6深度優(yōu)先遍歷所經(jīng)過的路徑廣度優(yōu)先遍歷所經(jīng)過的路徑7.3圖的遍歷非連通圖的遍歷V3V1V2V4V7.4.1圖的連通性問題--

無向圖的連通分量和生成樹

生成樹定義：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖叫~深度優(yōu)先生成樹與廣度優(yōu)先生成樹生成森林：非連通圖每個(gè)連通分量的生成樹一起組成非連通圖的~7.4圖的連通性7.4圖的連通性7.4.1圖的連通性問題--

無向圖的連通分量和生成樹說明一個(gè)圖可以有許多棵不同的生成樹所有生成樹具有以下共同特點(diǎn)：生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同生成樹是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹中再加一條邊必然形成回路含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹GHKI7.4.1圖的連通性問題--無向圖的連通分量和生成樹GHV1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例深度遍歷：V1V2例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)voidDFSTree(GraphG,intv,CSTree*T){/*從第v個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，建立以*T為根的生成樹*/visited[v]=TRUE;first=TRUE;for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w]){p=(CSTree)malloc(sizeof)CSNode));/*分配孩子結(jié)點(diǎn)*/*p={GetVex(G,w),NULL,NULL};if(first)/*w是v的第一個(gè)未被訪問的鄰接頂點(diǎn)，作為根的左孩子結(jié)點(diǎn)*/{T->lchild=p;first=FALSE;}else{/*w是v的其它未被訪問的鄰接頂點(diǎn)，作為上一鄰接頂點(diǎn)的右兄弟*/q->nextsibling=p;}q=p;DFSTree(G,w,&q);/*從第w個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，建立生成子樹*q*/}}voidDFSTree(GraphG,intv,C7.4圖的連通性7.4.3最小生成樹n個(gè)城市之間,最多可能設(shè)置n(n-1)/2條線路,而連通n個(gè)城市只需要n-1條線路.

最小(代價(jià))生成樹的定義.

一棵生成樹的代價(jià).7.4圖的連通性7.4.3最小生成樹507.4圖的連通性最小生成樹MST的性質(zhì):

假設(shè)N=(V,{E})是一個(gè)連通網(wǎng),U是頂點(diǎn)集V的一個(gè)非空子集.若(u,v)是一條具有最小權(quán)值(代價(jià))的邊,其中u屬于U,v屬于V-U,則必存在一棵包含邊(u,v)的最小生成樹.7.4圖的連通性最小生成樹MST的性質(zhì):517.4圖的連通性算法一：（普里姆算法）

假設(shè)N=(V,{E})是連通網(wǎng),TE是N上最小生成樹中邊的集合.算法從U={u0}(u0屬于V),TE={}開始,重復(fù)執(zhí)行下述操作:

在所有u屬于U,v屬于V-U的邊(u,v)屬于E中找一條代價(jià)最小的邊(u0,v0)并入集合TE,同時(shí)v0并入U(xiǎn),直至U=V為止.

此時(shí)TE中必有n-1條邊,則T=(V,{TE})為N的最小生成樹.7.4圖的連通性算法一：（普里姆算法）52

為實(shí)現(xiàn)這個(gè)算法需要附設(shè)一個(gè)輔助數(shù)組closedge,以記錄從U到V-U具有最小代價(jià)的邊.

對(duì)每個(gè)頂點(diǎn)vi屬于V-U,在輔助數(shù)組中存在一個(gè)相應(yīng)分量closedge[i-1],它包括兩個(gè)域,

其中l(wèi)owcost存儲(chǔ)該邊上的權(quán).顯然:closedge[i-1].lowcost=Min{cost(u,vi)|u屬于U}

vex域存儲(chǔ)該邊依附的在U中的頂點(diǎn).7.4圖的連通性為實(shí)現(xiàn)這個(gè)算法需要附設(shè)一個(gè)輔助數(shù)組closed53普里姆算法構(gòu)造最小生成樹的過程v2v4v6v3v1v5v1v4v6v5v2v3651534626(a)1425357.4圖的連通性普里姆算法構(gòu)造最小生成樹的過程v2v4v6v3v1v5v1v54普里姆算法voidMiniSpanTree_PRIM（MGraphG，VertexTypeu）{//用普里姆算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T，

//輸出T的各條邊。

//記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義：struct{VertexTypeadjvex；VRTypelowcost；}closedge[MAX_VERTEX_NUM];7.4圖的連通性普里姆算法7.4圖的連通性55k=LocateVex（G，u）；for（j=0；j<G.vexnum；++j）//輔助數(shù)組初始化

if（j！=k）closedge[j]={u，G.arcs[k][j].adj}；//{adjvex，lowcost}closedge[k].lowcost=0；//初始，U={u}for（i=1；i<G.vexnum；++i）{//選擇其余G.vexnum-1個(gè)頂點(diǎn)

k=minimum（closedge）；//求出T的下一個(gè)結(jié)點(diǎn)：第k頂點(diǎn)

//此時(shí)closedge[k].lowcost=

//MIN{closedge[vi].lowcost|closedge[vi].lowcost>0，vi∈V-U}printf（closedge[k].adjvex，G.vexs[k]）；//輸出生成樹的邊

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

for（j=0；j<G.vexnum；++j）

if（G.arcs[k][j].adj<closedge[j].lowcost）

//新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊

closedge[j]={G.vexs[k]，G.arcs[k][j].adj}；}}//MiniSpanTree7.4圖的連通性k=LocateVex（G，u）；7.4圖的連通性56算法二：（克魯斯卡爾算法）

為使生成樹上邊的權(quán)值之和最小，顯然，其中每一條邊的權(quán)值應(yīng)該盡可能地小?？唆斔箍査惴ǖ淖龇ň褪牵合葮?gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。7.4圖的連通性算法二：（克魯斯卡爾算法）7.4圖的連通性57克魯斯卡爾算法構(gòu)造最小生成樹的過程v2v4v6v3v1v5v1v4v6v5v2v3651534626(a)1425357.4圖的連通性克魯斯卡爾算法構(gòu)造最小生成樹的過程v2v4v6v3v1v5v58一般來講，由于普里姆算法的時(shí)間復(fù)雜度為O(n2)，則適于稠密圖；而克魯斯卡爾算法需對(duì)e條邊按權(quán)值進(jìn)行排序，其時(shí)間復(fù)雜度為O(eloge)，則適于稀疏圖。7.4圖的連通性一般來講，7.4圖的連通性597.4圖的連通性

“最小生成樹”主要是針對(duì)“無向圖”而言的，請(qǐng)思考它主要能解決哪些實(shí)際生活中遇到的問題？7.4圖的連通性“最小生成樹”主要是針對(duì)“無向圖607.6最短路徑

7.6.1從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑問題提出用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)——表示城市邊——表示城市間的交通聯(lián)系權(quán)——表示此線路的長度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑

7.6最短路徑

7.6.1從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路7.6最短路徑

7.6.1從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑給定帶權(quán)有向圖G和源點(diǎn)v,求從v到G中其余各頂點(diǎn)的最短路徑例:求v0到其余頂點(diǎn)的最短路徑V1V5V2V4V0V35501001060201030始點(diǎn)終點(diǎn)最短路徑路徑長度

v0v1

無

v2(v0,v2)10v3(v0,v4,v3)50v4(v0,v4)30v5(v0,v4,v3,v5)607.6最短路徑

7.6.1從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路

迪杰斯特拉(Dijkstra)算法(1)設(shè)置兩個(gè)頂點(diǎn)的集合T和S;集合S存放已找到最短路徑的頂點(diǎn)集合T存放當(dāng)前還未找到最短路徑的頂點(diǎn)(2)初始狀態(tài)時(shí),S只包含源點(diǎn)v0;(3)從T中選取某個(gè)頂點(diǎn)vi(要求vi到v0的路徑長度最短)加入到S中,;(4)S中每加入一個(gè)頂點(diǎn)vi,都要修改頂點(diǎn)v0到T中剩余頂點(diǎn)的最短路徑長度值;它們的值為原來值與新值的較小者;新值是vi的最短路徑長度值加上vi到該頂點(diǎn)的路徑長度(5)不斷重復(fù)(3)和(4),直到S包含全部頂點(diǎn);

迪杰斯特拉(Dijkstra)算法(1)設(shè)置兩個(gè)頂點(diǎn)的集合V1V5V2V4V0V35501001060201030迪杰斯特拉(Dijkstra)算法舉例帶權(quán)鄰接矩陣為:1030100550102060V1V5V2V4V0V35501001060201030迪杰最短路徑的求解過程終點(diǎn)v1v2v3v4v5vi步驟11030100v2(v0,v2)(v0,v4)(v0,v5)步驟2

6030100v4(v0,v2,v3)(v0,v4)(v0,v5)步驟35090v3(v0,v4,v3)(v0,v4,v5)步驟4

60v5(v0,v4,v3,v5)步驟5

無最短路徑的求解過程終點(diǎn)v1v7.6最短路徑

7.6.2每一對(duì)頂點(diǎn)間的最短路徑給定帶權(quán)有向圖G,求G中每個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑例:求有向網(wǎng)G的每一對(duì)頂點(diǎn)的最短路徑V0V2V1624113有向網(wǎng)G041160230鄰接矩陣7.6最短路徑

7.6.2每一對(duì)頂點(diǎn)間的最短路徑給定帶權(quán)Floyd算法(1)遞推產(chǎn)生一個(gè)矩陣序列A0,A1,...,Ak,...An其中Ak[i,j]表示從頂點(diǎn)vi到vj的路徑上所經(jīng)過的頂點(diǎn)序號(hào)不大于k的最短路徑長度(2)初始時(shí),A0為鄰接矩陣.(3)Ak+1[i,j]=min{Ak[i,j],Ak[i,k+1]+Ak[k+1,j]}(0<=k<=n-1)041160230A0=04650237

0A2=04660230A1=Floyd算法(1)遞推產(chǎn)生一個(gè)矩陣序列A0,A1,...,例ACB264311041160230初始：路徑：ABACBABCCA046602370加入V2：路徑：ABABCBABCCACAB0411602370加入V1：路徑：ABACBABCCACAB046502370加入V3：路徑：ABABCBCABCCACAB例ACB2643110411初始：路徑：AB7.5有向無環(huán)圖及其應(yīng)用一個(gè)無環(huán)的有向圖叫做有向無環(huán)圖簡稱DAG圖有向樹DAG圖有向圖7.5有向無環(huán)圖及其應(yīng)用一個(gè)無環(huán)的有向圖叫做有向無環(huán)圖簡稱有向無環(huán)圖是

--------描述含有公共子式的表達(dá)式的有效工具.((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)*****+++++abbcccddd用二叉樹描述表達(dá)式ee****+++abbcd用DAG描述表達(dá)式e有向無環(huán)圖是

--------描述含有公共子式的表達(dá)式的有效有向無環(huán)圖也是---------

描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過程的有效工具C12C10C11C9C1C2C3C4C6C5C7C8有向無環(huán)圖也是---------

描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過7.5.1拓?fù)渑判?/p>

AOV-網(wǎng)(ActivityOnVertex)頂點(diǎn)－－活動(dòng)?。顒?dòng)間的優(yōu)先關(guān)系A(chǔ)OV－網(wǎng)不應(yīng)該出現(xiàn)有向環(huán)上例的拓?fù)渑判蛐蛄兄唬篊1,C9,C2,C4,C10,C11,C3,C12,C6,C5,C7,C87.5.1拓?fù)渑判?/p>

AOV-網(wǎng)(ActivityOnV7.5.2關(guān)鍵路徑

AOE-網(wǎng)(ActivityOnEdge)AOE－網(wǎng)是帶權(quán)的有向無環(huán)網(wǎng)頂點(diǎn)－－事件或狀態(tài)?。顒?dòng)及發(fā)生的依次關(guān)系權(quán)－－活動(dòng)持續(xù)的時(shí)間源點(diǎn)－－入度為０的頂點(diǎn)（只有一個(gè)）匯點(diǎn)－－出度為０的頂點(diǎn)（只有一個(gè)）V4V1V3V8V2V7V9V6V5a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=47.5.2關(guān)鍵路徑

AOE-網(wǎng)(ActivityOnAOE-網(wǎng)要研究的問題完成整項(xiàng)工程至少需要多少時(shí)間？哪些活動(dòng)是影響整個(gè)工程進(jìn)度的關(guān)鍵？關(guān)鍵路徑：路徑長度最長的路徑（從源點(diǎn)到匯點(diǎn)）e(i)表示活動(dòng)ai的最早開始時(shí)間l(i)表示活動(dòng)ai的最遲開始時(shí)間(不推遲整個(gè)工期)

e(i)=l(i)的活動(dòng)叫做關(guān)鍵活動(dòng),關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng).ve(j)表示事件vj的最早發(fā)生時(shí)間vl(j)表示事件vj的最遲發(fā)生時(shí)間(不推遲整個(gè)工期)AOE-網(wǎng)要研究的問題完成整項(xiàng)工程至少需要多少時(shí)間？e(i)e(i),l(i),ve(j),vl(j)的關(guān)系若活動(dòng)ai由弧<j,k>表示,其持續(xù)的時(shí)間記為dut(<j,k>),則

e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)VjVkai求ve(j)和vl(j)分兩步進(jìn)行:(1)從ve(0)=0開始向前遞推:ve(j)=max{ve(i)+dut(<i,j>)}

iViVjaiViVjai(2)vl(n-1)=ve(n-1)開始向后遞推:

vl(i)=min{vl(j)-dut(<i,j>)}

je(i),l(i),ve(j),vl(j)的關(guān)系若活動(dòng)a求AOE網(wǎng)的關(guān)鍵路徑舉例V4V1V3V8V2V7V9V6V5a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4求AOE網(wǎng)的關(guān)鍵路徑舉例V4V1V3V8V2V7V9V6V5V1V8V2V7V9V5a1=6a4=1a7=9a8=7a10=2a11=4整個(gè)工期為18關(guān)鍵路徑有兩條:(V1,V2,V5,V7,V9),(V1,V2,V5,V8,V9)關(guān)鍵活動(dòng)有六個(gè):a1,a4,a7,a8,a10,a11V1V8V2V7V9V5a1=6a4=1a7=9a8=7a1第七章圖第七章圖

第七章圖7.1圖的定義和術(shù)語7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖及應(yīng)用7.6最短路徑第七章圖第七章圖本章介紹另一種非線性數(shù)據(jù)結(jié)構(gòu)——圖圖：是一種多對(duì)多的結(jié)構(gòu)關(guān)系，每個(gè)元素可以有零個(gè)或多個(gè)直接前趨；零個(gè)或多個(gè)直接后繼；第七章圖本章介紹另一種非線性數(shù)據(jù)結(jié)構(gòu)——圖第七章圖

學(xué)習(xí)要點(diǎn)1．熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解實(shí)際問題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系；2．熟練掌握?qǐng)D的兩種遍歷：深度優(yōu)先遍歷和廣度優(yōu)先遍歷的算法。在學(xué)習(xí)中應(yīng)注意圖的遍歷算法與樹的遍歷算法之間的類似和差異。樹的先根遍歷是一種深度優(yōu)先搜索策略，樹的層次遍歷是一種廣度優(yōu)先搜索策略3．理解課件中討論的各種圖的算法；

第七章圖

學(xué)習(xí)要點(diǎn)7.1圖的定義和術(shù)語一圖的概念

圖G由兩個(gè)集合構(gòu)成，記作G=<V,E>其中V是頂點(diǎn)的非空有限集合，E是邊的有限集合，其中邊是頂點(diǎn)的無序?qū)蛴行驅(qū)稀＠鼼1=<V1,E1>V1={v1,v2,v3,v4,v5}E1={(v1,v2),(v1,v3),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}G1圖示無序?qū)?vi,vj)：用表示頂點(diǎn)vi、vj的線段，稱為無向邊；

V5V1

V2

V4

V37.1圖的定義和術(shù)語一圖的概念例G1=<V1,E17.1圖的定義和術(shù)語例G2=<V2,E2>V2={v1,v2,v3,v4}E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}G2圖示有序?qū)?lt;vi,vj>：用以表示以vi起點(diǎn)、以vj為終點(diǎn)的有向線段，稱為有向邊或??；無向圖：在圖G中，若所有邊是無向邊，則稱G為無向圖；有向圖：在圖G中，若所有邊是有向邊，則稱G為有向圖；混和圖：在圖G中，即有無向邊也有有向邊，則稱G為混合圖；

V1

V2

V3

V4V1稱為弧尾(初始點(diǎn))V3稱為弧頭(終端點(diǎn))7.1圖的定義和術(shù)語例G2=<V2,E2>G2圖示有序7.1圖的定義和術(shù)語圖的應(yīng)用舉例例1交通圖（公路、鐵路）頂點(diǎn)：地點(diǎn)邊：連接地點(diǎn)的公路交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；例2電路圖頂點(diǎn)：元件邊：連接元件之間的線路例3通訊線路圖頂點(diǎn)：地點(diǎn)邊：地點(diǎn)間的連線例4各種流程圖如產(chǎn)品的生產(chǎn)流程圖頂點(diǎn)：工序邊：各道工序之間的順序關(guān)系

V5V1

V2

V4

V37.1圖的定義和術(shù)語圖的應(yīng)用舉例V5V1V2V47.1圖的定義和術(shù)語三圖的基本操作1CreateGraph(&G,V,VR);初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合操作結(jié)果：按V和VR的定義構(gòu)造圖G2DestroyGraph(&G);初始條件：圖G存在操作結(jié)果：銷毀圖G3LocateVex(G,u);初始條件：圖G存在，u和G中頂點(diǎn)有相同特征操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回其它信息。4GetVex(G,v);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)操作結(jié)果：返回v的值5PutVex(&G,v,value);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)操作結(jié)果：對(duì)v賦值value7.1圖的定義和術(shù)語三圖的基本操作7.1圖的定義和術(shù)語6FirstAdjVex(G,v);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)操作結(jié)果：返回v的第一個(gè)鄰接頂點(diǎn)。若頂點(diǎn)在G中沒有鄰接頂點(diǎn)，則返回“空”。7NextAdjVex(G,v,w);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)。操作結(jié)果：返回v的（相對(duì)于w的）下一個(gè)鄰接頂點(diǎn)。若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”。8InsertVex(&G,v);初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征。操作結(jié)果：在圖G中增添新頂點(diǎn)v9DeleteVex(&G,v);初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征操作結(jié)果：刪除G中頂點(diǎn)v及相關(guān)的弧7.1圖的定義和術(shù)語6FirstAdjVex(G,v7.1圖的定義和術(shù)語10InsertArc(&G,v,w);初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中增添弧<v,w>，若G是無向的，則還增添對(duì)稱弧<w,v>11DeleteArc(&G,v,w);初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中刪除弧<v,w>，若G是無向的，則還刪除對(duì)稱弧<w,v>12DFSTraverse(G,v,Visit());初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：從頂點(diǎn)v起深度優(yōu)先遍歷圖G，對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗13BFSTraverse(G,v,Visit());初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且一次。一旦visit()失敗，則操作失敗7.1圖的定義和術(shù)語10InsertArc(&G,v7.1圖的定義和術(shù)語圖的基本術(shù)語1鄰接點(diǎn)及關(guān)聯(lián)邊

鄰接點(diǎn)：邊的兩個(gè)頂點(diǎn)

關(guān)聯(lián)邊：若邊e=(v,u),則稱頂點(diǎn)v、u關(guān)聯(lián)邊e（邊e依附于頂點(diǎn)v,u)2頂點(diǎn)的度、入度、出度

頂點(diǎn)V的度=與V相關(guān)聯(lián)的邊的數(shù)目在有向圖中：頂點(diǎn)V的出度=以V為起點(diǎn)有向邊數(shù)

頂點(diǎn)V的入度=以V為終點(diǎn)有向邊數(shù)頂點(diǎn)V的度=V的出度+V的入度設(shè)圖G的頂點(diǎn)數(shù)為n，邊數(shù)為e

圖的所有頂點(diǎn)的度數(shù)和=2*e（每條邊對(duì)圖的所有頂點(diǎn)的度數(shù)和“貢獻(xiàn)”2度）

e1

V1

V2

V3

V4

V5V1

V2

V4

V37.1圖的定義和術(shù)語圖的基本術(shù)語e1V1V2V33有向完全圖、無向完全圖有向完全圖——n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)無向完全圖——n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是n(n-1)/2權(quán)(weight)——與圖的邊或弧相關(guān)的數(shù)叫~網(wǎng)——帶權(quán)的圖叫~7.1圖的定義和術(shù)語3有向完全圖、無向完全圖7.1圖的定義和術(shù)語7.1圖的定義和術(shù)語

路徑、回路

無向圖中的頂點(diǎn)序列v1,v2,…,vk,若(vi,vi+1)E(i=1,2,…k-1),v=v1,u=vk,

則稱該序列是從頂點(diǎn)v到頂點(diǎn)u的路徑；若v=u，則稱該序列為回路；

有向圖D=(V，E）中的頂點(diǎn)序列v1,v2,…,vk,若<vi,vi+1>E(i=1,2,…k-1),v=v1,u=vk,則稱該序列是從頂點(diǎn)v到頂點(diǎn)u的路徑；若v=u，則稱該序列為回路；

例在圖1中，V1,V2,V3,V4是V1到V4的路徑；V1,V2,V3,V4,V1是回路；在圖2中，V1,V3,V4是V1到V4的路徑；V1,V3,V4,V1是回路；

V5V1

V2

V4

V3

V1

V2

V3

V4圖1圖27.1圖的定義和術(shù)語路徑、回路V5V1V2V47.1圖的定義和術(shù)語連通圖、（強(qiáng)連通圖）

在無（有）向圖G=<V,E>中，若對(duì)任何兩個(gè)頂點(diǎn)v、u都存在從v到u的路徑，則稱G是連通圖（強(qiáng)連通圖）

V5

V6

V3

V1

V2

V4連通圖非連通圖

V5V1

V2

V4

V37.1圖的定義和術(shù)語連通圖、（強(qiáng)連通圖）V5V6V7.1圖的定義和術(shù)語子圖

設(shè)有兩個(gè)圖G=（V，E）、G1=（V1，E1），若V1V，E1E，E1關(guān)聯(lián)的頂點(diǎn)都在V1中，則稱G1是G的子圖；例圖2、圖3是圖1的子圖

V5V1

V2

V4

V3

V5V1

V2

V3

V5V1

V2

V4

V3圖1圖2圖37.1圖的定義和術(shù)語子圖V5V1V2V4V37.1圖的定義和術(shù)語連通分圖（強(qiáng)連通分量）

無向圖G的極大連通子圖稱為G的連通分量極大連通子圖意思是：該子圖是G連通子圖，將G的任何不在該子圖中的頂點(diǎn)加入，子圖不再連通；有向圖D的極大強(qiáng)連通子圖稱為D的強(qiáng)連通分量極大強(qiáng)連通子圖意思是：該子圖是D強(qiáng)連通子圖，將D的任何不在該子圖中的頂點(diǎn)加入，子圖不再是強(qiáng)連通的；

V5

V6

V3

V1

V2

V4連通分圖7.1圖的定義和術(shù)語連通分圖（強(qiáng)連通分量）V5V67.1圖的定義和術(shù)語

V5V1

V2

V4

V3

V5V1

V2

V4

V38生成樹（

包含無向圖G所有頂點(diǎn)的的極小連通子圖稱為G生成樹極小連通子圖意思是：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通，若T是G的生成樹當(dāng)且僅當(dāng)T滿足如下條件T是G的連通子圖T包含G的所有頂點(diǎn)T中無回路只有足以構(gòu)成一棵樹的n-1條邊7.1圖的定義和術(shù)語V5V1V2V4V3V5例213213有向完全圖無向完全圖356例245136圖與子圖例245136G1頂點(diǎn)2入度：1出度：3頂點(diǎn)4入度：1出度：0例157324G26頂點(diǎn)5的度：3頂點(diǎn)2的度：4例213213有向完全圖無向完全圖356例245136圖與子例157324G26例245136G1路徑：1，2，3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡單回路：1，2，3，1例157324G26例245136G1路徑：1，2，3，5，連通圖例245136強(qiáng)連通圖356例非連通圖連通分量例245136連通圖例245136強(qiáng)連通圖356例非連通圖連通分量例245第七章圖7.2圖的存儲(chǔ)結(jié)構(gòu)數(shù)組表示法鄰接表第七章圖7.2圖的存儲(chǔ)結(jié)構(gòu)7.2圖的存儲(chǔ)結(jié)構(gòu)

圖是多對(duì)多的結(jié)構(gòu)，比線性結(jié)構(gòu)、樹結(jié)構(gòu)復(fù)雜，所以其存儲(chǔ)結(jié)構(gòu)也要復(fù)雜些。與線性結(jié)構(gòu)、樹結(jié)構(gòu)一樣，圖的存儲(chǔ)結(jié)構(gòu)至少要保存兩類信息： 1)頂點(diǎn)的數(shù)據(jù)2) 頂點(diǎn)間的關(guān)系頂點(diǎn)的編號(hào)

為了使圖的存儲(chǔ)結(jié)構(gòu)與圖一一對(duì)應(yīng)，在討論圖的存儲(chǔ)結(jié)構(gòu)時(shí)，首先要給圖的所有頂點(diǎn)編號(hào)。

本課程介紹兩類圖的存儲(chǔ)結(jié)構(gòu)

數(shù)組表示法 鄰接表（鄰接表，逆鄰接表）

設(shè)G=<V,E>是圖,V={v1,v2,v3,…

vn},設(shè)頂點(diǎn)的的角標(biāo)為它的編號(hào)如何表示頂點(diǎn)間的關(guān)系？？7.2圖的存儲(chǔ)結(jié)構(gòu)圖是多對(duì)多的結(jié)構(gòu)，比線7.2圖的存儲(chǔ)結(jié)構(gòu)

鄰接矩陣：G的鄰接矩陣是滿足如下條件的n階矩陣：

一數(shù)組表示法數(shù)組表示法是圖的一種順序存儲(chǔ)結(jié)構(gòu)在數(shù)組表示法中，用鄰接矩陣表示頂點(diǎn)間的關(guān)系A(chǔ)[i][j]=1若(vi,vi+1)E或<vi,vi+1>E0否則

V5V1

V2

V4

V30101