工學山東科技大學數(shù)據(jù)結構課圖

會計學1工學山東科技大學數(shù)據(jù)結構課圖主要內(nèi)容7.1圖的定義和術語

7.2圖的基本操作

7.3圖的存儲結構

7.4圖的遍歷

7.5生成樹和最小生成樹第1頁/共119頁7.1圖的定義和術語一圖的定義圖G由兩個集合構成，記作G=<V,E>其中V是頂點的非空有限集合，E是邊的有限集合，其中邊是頂點的無序對或有序對集合。G1=<V1,E1>V1={v0,v1,v2,v3,v4}E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}無序對(vi,vj)：用連接頂點vi、vj的線段表示，稱為無向邊；

V0

V4

V3

V1

V2例G1圖示第2頁/共119頁7.1圖的定義和術語G2圖示有序對<vi,vj>：用以為vi起點、以vj為終點的有向線段表示，稱為有向邊或?。?/p>

V0

V1

V2

V3G2=<V2,E2>V2={v0v1,v2,v3}E2={<v0,v1>

,<v0,v2>,<v2,v3>,<v3,v0>}第3頁/共119頁圖的應用舉例：例1交通圖（公路、鐵路）頂點：地點邊：連接地點的公路交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；例2電路圖頂點：元件邊：連接元件之間的線路例3通訊線路圖頂點：地點邊：地點間的連線例4各種流程圖如產(chǎn)品的生產(chǎn)流程圖頂點：工序邊：各道工序之間的順序關系

V0

V4

V3

V1

V2

V0

V1

V2

V37.1圖的定義和術語第4頁/共119頁二圖的基本術語

V0

V4

V3

V1

V2

V0

V1

V2

V37.1圖的定義和術語1)無向圖（undigraph）：在圖G中，若所有邊是無向邊，則稱G為無向圖；2)有向圖（digraph）：在圖G中，若所有邊是有向邊，則稱G為有向圖；混和圖：在圖G中，即有無向邊也有有向邊，則稱G為混合圖；3)無向完全圖：任意兩頂點間都有邊的圖稱為無向完全圖。在一個含有n個頂點的無向完全圖中，有n(n-1)/2條邊。4）有向完全圖：任意兩頂點之間都有方向互為相反的兩條弧相連接的有向圖稱為有向完全圖。在一個含有n個頂點的有向完全圖中，有n(n-1)條弧。5）稠密圖/稀疏圖：若邊數(shù)為e，頂點數(shù)為n，邊數(shù)稀少到e<nlogn，則稱該圖為稀疏圖，否則該圖為稠密圖。第5頁/共119頁6）頂點的度、入度、出度鄰接點：邊的兩個頂點關聯(lián)邊：若邊e=(v,u),則稱頂點v、u關聯(lián)邊在無向圖中：頂點V的度=與V相關聯(lián)的邊的數(shù)目，記作TD(V)

在有向圖中：頂點V的出度=以V為起點有向邊數(shù)，記作OD(V)

頂點V的入度=以V為終點有向邊數(shù)，記作ID(V)

頂點V的度=V的出度+V的入度設圖G的頂點數(shù)為n，邊數(shù)為e

7.1圖的定義和術語

V0

V4

V3

V1

V2

V0

V1

V2

V3TD(V0)=2TD(V1)=3TD(V2)=3TD(V3)=2TD(V4)=2ID(V0)=1OD(V0)=2TD(V0)=3ID(V1)=1OD(V1)=0TD(V1)=1ID(V2)=1OD(V2)=1TD(V2)=2ID(V3)=1OD(V3)=1TD(V3)=2第6頁/共119頁

7)邊的權：在圖的邊或弧上表示數(shù)字，表示與該邊相關的數(shù)據(jù)信息，這個數(shù)據(jù)信息就稱該邊的權（weight）。8）網(wǎng)（network）：邊（或弧）上帶權的圖稱為網(wǎng)。9）路徑、回路

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

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

在圖1中，V0,V1,V2,V3是V0到V3的路徑；V0,V1,V2,V3,V0是回路；在圖2中，V0,V2,V3是V0到V3的路徑；V0,V2,V3,V0是回路；無向圖G1有向圖G2

V0

V4

V3

V1

V2

V0

V1

V2

V3例7.1圖的定義和術語第7頁/共119頁

10)簡單路徑和簡單回路

在一條路徑中,若除起點和終點外,所有頂點各不相同,則稱該路徑為簡單路徑； 由簡單路徑組成的回路稱為簡單回路；

在圖1中，V0,V1,V2,V3是簡單路徑；V0,V1,V2,V4,V1不是簡單路徑；在圖2中，V0,V2,V3,V0是簡單回路；7.1圖的定義和術語無向圖G1有向圖G2

V0

V4

V3

V1

V2

V0

V1

V2

V3例第8頁/共119頁11）子圖

設有兩個圖G=（V，E）、G1=（V1，E1），若V1V，E1E，E1關聯(lián)的頂點都在V1中，則稱G1是G的子圖；例

(b)、(c)是(a)的子圖(a)(b)(c)

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V27.1圖的定義和術語第9頁/共119頁12）連通圖（強連通圖）在無（有）向圖G=<V,E>中，若對任何兩個頂點v、u都存在從v到u的路徑，則稱G是連通圖（強連通圖）

非連通圖

連通圖

強連通圖

非強連通圖

