第5章圖張成文北京郵電大學(xué)計(jì)算機(jī)學(xué)院編輯ppt第5章圖第5章圖5.1圖的基本概念

非線性結(jié)構(gòu)，數(shù)據(jù)元素之間呈多對(duì)多的關(guān)系。5.1.1圖的定義Graph=(V,VR)V：頂點(diǎn)(數(shù)據(jù)元素)的有窮非空集合。

VR：弧(關(guān)系)的有窮集合。2編輯ppt第5章圖例1：G1=(V1,VR1)V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}EACBD例2：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)}BCAFED3編輯ppt第5章圖5.1.2圖的相關(guān)術(shù)語頂點(diǎn)數(shù)據(jù)元素所構(gòu)成的結(jié)點(diǎn)。有向圖弧的頂點(diǎn)偶對(duì)是有序的。對(duì)弧<vi,vj>而言，

vi是弧尾/初始點(diǎn)；vj是弧頭/終端點(diǎn)。無向圖弧的頂點(diǎn)偶對(duì)是無序的。

(vi,vj)和(vj,vi)代表同一條邊(ij)。(無向)完全圖每個(gè)頂點(diǎn)與其余頂點(diǎn)都有邊的無向圖。頂點(diǎn)數(shù)為n時(shí)，邊數(shù)e=n(n-1)/2有向完全圖每個(gè)頂點(diǎn)與其余頂點(diǎn)都有弧的有向圖。頂點(diǎn)數(shù)為n時(shí)，弧數(shù)e=n(n-1)稀疏圖有很少邊或弧的圖。（e<nlogn）稠密圖有較多邊或弧的圖。vivjvivj4編輯ppt第5章圖權(quán)圖中的邊或弧具有一定的大小的概念。網(wǎng)邊/弧帶權(quán)的圖。鄰接有邊/弧相連的兩個(gè)頂點(diǎn)之間的關(guān)系。存在(vi,vj)，則稱vi和vj互為鄰接點(diǎn)；存在<vi,vj>，則稱vi鄰接到vj，vj鄰接于vi

關(guān)聯(lián)(依附)邊/弧與頂點(diǎn)之間的關(guān)系。存在(vi,vj)/<vi,vj>，則稱該邊/弧關(guān)聯(lián)于vi和vj頂點(diǎn)的度與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，記為D(v)。

入度ID(v)：有向圖中，以該頂點(diǎn)為弧頭的弧數(shù)目。

出度OD(v)：有向圖中，以該頂點(diǎn)為弧尾的弧數(shù)目。vivjvivjABEC輯ppt第5章圖路徑

接續(xù)的邊構(gòu)成的頂點(diǎn)序列。

路徑長度路徑上邊或弧的數(shù)目/權(quán)值之和。

回路(環(huán))第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。

簡單路徑序列中頂點(diǎn)均不相同的路徑。

簡單回路(簡單環(huán))除路徑起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)均不相同的路徑。從A到F長度為3的路徑

{A,B,C,F}ABECF6編輯ppt第5章圖連通圖無向圖中，任何一對(duì)頂點(diǎn)間都存在路徑。

連通分量無向圖中的極大連通子圖。強(qiáng)連通圖有向圖中，任何一對(duì)頂點(diǎn)間都存在路徑。

強(qiáng)連通分量有向圖中的極大連通子圖。7編輯ppt第5章圖生成有向樹生成森林子圖對(duì)于圖G=(V,E)和G’=(V’,E’)，如果V’V，E’E，且E’關(guān)聯(lián)的頂點(diǎn)都在V’中，則稱G’是G的子圖。生成子圖由圖的全部頂點(diǎn)和部分邊組成的子圖稱為原圖的生成子圖。生成樹包含圖中全部頂點(diǎn)的極小連通子圖。有向樹圖中恰有一個(gè)頂點(diǎn)入度為0，其余頂點(diǎn)入度均為1。生成森林有向圖中，包含所有頂點(diǎn)的若干棵有向樹構(gòu)成的子圖。e=n-18編輯ppt第5章圖5.2圖的存儲(chǔ)結(jié)構(gòu)5.2.1數(shù)組/鄰接矩陣表示法(順序存儲(chǔ)方式)[例1]無向圖

頂點(diǎn)數(shù)組vexs

鄰接矩陣(邊表)arcs0A01101B10112C11013D01100AB12CD3G1無向圖的鄰接矩陣具有對(duì)稱性[例2]有向網(wǎng)頂點(diǎn)數(shù)組vexs

