抽象數(shù)據(jù)類型圖的定義課件.ppt

《抽象數(shù)據(jù)類型圖的定義課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

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

3、={,,,,,,}若?VR必有?VR,則稱(v,w)為頂點v和頂點w之間存在一條邊。BCAFED由頂點集和邊集構(gòu)成的圖稱作無向圖。例如: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ù)語網(wǎng)、子圖完全圖、稀疏圖、稠密圖鄰接點、度、入度、出度路徑、路徑長度、簡單路徑、簡單回路連通圖、連通分量、強連通圖、強連通分量生成樹、生成森林ABECFAEFB

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

5、度:以頂點v為弧尾的弧的數(shù)目;ABECF對有向圖來說，頂點的入度:以頂點v為弧頭的弧的數(shù)目。頂點的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3由于弧有方向性，則有入度和出度之分設(shè)圖G=(V,{VR})中的一個頂點序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)?VR1≤j≤m,則稱從頂點u到頂點w之間存在一條路徑。路徑上邊的數(shù)目稱作路徑長度。ABECF如:從A到F長度為3的路徑{A,B,C,F}簡單路徑:指序列中頂點不重復(fù)出現(xiàn)的路徑。簡單回路:指序列中第一個頂點和最

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

7、點的訪問操作遍歷插入和刪除弧基本操作CreatGraph(&G,V,VR)://按定義(V,VR)構(gòu)造圖DestroyGraph(&G)://銷毀圖結(jié)構(gòu)的建立和銷毀對頂點的訪問操作LocateVex(G,u);//若G中存在頂點u，則返回該頂點在//圖中“位置”；否則返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//對v賦值value。對鄰接點的操作FirstAdjVex(G,v);//返回v的“第一個鄰接點”。若該頂點//在G中沒有鄰接點，則返回“空”。NextAdjVex(G,v,w);

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

9、并對每//個頂點調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit());//從頂點v起廣度優(yōu)先遍歷圖G，并對每//個頂點調(diào)用函數(shù)Visit一次且僅一次。7.2圖的存儲表示一、圖的數(shù)