V0

V1

V2

V3

V0

V4

V3

V1

V2

V0

V1

V2

V3

V0

V2

V3

V1

V5

V47.1圖的定義和術語第10頁/共119頁13）連通分圖（強連通分量）無向圖G的極大連通子圖稱為G的連通分量極大連通子圖意思是：該子圖是G連通子圖，將G的任何不在該子圖中的頂點加入，子圖不再連通；

連通分圖非連通圖

V0

V2

V3

V1

V5

V4

V0

V2

V1非連通分圖7.1圖的定義和術語第11頁/共119頁有向圖D的極大強連通子圖稱為D的強連通分量極大強連通子圖意思是：該子圖是D強連通子圖，將D的任何不在該子圖中的頂點加入，子圖不再是強連通的；強連通分量

V0

V1

V2

V3

V0

V2

V3

V17.1圖的定義和術語第12頁/共119頁14)生成樹包含無向圖G所有頂點的的極小連通子圖稱為G的生成樹極小連通子圖意思是：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通，若T是G的生成樹當且僅當T滿足如下條件

T是G的連通子圖

T包含G的所有頂點

T中無回路連通圖G1G1的生成樹

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V27.1圖的定義和術語第13頁/共119頁生成樹：極小連通子圖，它含有圖中全部全部頂點，但是只有足以構成一棵樹的n-1條邊。一棵有n個頂點的生成樹有且僅有n-1條邊。無法將圖中頂點排列成一個唯一的線性序列，任何一個頂點都可被看成是第一個頂點。任一個頂點的鄰接點之間也不存在次序關系。第14頁/共119頁7.2圖的基本操作圖有以下基本操作：1）CreatGraph（G）：輸入圖G的頂點和邊，建立圖G的存儲。2）DFSTraverse（G,V）：從圖G的一個頂點V出發(fā)深度優(yōu)先遍歷圖G。3）BFSTraverse（G,V）：從圖G的一個頂點V出發(fā)廣度優(yōu)先遍歷圖G。第15頁/共119頁圖的存儲結構至少要保存兩類信息：

1)頂點的數(shù)據(jù)

2)頂點間的關系約定:G=<V,E>是圖,V={v0,v1,v2,…vn-1},設頂點的角標為它的編號

如何表示頂點間的關系？頂點的編號

？

V0

V4

V3

V1

V2

V0

V1

V2

V37.3圖的存儲表示第16頁/共119頁1鄰接矩陣：G的鄰接矩陣是滿足如下條件的n階矩陣：A[i][j]=1若(vi,vi+1)E或<vi,vi+1>E0否則01010010101011010001100011000000001000一鄰接矩陣表示

V0

V4

V3

V1

V2

V0

V1

V2

V37.3圖的存儲表示第17頁/共119頁無向圖鄰接矩陣表示法特點：1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；2）頂點v的度：等于二維數(shù)組對應行（或列）中1的個數(shù)；3）判斷兩頂點v、u是否為鄰接點：只需判二維數(shù)組對應分量是否為1；4）頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對應分量賦值1或清0；5）設圖的頂點數(shù)為n,存儲圖用一維數(shù)組,數(shù)組元素有m個（m>=n),則G占用存儲空間：m+n2；G占用存儲空間只與它的頂點數(shù)有關，與邊數(shù)無關；適用于邊稠密的圖；對有向圖的數(shù)組表示法可做類似的討論

01010010101011010001100鄰接矩陣表示法的空間代價只與圖的頂點數(shù)有關

V0

V4

V3

V1

V27.3圖的存儲表示第18頁/共119頁圖的基本操作：1）求無向圖某頂點vi的度(或有向圖中vi的出度)。A[i][0]到A[i][n-1]中的非0個數(shù)，即數(shù)組A中第i行的非0元素的個數(shù)；2）求有向圖某頂點vi的入度。：A[0][i]到A[n-1][i]中的非0個數(shù)，即數(shù)組A中第i列的非0元素的個數(shù)；3）檢測圖中的總邊數(shù)。掃描整個數(shù)組A，統(tǒng)計出數(shù)組中非0元素的個數(shù)。無向圖的總邊數(shù)為非0元素個數(shù)的一半，而有向圖的總弧數(shù)為非0元素個數(shù)；

V0

V4

V3

V1

V2

V0

V1

V2

V3010100101010110100011000110000000010007.3圖的存儲表示第19頁/共119頁鄰接矩陣表示法對求頂點的度很方便。在無向圖中：頂點的度數(shù)=矩陣中對應該頂點的行或列中非零元素的個數(shù)。在有向圖中：頂點的出度=矩陣中對應該頂點的行中非零元素的個數(shù)。頂點的入度=矩陣中對應該頂點的列中非零元素的個數(shù)。第20頁/共119頁V1V3V2V4V1V3V2V4

V1V2V3V4

V1

0010

V20001

V30001

V41000

V1V2V3V4

V1

0111

V21001

V31000

V41100入度出度11112101度數(shù)3212第21頁/共119頁V1V3V2V4

V1V2V3V4

V1∞

∞2∞

V2∞

∞

∞8

V3

∞

9

∞6

V44∞

∞

∞

2846網(wǎng)及其鄰接矩陣9便于找一個圖中某個頂點的鄰接點序列第22頁/共119頁鄰接表

