數(shù)據(jù)結(jié)構(gòu)圖的基本概念本

第七章圖圖與其它結(jié)構(gòu)對比圖是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層的數(shù)據(jù)元素可能和下一層中的多個元素有關(guān)，但只能和上一層中一個元素有關(guān)。圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。本章內(nèi)容1.圖的基本概念2.圖的存儲結(jié)構(gòu)3.圖的遍歷4.圖的連通性和最小生成樹問題5.圖的拓?fù)渑判蚝完P(guān)鍵路徑6.圖的最短路徑圖的結(jié)構(gòu)定義圖G是由兩個集合V和R組成。其中V是頂點(diǎn)的有窮非空集合，R是V中頂點(diǎn)偶對的有窮集合。Graph=(V,R)V={圖中所有頂點(diǎn)}R={圖中各個頂點(diǎn)之間的關(guān)系VR}其中，VR＝{<v,w>|v,w∈V

且P(v,w)}

<v,w>表示從v到w的一條弧，并稱v

為弧尾，w

為弧頭。謂詞P(v,w)定義了弧<v,w>的意義或信息。

由于“弧”是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖。EACBD例如:G1=(V1,VR1)其中V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}若<v,w>VR

必有<w,v>VR,則稱(v,w)

為頂點(diǎn)v和頂點(diǎn)w之間存在一條邊。

BCADFE由頂點(diǎn)集和邊集構(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)、子圖

完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長度、簡單路徑、簡單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹、生成森林ABECFAEFBC設(shè)圖G=(V,{VR})和圖

G=(V,{VR}),且

VV,VRVR,則稱

G為G的子圖。1597211132弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無向網(wǎng)。假設(shè)圖中有n

個頂點(diǎn)，e

條邊，則：含有e=n(n-1)/2

條邊的無向圖稱作無向完全圖；含有e=n(n-1)

條弧的有向圖稱作有向完全圖；若邊或弧的個數(shù)e<nlogn，則稱作稀疏圖，否則稱作稠密圖。對于無向圖G，頂點(diǎn)v和頂點(diǎn)w之間存在一條邊，則稱頂點(diǎn)v

和w

互為鄰接點(diǎn)，ACDFE例如:TD(B)=3TD(A)=2

邊(v,w)

和頂點(diǎn)v和w相關(guān)聯(lián)。和頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目定義為頂點(diǎn)的度。B頂點(diǎn)的出度:以頂點(diǎn)v為弧尾的弧的數(shù)目；ABECF對有向圖來說，頂點(diǎn)的入度:以頂點(diǎn)v為弧頭的弧的數(shù)目。頂點(diǎn)的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3一般地，如果頂點(diǎn)vi的度記為TD(vi)，那么一個有n個頂點(diǎn)，e條邊或弧的圖，滿足如下關(guān)系：設(shè)圖G=(V,{VR})中的一個頂點(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ù)目稱作路徑長度。ABECF如:長度為3的路徑{A,B,C,F}簡單路徑:序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。回路或環(huán):序列中第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑。簡單回路或簡單環(huán)：除第一個和最后一個頂點(diǎn)外，其余頂點(diǎn)不出現(xiàn)重復(fù)的回路。若無向圖G中任意兩個頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖；若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。BACDFEBACDFE

若任意兩個頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。ABECFABECF對有向圖，否則，其各個極大強(qiáng)連通子圖稱作它的強(qiáng)連通分量。假設(shè)一個連通圖有n個頂點(diǎn)和e條邊，其中n-1條邊和n個頂點(diǎn)構(gòu)成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林。BACDFE圖的基本操作1.圖的建立和銷毀CreatGraph(&G,V,VR)DestroyGraph(&G)2.圖的遍歷DFSTraverse(G,v)深度優(yōu)先遍歷圖GBFSTraverse(G,v)廣度優(yōu)先遍歷圖G3.對頂點(diǎn)的操作LocateVex(G,u)GetVex(G,v)PutVex(&G,v,value)InsertVex(&G,