抽象數(shù)據(jù)類型圖的定義

《抽象數(shù)據(jù)類型圖的定義》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第七章圖7.1抽象數(shù)據(jù)類型圖的定義7.2圖的存儲(chǔ)表示7.3圖的遍歷7.4最小生成樹(shù)7.5重（雙）連通圖和關(guān)節(jié)點(diǎn)7.6兩點(diǎn)之間的最短路徑問(wèn)題7.7拓?fù)渑判?.8關(guān)鍵路徑圖是由一個(gè)頂點(diǎn)集V和一個(gè)弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。Graph=(V,R)其中，VR＝{

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

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

4、FAEABBC設(shè)圖G=(V,{VR})和圖G?=(V?,{VR?}),且V??V,VR??VR,則稱G?為G的子圖。1597211132弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無(wú)向網(wǎng)。假設(shè)圖中有n個(gè)頂點(diǎn)，e條邊，則含有e=n(n-1)/2條邊的無(wú)向圖稱作完全圖；含有e=n(n-1)條弧的有向圖稱作有向完全圖；若邊或弧的個(gè)數(shù)e

5、點(diǎn)的出度:以頂點(diǎn)v為弧尾的弧的數(shù)目；ABECF對(duì)有向圖來(lái)說(shuō)，頂點(diǎn)的入度:以頂點(diǎn)v為弧頭的弧的數(shù)目。頂點(diǎn)的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3設(shè)圖G=(V,{VR})中的一個(gè)頂點(diǎn)序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)?VR1≤j≤m,則稱從頂點(diǎn)u到頂點(diǎn)w之間存在一條路徑。路徑上邊的數(shù)目稱作路徑長(zhǎng)度。ABECF如:長(zhǎng)度為3的路徑{A,B,C,F}簡(jiǎn)單路徑:序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡(jiǎn)單回路:序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。若圖G中任意

6、兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖；若無(wú)向圖為非連通圖，則圖中各個(gè)極大連通子圖稱作此圖的連通分量。BACDFEBACDFE若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。ABECFABECF對(duì)有向圖，否則，其各個(gè)強(qiáng)連通子圖稱作它的強(qiáng)連通分量。假設(shè)一個(gè)連通圖有n個(gè)頂點(diǎn)和e條邊，其中n-1條邊和n個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹(shù)。對(duì)非連通圖，則稱由各個(gè)連通分量的生成樹(shù)的集合為此非連通圖的生成森林。BACDFE結(jié)構(gòu)的建立和銷毀插入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)頂點(diǎn)的訪問(wèn)操作遍歷插入和刪除弧

7、基本操作CreatGraph(&G,V,VR)://按定義(V,VR)構(gòu)造圖DestroyGraph(&G)://銷毀圖結(jié)構(gòu)的建立和銷毀對(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);//返回v的（相對(duì)于w

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

9、調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit());//從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對(duì)每//個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。7.2圖的存儲(chǔ)表示一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示二、圖的鄰接表存儲(chǔ)表示三、有向圖的十