鄰接表是圖的鏈式存儲結構：即對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于該頂點Vi的邊（或?。?無向圖的鄰接表頂點：通常按編號順序將頂點數(shù)據(jù)存儲在一維數(shù)組中；關聯(lián)同一頂點的邊：用線性鏈表存儲該結點表示邊（ViVj）,其中的1是Vj在一維數(shù)組中的位置例

V0

V4

V3

V1

V22

01234m-1V0V1V2V3V413422110034下標編號link7.3圖的存儲表示第23頁/共119頁圖的鄰接表類型定義structnode//邊（?。┙Y點的類型定義{intvertex;//邊（?。┑牧硪豁旤c的在數(shù)組中的位置

structnode*link;//指向下一條邊（?。┙Y點的指針};typedefstructNODE；NODEadjlist[MAX];//鄰接點鏈表的頭指針所對應的數(shù)組7.3圖的存儲表示第24頁/共119頁無向圖的鄰接表的特點

1）在G鄰接表中，同一條邊對應兩個結點；

2）頂點v的度：等于v對應線性鏈表的長度；

3）判定兩頂點v，u是否鄰接：要看v對應線性鏈表中有無對應的結點

4）在G中增減邊：要在兩個單鏈表插入、刪除結點；

5）設存儲頂點的一維數(shù)組大小為m(m圖的頂點數(shù)n),圖的邊數(shù)為e，G占用存儲空間為：m+2*e。G占用存儲空間與G的頂點數(shù)、邊數(shù)均有關；適用于邊稀疏的圖

01234m-1V0V1V2V3V413422110043鄰接表的空間代價與圖的邊及頂點數(shù)均有關

V0

V4

V3

V1

V227.3圖的存儲表示第25頁/共119頁2有向圖的鄰接表和逆鄰接表1）有向圖的鄰接表頂點：用一維數(shù)組存儲（按編號順序）以同一頂點為起點的弧：用線性鏈表存儲類似于無向圖的鄰接表，所不同的是：以同一頂點為起點的?。河镁€性鏈表存儲下標編號link

V0V1V2V31230

0123m-1例

V0

V1

V2

V37.3圖的存儲表示第26頁/共119頁2）有向圖的逆鄰接表頂點：用一維數(shù)組存儲（按編號順序）以同一頂點為終點的?。河镁€性鏈表存儲V0V1V2V3

0123m-10023

類似于有向圖的鄰接表，所不同的是：以同一頂點為終點?。河镁€性鏈表存儲例

V0

V1

V2

V37.3圖的存儲表示第27頁/共119頁

建立鄰接表的算法建立無向鄰接表

intcreate(NODE*adjlist[]){NODE*p;intnum,i,v1,v2;scanf(“%d\n”,&num);//讀入結點數(shù)

for(i=0;i<num;i++)//初始化空關系圖

{adjlist[i].link=NULL;adjlist[i].vertex=i;}7.3圖的存儲表示第28頁/共119頁for(;;){scanf(“%dto%d\n”,&v1,&v2);//讀入一條邊

if(v1<0||v2<0)break;//數(shù)據(jù)輸入的終止條件

p=(NODE*)malloc(sizeof(NODE));p->vertex=v2;p->link=adjlist[v1].link;adjlist[v1].link=p;//插入在鏈表首部

p=(NODE*)malloc(sizeof(NODE));p->vertex=v1;p->link=adjlist[v2].link;adjlist[v2].link=p;}return(num);//返回圖的結點數(shù)}7.3圖的存儲表示第29頁/共119頁（3）十字鏈表V1V2V3V401v1v2∧v3v4012302∧2023∧∧30∧31∧32∧∧tailvexheadvexhlinktlinkinfodatafirstinfirstout第30頁/共119頁弧頭相同的弧在同一鏈表上，弧尾相同的弧在同一鏈表上。十字鏈表也可以看成是鄰接矩陣的鏈表存儲結構。第31頁/共119頁（4）鄰接多重表V1V3V2V4

1

2

3

4211∧134∧4∧2∧鄰接表第32頁/共119頁V1V2V4V5v1v2v3v4v5342120∧0∧V30123421∧431∧v1v2v3v4v501012340∧3∧212341∧2∧4∧mark頂點位置下一鄰邊第33頁/共119頁鄰接多重表中，所有依附于同一頂點的邊串聯(lián)在同一鏈表中。由于每條邊依附于兩個頂點，則每個邊結點同時鏈接在兩個鏈表中。與鄰接表的區(qū)別：用來表示同一條邊的結點個數(shù)不同。在存儲量問題上，存儲容量大致相同。第34頁/共119頁

在不同的存儲結構下，實現(xiàn)各種操作的效率可能是不同的。所以在求解實際問題時，要根據(jù)求解問題所需操作，選擇合適的存儲結構。7.3圖的存儲表示第35頁/共119頁

圖的遍歷：從圖的某頂點出發(fā)，訪問圖中所有頂點，并且每個頂點僅訪問一次。在圖中，訪問部分頂點后，可能又沿著其他邊回到已被訪問過的頂點。為保證每一個頂點只被訪問一次，必須對頂點進行標記，一般用一個輔助數(shù)組visit[MAX]作為對頂點的標記，當頂點vi未被訪問，visit[i]值為0；當vi已被訪問，則visit[i]值為1。

圖的遍歷與樹的遍歷有什么不同？

有兩種遍歷方法（它們對無向圖，有向圖都適用）深度優(yōu)先遍歷廣度優(yōu)先遍歷7.4圖的遍歷第36頁/共119頁

一、深度優(yōu)先遍歷從圖中某頂點v出發(fā)：1）訪問頂點v；

2）依次從v的未被訪問的鄰接點出發(fā)，繼續(xù)對圖進行深度優(yōu)先遍歷；直至圖中所有和v有路徑相通的頂點都被訪問到；3）若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起始點，重復上述過程。直至圖中所有頂點都被訪問到。

V0,V1,V3,V7,V4,V2,V5,V6,

由于沒有規(guī)定訪問鄰接點的順序，深度優(yōu)先序列不是唯一的這是序列（1）在遍歷過程中所經(jīng)過的路徑例求圖G以V0起點的的深度優(yōu)先序列：V0,V1,V4,V7,V3,V2,V5,V6

V0

V7

V6

V5

V4

V3

V2

V1

V0

V1

V3

V2

V7

V6

V5

V47.4圖的遍歷第37頁/共119頁如果將圖頂點的鄰接點看作二叉樹結點的左、右孩子深度優(yōu)先遍歷與先序遍歷是不是很類似？深度優(yōu)先遍歷從圖中某頂點v出發(fā)：（1）訪問頂點v；

（2）依次從v的未被訪問的鄰接點出發(fā)，對圖進行深度優(yōu)先遍歷；

先序遍歷（DLR）若二叉樹非空

（1）訪問根結點；（2）先序遍歷左子樹；

（3）先序遍歷右子樹；

V0

V7

V6

V5

V4

V3

V2

V17.4圖的遍歷第38頁/共119頁結點定義typedefstructnode{intvertex;//邊（弧）的另一頂點在數(shù)組中的位置

structnode*link;//指向下一條邊（?。┙Y點的指針};typedefstructNODE；NODEadjlist[MAX];//鄰接點鏈表的頭指針所對應的數(shù)組輔助數(shù)組

intvisit[MAX];//頂點標志數(shù)組,全局變量

NODE*ptr[MAX];//頂點鏈表指針數(shù)組visit01234m-100000深度優(yōu)先遍歷算法7.4圖的遍歷第39頁/共119頁voiddepthfirst(NODEadjlist[],intnum){inti;for(i=0;i<num;i++){ptr[i]=adjlist[i].link;//記住每個頂點鏈表的第一個結點的地址

visit[i]=0;//給每個結點一個未訪問標記

}for(i=0;i<num;i++)if(visit[i]==0)dfs(i);//調(diào)用以頂點vi為出發(fā)點的深度優(yōu)先遍歷圖G的算法

}圖G的深度優(yōu)先遍歷算法