鄰接矩陣(邊表)arcs0A0321B042C503D2032542G20AB12CD39編輯ppt第5章圖5.2.2鄰接表順序存儲(chǔ)+鏈?zhǔn)酱鎯?chǔ)

頂點(diǎn)順序表鄰接頂點(diǎn)的單鏈表(邊表)G1:0A12^1B023^2C013^3D12^G2:0A1322^1B34^2C15^3D22^

出邊表(逆鄰接表時(shí)用入邊表)nextarcadjvexnextarcweightadjvex無向圖有向網(wǎng)0AB12CD30AB12CD332542datafirstarcvertices10編輯ppt第5章圖5.3圖的遍歷深度優(yōu)先遍歷(樹的先根遍歷的推廣)廣度優(yōu)先遍歷(樹的按層次遍歷的推廣)[例]v1v2v3v4v5v6v7v8深度：v1v2v4v8v5v6v3v7廣度：v1v2v3v4v5v6v7v8設(shè)從v1出發(fā)遍歷數(shù)據(jù)結(jié)構(gòu)：主——圖的存儲(chǔ)結(jié)構(gòu)輔——數(shù)組visited[0..n-1]11編輯ppt第5章圖5.3.1深度優(yōu)先搜索遞歸的算法思想

(1)訪問頂點(diǎn)v，并記錄v已被訪問

(2)依次從v的未訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先搜索圖G。算法描述typedefenum{FALSE,TRUE}Boolean;//FALSE為0，TRUE為1Booleanvisited[MAX_VERTEX_NUM];//輔助訪問標(biāo)志向量voidDFSTraverse(GraphG){for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//標(biāo)志向量初始化

for(v=0;v<G.vexnum;++v)

if(!visited[v])DFS(G,v);}//DFSTraverse0123412編輯ppt第5章圖voidDFS(GraphG,intv){visit(v);visited[v]=TRUE;//訪問頂點(diǎn)v，并標(biāo)記

for(w=FirstAdjVex(G,v);w>-1;w=NextAdjVex(G,v,w))

if(!visited[w])DFS(G,w);}//DFSvoidDFS(MGraphG,intv)//深度優(yōu)先遍歷鄰接矩陣表示的圖{visit(G.vexs[v]);visited[v]=TRUE;for(j=0;j<G.vexnum;++j)

if(G.arcs[v][j]!=0&&!visited[j])DFS(G,j);}//DFSvoidDFS(ALGraphG,intv)//深度優(yōu)先遍歷鄰接表表示的圖{visit(G.vertices[v].data);visited[v]=TRUE;p=G.vertices[v].firstarc;//取v邊表的頭指針

while(p){

if(!visited[p->adjvex])DFS(G,p->adjvex);p=p->nextarc;}}//DFS例13編輯ppt第5章圖abchdekfg812345670FFFFFFFFF012345678TTTTTTTTTachdkfebgachkfedbg訪問標(biāo)志:訪問次序:例achdkfe14編輯ppt第5章圖5.3.2廣度(寬度)優(yōu)先遍歷[算法思想](1)訪問頂點(diǎn)v，并記錄它已被訪問；頂點(diǎn)v入隊(duì)列；

(2)如果隊(duì)列空，則退出；否則，從隊(duì)中取出一頂點(diǎn)；

(3)求該頂點(diǎn)的一個(gè)鄰接點(diǎn)；如果此鄰接點(diǎn)未被訪問，則訪問它，并記錄它已被訪問，將其入隊(duì)列；

(4)如果該頂點(diǎn)還有下一個(gè)鄰接點(diǎn)，則轉(zhuǎn)(3)；否則，轉(zhuǎn)(2)12345615編輯ppt第5章圖算法描述voidBFSTraverse(GraphG){for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//標(biāo)志向量初始化

InitQueue(Q);//輔助隊(duì)列初始化

for(v=0;v<G.vexnum;++v)

if(!visited[v]){

visit(v);visited[v]=TRUE;EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,u);

for(w=FirstAdjVex(G,u);w>-1;w=NextAdjVex(G,u,w))if(!visited[w]){

visited[w]=TRUE;visit(w);EnQueue(Q,w);}}}}//BFSTraverse16編輯ppt第5章圖[算法時(shí)間復(fù)雜度分析]

與深度優(yōu)先遍歷過程相同5.3.3圖的遍歷小結(jié)深度優(yōu)先遍歷算法借助于棧結(jié)構(gòu)實(shí)現(xiàn)；廣度優(yōu)先遍歷算法借助于隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)圖的遍歷序列與算法和存儲(chǔ)方式有關(guān)17編輯ppt第5章圖5.3.4圖的遍歷應(yīng)用舉