數(shù)據(jù)結(jié)構(gòu)與算法分析第6講圖

《數(shù)據(jù)結(jié)構(gòu)與算法分析第6講圖》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、Chapter6Graphs圖的類(lèi)型定義n(n≥0)個(gè)元素的有限集合基本術(shù)語(yǔ)圖是由一個(gè)頂點(diǎn)集V和一個(gè)弧集VR構(gòu)成的數(shù)據(jù)結(jié)構(gòu)Graph=(V,{VR})其中:VR＝{

2、v,w∈V且P(v,w)}表示從v到w的一條弧，并稱(chēng)v為弧尾，w為弧頭謂詞P(v,w)定義了弧的意義或信息由于“弧”是有方向的，因此稱(chēng)由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖ABECD例如:G1=(V1,{VR1})其中:V1={A,B,C,D,E}VR1={,,,,,,}若有?VR,必有

3、v>?VR,則稱(chēng)(v,w)為頂點(diǎn)v和頂點(diǎn)w之間存在一條邊BCADFE由頂點(diǎn)集和邊集構(gòu)成的圖稱(chēng)作無(wú)向圖例如:G2=(V2,{VR2})V2={A,B,C,D,E,F}VR2={,,,,,,}名詞和術(shù)語(yǔ)網(wǎng)、子圖完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑、簡(jiǎn)單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹(shù)、生成森林關(guān)節(jié)點(diǎn)、重連通圖重連通分量、連通度AEFBBC設(shè)圖G=(V,VR)和圖G?=(V?,VR?),且V??V,VR??VR,則稱(chēng)G?為G的子圖ABECF15972

4、11132弧或邊帶權(quán)的圖分別稱(chēng)作有向網(wǎng)或無(wú)向網(wǎng)假設(shè)圖中有n個(gè)頂點(diǎn)，e條邊，則含有e=n(n-1)/2條邊的無(wú)向圖稱(chēng)作無(wú)向完全圖含有e=n(n-1)條弧的有向圖稱(chēng)作有向完全圖若邊或弧的個(gè)數(shù)e

5、=3設(shè)圖G=(V,{VR})中的一個(gè)頂點(diǎn)序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)?VR1≤j≤m,則稱(chēng)從頂點(diǎn)u到頂點(diǎn)w之間存在一條路徑。路徑上邊的數(shù)目稱(chēng)作路徑長(zhǎng)度ABECF長(zhǎng)度為3的路徑{A,B,C,F}ABECF簡(jiǎn)單路徑:序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑簡(jiǎn)單回路:序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑若圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱(chēng)此圖為連通圖若無(wú)向圖為非連通圖，則圖中各個(gè)極大連通子圖稱(chēng)作此圖的連通分量BACDFEBACDFE若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱(chēng)此有向圖為強(qiáng)連通圖,ABECFABECF對(duì)有向圖

6、，否則，其各個(gè)強(qiáng)連通子圖稱(chēng)作它的強(qiáng)連通分量假設(shè)一個(gè)連通圖有n個(gè)頂點(diǎn)和e條邊，其中n-1條邊和n個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱(chēng)該極小連通子圖為此連通圖的生成樹(shù)對(duì)非連通圖，則稱(chēng)由各個(gè)連通分量的生成樹(shù)的集合為此非連通圖的生成森林BACDFE沒(méi)有關(guān)節(jié)點(diǎn)的連通圖被稱(chēng)為重連通圖若連通圖中的某個(gè)頂點(diǎn)和其相關(guān)聯(lián)的邊被刪去之后，該連通圖被分割成兩個(gè)或兩個(gè)以上的連通分量，則稱(chēng)此頂點(diǎn)為關(guān)節(jié)點(diǎn)一個(gè)連通圖G如果不是重連通圖，那么它可以包括幾個(gè)重連通分量若依次刪除一個(gè)連通圖中的1,2,…,k-1個(gè)頂點(diǎn)后,該圖仍連通,刪除第k個(gè)頂點(diǎn)后該圖成為不連通的,則稱(chēng)該圖的連通度為k結(jié)構(gòu)的建立和銷(xiāo)毀插

7、入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)頂點(diǎn)的訪問(wèn)操作頂點(diǎn)的遍歷插入和刪除弧基本操作CreatGraph(&G,V,VR)://按定義(V,VR)構(gòu)造圖DestroyGraph(&G)://銷(xiāo)毀圖結(jié)構(gòu)的建立和銷(xiāo)毀對(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對(duì)鄰接點(diǎn)的操作FirstAdjVex(G,v);//返回v的“第一個(gè)鄰接點(diǎn)”。若該頂點(diǎn)//在G中沒(méi)有鄰接點(diǎn)，則返回“空”NextAdjVex(G,v,w

8、);//返回v的（相對(duì)于w的）“下一個(gè)鄰接//點(diǎn)”。若w是v的最后一個(gè)鄰接點(diǎn)，則//返回“空”插入或刪除頂點(diǎn)InsertVex(&G,v);//在圖G中增添新頂點(diǎn)vDeleteVex(&G,v);//刪除G中頂點(diǎn)v及其相關(guān)的弧插入和刪除弧InsertArc(&G,v,w);//在G中增添弧，若G是無(wú)向的，//則還增添對(duì)稱(chēng)弧DeleteArc(&G,v,w);//在G中刪除弧，若G是無(wú)向的，//則還刪除對(duì)稱(chēng)弧遍歷DFSTraverse(G,v,Visit());//從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對(duì)每//個(gè)頂點(diǎn)調(diào)用函數(shù)Vis

9、it一次且僅一次BFSTraverse