V0

V2

V3

V1

V5

V4深度優(yōu)先遍歷7.4圖的遍歷第40頁/共119頁voiddfs(intv){intw;printf(“%d,“,v);visit[v]=1;//訪問此結點

while(ptr[v]！=NULL）

{w=ptr[v]->vertex;取結點的鄰接頂點wif(visit[w]==0;)dfs(w);ptr[v]=ptr[v]->link;//記住頂點v的鄰接頂點位置，

}該鄰接點在w之后

}從第v個頂點出發(fā)，遞歸地深度優(yōu)先遍歷圖G。7.4圖的遍歷第41頁/共119頁調(diào)用深度優(yōu)先遍歷算法的主函數(shù)

main(){NODEadjlist[MAX];intnum;num=create(adjlist);/*建立圖G的鄰接表*/depthfirst(adjlist,num);/*調(diào)用對圖G深度優(yōu)先搜索算法*/}深度優(yōu)先遍歷算法7.4圖的遍歷第42頁/共119頁

V0

V7

V6

V5

V4

V3

V2

V1

01234567V0V1V2V3V4V5V6V71201157730642652437.4圖的遍歷第43頁/共119頁如果將圖頂點的鄰接點看作二叉樹結點的左、右孩子深度優(yōu)先遍歷算法與先序遍歷算法的結構是不是很像？深度優(yōu)先遍歷算法voiddfs(intv){intw;printf(“%d,“,v);visit[v]=1;//訪問此結點

while(ptr[v]！=NULL）

{w=ptr[v]->vertex;取結點的鄰接頂點wif(visit[w]==0;)dfs(w);ptr[v]=ptr[v]->link;//記住頂點v的鄰接點位置，

}該鄰接點在w之后

}

先序遍歷遞歸算法

voidprev(NODE*root)

{if(root!=NULL)

{printf(“%d,”,root->data)；

//訪問此結點

prev(root->lch);//訪問孩子結點

prev(root->rch);

}}比較7.4圖的遍歷第44頁/共119頁圖中某未訪問過的頂點vi出發(fā)：1）訪問頂點vi；2）訪問vi的所有未被訪問的鄰接點w1,w2,…wk

；3）依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點;依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；二、廣度優(yōu)先遍歷（類似于樹的按層遍歷）

V0

V7

V6

V5

V4

V3

V2

V1V0

V1

V3

V2

V7

V6

V5

V4這是序列（1）在遍歷過程中所經(jīng)過的路徑由于沒有規(guī)定訪問鄰接點的順序，廣度優(yōu)先序列不是唯一的例求圖G的以V0起點的的廣度優(yōu)先序列:V0,V1,V2,V3,V4,V5,V6,V77.4圖的遍歷第45頁/共119頁從圖中某頂點vi出發(fā)：1）訪問頂點vi；（容易實現(xiàn)）2）訪問vi的所有未被訪問的鄰接點w1,w2,…wk

；（容易實現(xiàn)）3）依次從這些鄰接點（在步驟2）訪問的頂點）出發(fā)，訪問它們的所有未被訪問的鄰接點;依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；為實現(xiàn)3），需要保存在步驟(2）中訪問的頂點，而且訪問這些頂點鄰接點的順序為：先保存的頂點，其鄰接點先被訪問。廣度優(yōu)先遍歷算法在廣度優(yōu)先遍歷算法中，需設置一隊列Q，保存已訪問的頂點，并控制遍歷頂點的順序。

V0

V7

V6

V5

V4

V3

V2

V17.4圖的遍歷第46頁/共119頁廣度優(yōu)先遍歷從圖中某頂點v出發(fā)：1）訪問頂點v；2）訪問v的所有未被訪問的鄰接點w1,w2,…wk

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

V0

V7

V6

V5

V4

V3

V2

V1QV1V2V3V0V4V5V6V7V0V1V2V3V4V5V6V77.4圖的遍歷第47頁/共119頁在廣度優(yōu)先遍歷算法中，需設置一隊列

Q，保存已訪問的頂點，并控制遍歷頂點的順序intvisit[MAX];intqueue[MAX],front=0,rear=0;

7.4圖的遍歷第48頁/共119頁voidbft(intv)//從v出發(fā)，廣度優(yōu)先遍歷圖G。

{intw;NODE*p;visit[v]=1;printf(“%d,”,v);

enter(v);//enter(v)為入隊列函數(shù)

while((v=leave())!=NULL);//leave()為出隊列函數(shù)

{p=adjlist[v].link;//p指向出隊列頂點v的第一個鄰接點

while(p!=NULL){w=p->vertex;//遍歷v所指的整個鏈表

if(visit[w]==0)//如果w未被訪問過

{printf(“%d,”,w);//訪問wvisit[w]=1;enter(w);訪問后，w入隊

}p=p->link;}}}7.4圖的遍歷第49頁/共119頁main(){intnum;num=create(adjlist);breadfirst(num);//調(diào)用對圖G廣度遍歷圖算法

}voidbreadfirst(intnum){int;for(i=0;i<num;i++)visit[i]=0;//給所有頂點一個未被訪問標記

for(i=0;i<num;i++)if(visit[i]==0)bft(i);//調(diào)用以頂點vi為出發(fā)點的是廣度優(yōu)先遍歷圖G的算法

}第50頁/共119頁

01234567V0V1V2V3V4V5V6V7120115773064265243第51頁/共119頁

V0

V2

V3

V1

V5

V4

V0

V2

V3

V1

V5

V4深度優(yōu)先遍歷廣度優(yōu)先遍歷兩種遍歷的比較7.4圖的遍歷第52頁/共119頁7.5生成樹和最小生成樹7.5.1

無向圖的連通分量和生成樹深度遍歷P159圖G3，得到的序列為：ALMJBFCDEGKHI第53頁/共119頁生成樹生成樹是一個連通圖G的一個極小的連通子圖。包含圖G的所有頂點，但只有n-1條邊，并且是連通的。生成樹可由遍歷過程中所經(jīng)過的邊組成。深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。

V0

V7

V6

V5

V4

V3

V2

V1

V3

V0

V7

V6

V5

V4

V2

V1深度優(yōu)先生成樹廣度優(yōu)先生成樹7.5生成樹和最小生成樹第54頁/共119頁

要在n個城市間建立交通網(wǎng)，要考慮的問題如何在保證n點連通的前題下最節(jié)省經(jīng)費?V2V0V3V5V4如何求連通圖的最小生成樹?？7.5.2最小生成樹（最小支撐樹）

若有一個連通的無向圖G，有n個頂點，并且它的邊是有權值的。在G上構造生成樹G’

,最小生成樹n-1條邊的權值之和最小的G’

。7.5生成樹和最小生成樹第55頁/共119頁MST性質(zhì)：假設N=(V,{E})是一個連通網(wǎng)，若(u,v)是一條具有最小權值（代價）的邊，則必存在一棵包含邊(u,v)的最小生成樹。普里姆算法克魯斯卡爾算法第56頁/共119頁普魯姆算法基本步驟設G=（V，E）為一個具有n個頂點的帶權的連通網(wǎng)絡，T=（U，TE）為構造的生成樹。（1）初始時，U={u0}，TE=；（2）在所有uU、vV-U的邊（u,v）中選擇一條權值最小的邊，不妨設為（u,v)；（3）(u,v)加入TE，同時將u加入U；（4）重復(2)、（3），直到U=V為止；(1)普魯姆算法V2V0V3V5V4V136521655467.5生成樹和最小生成樹第57頁/共119頁V2V0V3V5V42V0V3V5V4V112V2V0V3V5V4V114V2V0V3V5V4V1142V2V0V3V5V4V11452V3V0V3V5V4V11453U={V0}U={V0,V2}U={V0,V2,V5}U={V0,V2,V5,V3}U={V0,V2,V5,V3,V1}U={V0,V2,V5,V3,V1,V4}第58頁/共119頁有關數(shù)據(jù)的存儲結構無向連通網(wǎng)絡:G

為選擇權值最小的邊:置一個一維數(shù)組：closest[]，對iV-Uclosest[i]=j(jU)(j,i)是一條邊，且是i到U中各頂點“權最小邊”Lowcost[i]：用來保存連接i到U中各頂點“權最小邊”的權。

普魯姆算法涉及的數(shù)據(jù)和操作：數(shù)據(jù)：無向連通網(wǎng)絡操作:選擇權值最小的邊，不妨設為（u,v)(u,v)加入TE，u加入UV2V0V3V5V4V-UviUV-Uvivj7.5生成樹和最小生成樹第59頁/共119頁V2V0V3V5V40000000615maxmax

iclosest[i]lowcost[i]

012345iclosest[i]lowcost[i]

01234502002

205

056

4U={v0}U={v0,v2}V2V0V3V5V4U對iV-Uclosest[i]=j(jU)(j,i)是一條邊，且是i到U中各頂點“權最小邊”Lowcost[i]：用來保存連接i到U中各頂點“權最小邊”的權。V-U={v1,V2,V3,V4,V5}V-U={v1,V3,V4,V5}7.5生成樹和最小生成樹第60頁/共119頁

000000

06

1

5maxmax

lowcost{0}

020022

05056

4

closestlowcost{0,2}

020522

050

2

60

closestlowcost{0,2,5}

020522

0

5

0060

closestlowcost{0,2,5,3}

020512

0000

3

0closestlowcost{0,2,5,3,1}

020512

000000

closestlowcost{0,2,5,3,1,4}iclosest

012345U7.5生成樹和最小生成樹第61頁/共119頁普里姆算法圖采用鄰接矩陣表示，鄰接矩陣所對應的二維數(shù)組是cost[MAX][MAX],則

(1)初始化(U={0}),closest[i]=0;lowcost[i]=cost[0][i];lowcost[0]=0;(i=1,2,3,…n-1;)(2)每次掃描數(shù)組lowcost[i]，找出值最小且不為0的lowcost[k]，得到最小生成樹的一條邊（closest[k],k]),將其輸出。（3）令lowcost[k]=0,將k并入U中（4）修改數(shù)組closest[i]和lowcost[i]（lowcost[i]！=0及i∈V-U（5）重復（2）（3）（4），直到U=V（或循環(huán)n-1次）結束

7.5生成樹和最小生成樹第62頁/共119頁普里姆算法viudPRIM(intcost[][N],intstart_v){intclosest[N],lowcost[N],i,j,k,min;for(i=0;j<N;i++){lowcost[i]=cost[start_v][i];closest[i]=start_v;}for(i=1;i<N;i++)//循環(huán)n-1次，每次求出最小生成樹的一條邊

{min=MAX;for(j=0;j<N;j++)if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}//找出值最小的lowcost[k]printf(“%d,%d:%d\n”,closest[k],k,lowcost[k]);lowcost[k]=0;//將k并入U中

for(j=0;j<N;j++)//修改lowcost[]和closest[]if(cost[k][j]!=0&&cost[k][j]<lowcost[j]){lowcost[j]=cost[k][j];closest[j]=k;}}}7.5生成樹和最小生成樹第63頁/共119頁基本步驟設G=（V，E）為一個具有n個頂點的帶權的連通網(wǎng)絡，最小生成樹的初始狀態(tài)為有n個頂點但無邊的非連通圖T=（V，）。（1）將E中的邊按權值的遞增順序排序，選擇權值最小的邊，若與相關的頂點落在T中不同的連通分量上，則將其加入T中，否則，將其棄舍。（2）循環(huán)至所有頂點在同一的連通分量上。如何識別一條邊所相關的頂點是否落在同一個連通分量上？可將一個連通分量的所有頂點看成一個集合，當從E中取出一條邊（xi,xj）時，若xi,xj在同一集合u中，則將該邊棄舍；否則，則將該邊加入到T中，并將xj所在的集合v并入集合u中。（2）克魯斯卡爾算法V2V0V3V5V4V136521655467.5生成樹和最小生成樹第64頁/共119頁需要引入輔助數(shù)組sets[]（1）初始化：圖G中的n個頂點，構成n個連通分量，頂點xi對應的連通分量用集合i表示，所以sets[i]=i,即表示第i個頂點在集合i中。（2）依次取出E中的邊（按邊權值遞增順序），設取出的邊為（xi,xj）。（3）判斷：若sets[i]=sets[j],則表示xi和xj在同一集合中，返回（2）；否則，轉到（4）。（4）將邊（xi,xj）并入T，同時將xj所在的集合v（與xj連通的頂點）并入xi所在的集合u（與xi連通的頂點），即：由v=sets[j]和u=sets[i]，掃描輔助數(shù)組sets[]，若sets[k]=v,則令sets[k]=u。返回（2）。（5）重復（2）、（3）、（4），取出n-1條邊。012345012345

下標setsV2V0V3V5V4V136521655467.5生成樹和最小生成樹第65頁/共119頁V2V0V3V5V4V13652165546012345012345

下標sets012345012345

下標sets031001111V2V0V3V5V4V1123457.5生成樹和最小生成樹第66頁/共119頁V2V0V3V5V4V13652165546012345012345

下標sets012345012345

下標setsV2V0V3V5V4V17.5生成樹和最小生成樹第67頁/共119頁V2V0V3V5V4V13652165546012345012345

下標sets010345012345

下標setsV2V0V3V5V4V117.5生成樹和最小生成樹第68頁/共119頁V2V0V3V5V4V13652165546012345012345

下標sets010343

012345

下標setsV2V0V3V5V4V1127.5生成樹和最小生成樹第69頁/共119頁V2V0V3V5V4V13652165546012345012345

下標sets010313012345

下標setsV2V0V3V5V4V11237.5生成樹和最小生成樹第70頁/共119頁V2V0V3V5V4V13652165546012345012345

下標sets010310012345

下標setsV2V0V3V5V4V112347.5生成樹和最小生成樹第71頁/共119頁V2V0V3V5V4V13652165546012345012345

下標sets010010012345

下標setsV2V0V3V5V4V112347.5生成樹和最小生成樹第72頁/共119頁V2V0V3V5V4V13652165546012345012345

下標sets011010012345

下標setsV2V0V3V5V4V1123457.5生成樹和最小生成樹第73頁/共119頁V2V0V3V5V4V13652165546012345012345

下標sets111010012345

下標setsV2V0V3V5V4V1123457.5生成樹和最小生成樹第74頁/共119頁V2V0V3V5V4V13652165546012345012345

下標sets111

110012345

下標setsV2V0V3V5V4V1123457.5生成樹和最小生成樹第75頁/共119頁V2V0V3V5V4V13652165546012345012345

下標sets111

111

012345

下標setsV2V0V3V5V4V1123457.5生成樹和最小生成樹第76頁/共119頁克魯斯卡爾算法中，數(shù)據(jù)結構定義為：

structnode{intbegin,end;//邊的相關頂點編號

intcost;};//邊的權值

typedefstructnodeEDGE;EDGEedges[MAX];//存放邊的數(shù)組，排好序的

intnum;//數(shù)組中實際存放的邊數(shù)

intkruskal(EDGEedges[],intnum){intsets[N],t,i,j,k,u,v;for(i=0;i<N;i++)sets[i]=i;//初始化

k=0;t=0;7.5生成樹和最小生成樹第77頁/共119頁克魯斯卡爾算法：

while((t<N)&&(k<num)){i=edges[k].begin;j=edges[k].end;k++;

//按順序取出一條邊

u=sets[i];v=sets[j];

//xi在集合u中,xj在集合v中

if(u!=v)

//xi,xj不在同一集合中

{printf(“%d,%d:%d\n”,u,v,edges[k].cost);t++;for(i=0;i<N;i++)

if(sets[i]==v)set[i]=u;

//xi在集合的v并入在集合的u中

}}

if(t==N-1)return(1);elsereturn(0);}7.5生成樹和最小生成樹第78頁/共119頁作業(yè)：1、寫出圖的深度優(yōu)先遍歷算法和廣度優(yōu)先遍歷算法。寫出下圖的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列。ABLMV1IEKHCFGDJ第79頁/共119頁2、分別用普里姆算法和克魯斯卡爾算法畫出下圖中的網(wǎng)的最小生成樹生成過程。V2V0V3V5V480頁/共119頁7.5

有向無環(huán)圖及其應用在工程實踐中，一個工程項目往往由若干個子項目組成，這些子項目間往往有多種關系：①先后關系，即必須在一子項目完成后，才能開始實施另一個子項目；②子項目之間無次序要求，即兩個子項目可以同時進行，互不影響。在工廠中，一件設備的生產(chǎn)包括許多工序，各工序之間也存在這兩種關系。學校里某個專業(yè)的課程學習，有些課程是基礎課，它們可以獨立于其它課程，即無前導課程；有些課程必須在一些課程學完后才能開始學。2023/1/1982第81頁/共119頁AOV網(wǎng)絡這些類似的問題都可以用有向圖來表示，我們把這些子項目、工序、課程看成一個個頂點稱之為活動(Activity)。如果從頂點Vi到Vj之間存在有向邊<Vi，Vj>,則表示活動i必須先于活動j進行。這種圖稱做頂點表示活動的網(wǎng)絡(ActivityOnVertexnetwork,簡稱AOV網(wǎng)絡)。例如某校計算機專業(yè)的課程及其相互之間的關系，它對應的AOV網(wǎng)絡如下頁圖所示。2023/1/1983第82頁/共119頁

某專業(yè)課程設置2023/1/1984第83頁/共119頁

課程設置的AOV網(wǎng)絡2023/1/1985第84頁/共119頁

有向無環(huán)圖描述在AOV網(wǎng)絡中，如果頂點Vi的活動必須在頂點Vj的活動以前進行，則稱Vi為Vj的前趨頂點，而稱Vj為Vi的后繼頂點。這種前趨后繼關系有傳遞性。AOV網(wǎng)絡中一定不能有有向環(huán)路。例如在下頁圖那樣的有向環(huán)路中，V2是V3的前趨頂點，V1是V2的前趨頂點，V3又是V1的前趨頂點，環(huán)路表示頂點之間的先后關系進入了死循環(huán)。因此，對給定的AOV網(wǎng)絡首先要判定網(wǎng)絡中是否存在環(huán)路，只有有向無環(huán)路網(wǎng)絡在應用中才有實際意義。一個無環(huán)的有向圖稱為有向無環(huán)圖，它是一類較有向樹更一般的特殊有向樹。2023/1/1986第85頁/共119頁

有向環(huán)路舉例2023/1/1987第86頁/共119頁

拓撲排序所謂“拓撲排序”就是將AOV網(wǎng)絡中的各個頂點(各個活動)排列成一個線性有序序列，使得所有要求的前趨、后繼關系都能得到滿足。由于AOV網(wǎng)絡中有些頂點之間沒有次序要求，它們在拓撲有序序列中的位置可以任意顛倒，所以拓撲排序的結果一般并不是唯一的。通過拓撲排序還可以判斷出此AOV網(wǎng)絡是否包含有有向環(huán)路，若有向圖G所有頂點都在拓撲排序序列中，則AOV網(wǎng)絡必定不包含有有向環(huán)路。2023/1/1988第87頁/共119頁

拓撲排序方法(1)在網(wǎng)絡中選擇一個沒有前趨(入度為0)的頂點，并把它輸出；(2)從網(wǎng)絡中刪去該頂點和從該頂點發(fā)出的所有有向邊；(3)重復執(zhí)行上述兩步，直到網(wǎng)中所有的頂點都被輸出(此時，原AOV網(wǎng)絡中的所有頂點和邊就都被刪除掉了)。如果進行到某一步，無法找到無前趨的頂點，則說明此AOV網(wǎng)絡中存在有向環(huán)路，遇到這種情況，拓撲排序就無法進行了。2023/1/1989第88頁/共119頁

拓撲排序過程AOV網(wǎng)絡2023/1/1990輸出V3后第89頁/共119頁輸出V4后2023/1/1991輸出V2后輸出V1后輸出V5后輸出拓撲序列為：34215第90頁/共119頁

關鍵路徑法關鍵路徑法是采用邊表示活動(ActivityOnEdge)的網(wǎng)絡，簡稱為AOE網(wǎng)絡。AOE網(wǎng)絡是一個帶權的有向無環(huán)路圖，其中，每個頂點代表一個事件(Event)，事件說明某些活動或某一項活動的完成，即階段性的結果。離開某頂點的各條邊所代表的活動，只有在該頂點對應的事件出現(xiàn)后才能開始。權值表示活動持續(xù)的時間。2023/1/1992第91頁/共119頁

一個AOE網(wǎng)絡2023/1/1993第92頁/共119頁AOE網(wǎng)絡通常利用AOE網(wǎng)絡可以研究以下兩個問題：(1)完成整個工程至少需要多少時間？(2)哪些活動是影響工程進度的關鍵？2023/1/1994第93頁/共119頁

關鍵路徑完成工程所需的時間就是從開始點起進行到結束點止所需的時間。路徑長度是指沿路徑各邊的權值之和，也就是這些邊所代表的活動所需時間之和。完成整個工程所需的時間取決于從開始點到結束點的最長路徑長度，此長度最大的路徑叫做關鍵路徑。分析關鍵路徑的目的是辨別哪些是關鍵活動，以便爭取提高關鍵活動的效率，縮短整個工期。2023/1/1995第94頁/共119頁求關鍵路徑的算法描述在描述關鍵路徑的算法時，設活動ai由弧<j,k>表示，要確定如下幾個相關的量：(1)事件Vj的最早出現(xiàn)時間和活動的最早開始時間：從源點V1到某頂點Vj的最長路徑長度叫作事件j的最早出現(xiàn)時間，表示成ve[j]。頂點Vj的最早出現(xiàn)時間ve[j]決定了從Vj指出的各條邊所代表活動的最早開始時間，因為事件j不出現(xiàn)，它后面的各項活動就不能開始。我們以e[i]表示活動ai的最早開始時間。顯然e[i]=ve[j]。2023/1/1996第95頁/共119頁求關鍵路徑的算法描述(續(xù))(2)活動ai的最遲開始時間：在不影響整個工程按時完成的前提下，此項活動最遲的必須開始時間，表示成L[i]。只要某活動ai有L[i]=e[i]的關系，我們就稱ai為關鍵活動。關鍵活動只允許在一個確定的時間開始，再早，它前面的事件還沒出現(xiàn)，尚不能開始；再晚，又會延誤整個工程的按時完成。由于完成整個工程所需的時間是由關鍵路徑上各邊權值之和所決定的，顯然關鍵路徑上各條邊所對應的活動都是關鍵活動。2023/1/1997第96頁/共119頁求關鍵路徑的算法描述(續(xù))(3)事件j的最遲出現(xiàn)時間：即事件j在不延誤整個工程的前提下允許發(fā)生的最遲時間，表示為vl[j]。對某條指向頂點Vk的邊所代表的活動ai可得到：

L[i]=vl[k]-(活動ai所需時間)

也就是活動ai必須先于它后面事件的最遲出現(xiàn)時間開始，提前的時間為進行此活動所需的時間。下圖所示為活動開始時間與事件出現(xiàn)時間的關系。2023/1/1998VjaiVk第97頁/共119頁求關鍵路徑的算法描述(續(xù))確定關鍵路徑的方法就是要確定e[i]=L[i]的關鍵活動。假設以w[j,k]表示有向邊<j,k>的權，即此邊對應的活動所需的時間，為了求AOE網(wǎng)絡中活動ai的最早開始時間e[i]和活動ai的最遲開始時間L[i]，先要求得頂點Vk的最早出現(xiàn)時間ve[k]和最遲出現(xiàn)時間vl[k]。2023/1/1999第98頁/共119頁ve[k]和vl[k]可以采用下