數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)圖

數(shù)據(jù)結(jié)構(gòu)07圖第七章圖7.1圖地基本概念7.2圖地存儲(chǔ)結(jié)構(gòu)7.3圖地遍歷7.4最小生成樹7.5有向無環(huán)圖與其應(yīng)用7.6最短路徑7.1.1圖地概念圖（Graph）是由有窮非空地頂點(diǎn)集合與頂點(diǎn)之間邊地集合組成地,可表示為:G=(V,E)其G表示圖,圖地?cái)?shù)據(jù)元素通常叫作頂點(diǎn)（Vertex）,V稱為頂點(diǎn)地有窮非空集合,E是圖G頂點(diǎn)之間邊（Edge）地集合。7.1.1圖地概念若頂點(diǎn)v與w間地邊沒有方向,則稱這條邊為無向邊,用(v,w)表示,此時(shí)地圖稱為無向圖。若頂點(diǎn)v與w間地邊有方向,則稱這條邊為有向邊（也稱為?。?用<v,w>表示,且稱v為弧尾或初始點(diǎn),稱w為弧頭或終端點(diǎn),此時(shí)地圖稱為有向圖。7.1.1圖地概念無向圖G1頂點(diǎn)集合V={v1,v2,v3,v4,v5}邊地集合E={(v1,v2),(v1,v3),(v2,v4),(v2,v5),(v4,v5),(v3,v5)}有向圖G2頂點(diǎn)集合V={v1,v2,v3,v4}邊地集合E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}7.1.2圖地基本術(shù)語(yǔ)完全圖在由n個(gè)頂點(diǎn)組成地?zé)o向完全圖,若有n(n-1)/2條邊,則稱之為無向完全圖;在由n個(gè)頂點(diǎn)組成地有向圖,若有n(n-1)條邊,則稱之為有向完全圖。有向完全圖無向完全圖7.1.2圖地基本術(shù)語(yǔ)權(quán):在某些圖,邊或弧上具有與它有關(guān)地?cái)?shù)據(jù)信息稱為權(quán)。在實(shí)際應(yīng)用,權(quán)值可以有某種意義。比如,在反映城市交通線路地圖,邊上地權(quán)值可以表示該條線路地長(zhǎng)度;在反映工程進(jìn)度地圖,邊上地權(quán)值可以表示從前一個(gè)工程到后一個(gè)工程所需求地時(shí)間。這種帶權(quán)地圖稱為網(wǎng)或網(wǎng)絡(luò)。分別稱帶權(quán)地有向圖與帶權(quán)地?zé)o向圖為有向網(wǎng)與無向網(wǎng)。7.1.2圖地基本術(shù)語(yǔ)鄰接頂點(diǎn):對(duì)于無向圖G=(V,E),如果邊(u,v)∈E,則稱頂點(diǎn)u,v互為鄰接點(diǎn),即u,v相鄰接。邊(u,v)依附于頂點(diǎn)u與v,或者說邊(u,v)與頂點(diǎn)u與頂點(diǎn)v有關(guān)聯(lián)。對(duì)于有向圖而言,若弧<u,v>∈E,則稱頂點(diǎn)u鄰接到頂點(diǎn)v,頂點(diǎn)v鄰接自頂點(diǎn)u,或者說弧<u,v>與頂點(diǎn)u,v有關(guān)聯(lián)。7.1.2圖地基本術(shù)語(yǔ)子圖:設(shè)圖G=(V,E)與G'=(V',E'),若V'?V且E'?E,則稱圖G'是圖G地子圖。無向圖G3無向圖G3地部分子圖有向圖G4有向圖G4地部分子圖有向圖G4地部分子圖7.1.2圖地基本術(shù)語(yǔ)度無向圖地度:與頂點(diǎn)v關(guān)聯(lián)地邊地?cái)?shù)目,稱作v地度,記作deg(v)。有向圖地度:在有向圖,頂點(diǎn)地度等于入度與出度之與。頂點(diǎn)地入度是以頂點(diǎn)v為弧頭地弧地?cái)?shù)目,記作indeg(v);頂點(diǎn)v地出度是以頂點(diǎn)v為弧尾地弧地?cái)?shù)目,記作outdeg(v)。頂點(diǎn)地度deg(v)=indeg(v)+outdeg(v)度地計(jì)算公式:不論是有向圖還是無向圖,若圖有n個(gè)頂點(diǎn)與e條邊,則有:=7.1.2圖地基本術(shù)語(yǔ)路徑無向圖路徑:在圖G=(V,E),若從頂點(diǎn)vi出發(fā),沿一些邊通過若干頂點(diǎn)vp1,vp2,…,vpm到達(dá)頂點(diǎn)vj,則稱頂點(diǎn)序列。(vi,vp1,vp2,…,vpm,vj)為從頂點(diǎn)vi到頂點(diǎn)vj地一條路徑。它通過地邊(vi,vp1),(vp1,vp2),…,(vpm,vj)都屬于E。有向圖路徑:如果G是一個(gè)有向圖,則其路徑也是有向地,頂點(diǎn)序列(vi,vp1,vp2,…,vpm,vj)滿足它所通過地弧<vi,vp1>,<vp1,vp12>,…,<vpm,vj>都屬于E。路徑長(zhǎng)度:一條路徑上通過地邊或弧地?cái)?shù)目。7.1.2圖地基本術(shù)語(yǔ)簡(jiǎn)單路徑與回路簡(jiǎn)單路徑:若路徑上各頂點(diǎn)v1,v2,…,vm均不重復(fù),則稱這樣地路徑為簡(jiǎn)單路徑?；芈?若路徑上第一個(gè)頂點(diǎn)v1與最后一頂點(diǎn)vm重合,則稱這樣地路徑為回路或環(huán)。7.1.2圖地基本術(shù)語(yǔ)連通圖與連通分量:在無向圖,若存在從頂點(diǎn)v1到頂點(diǎn)v2地路徑,則稱頂點(diǎn)v1與v2是連通地。如果圖任意一對(duì)頂點(diǎn)都是連通地,則稱此圖是連通圖。非連通圖地極大連通子圖叫作連通分量。無向非連通圖G無向非連通圖G地三個(gè)連通分量7.1.2圖地基本術(shù)語(yǔ)強(qiáng)連通圖與強(qiáng)連通分量:在有向圖,若在每一對(duì)頂點(diǎn)vi與vj之間都存在一條從vi到vj地路徑,也存在一條從vj到vi地路徑,則稱此圖是強(qiáng)連通圖。而非強(qiáng)連通圖地極大強(qiáng)連通子圖叫作強(qiáng)連通分量。有向圖G有向圖G地兩個(gè)強(qiáng)連通分量7.1.2圖地基本術(shù)語(yǔ)生成樹:具有n個(gè)頂點(diǎn)地連通圖G地生成樹是包含G全部頂點(diǎn)地一個(gè)極小連通子圖。無向圖G無向圖G地生成樹注意:1.在生成樹添加任意一條屬于原圖地邊必定會(huì)產(chǎn)生回路或環(huán);2.生成樹減少任意一條邊必然會(huì)成為非連通圖3.一棵具有n個(gè)頂點(diǎn)地生成樹有且僅有n-1條邊7.1.2圖地基本術(shù)語(yǔ)生成森林:非連通圖地每個(gè)連通分量都可以得到一棵生成樹。這些連通分量地生成樹構(gòu)成了地森林,稱為生成森林。非連通圖GG地生成森林稀疏圖與稠密圖:邊數(shù)很少地圖稱為稀疏圖,反之則稱為稠密圖。7.1.3圖地抽象數(shù)據(jù)類型圖地基本操作與其它數(shù)據(jù)結(jié)構(gòu)一樣,也有創(chuàng)建,插入,刪除,查找等。圖地抽象類型定義與基本操作如P179所示。第七章圖7.1圖地基本概念7.2圖地存儲(chǔ)結(jié)構(gòu)7.3圖地遍歷7.4最小生成樹7.5有向無環(huán)圖與其應(yīng)用7.6最短路徑7.2.1圖地順序存儲(chǔ)結(jié)構(gòu)——鄰接矩陣鄰接矩陣定義:采用兩個(gè)數(shù)組表示圖。一個(gè)一維數(shù)組存儲(chǔ)圖頂點(diǎn)（數(shù)據(jù)元素信息）;一個(gè)二維數(shù)組存儲(chǔ)圖頂點(diǎn)之間地關(guān)系（邊或弧地信息）。7.2.1圖地順序存儲(chǔ)結(jié)構(gòu)——鄰接矩陣設(shè)G=(V,E)包含n個(gè)頂點(diǎn),則G地鄰接矩陣是一個(gè)二維數(shù)組G.Edge[n][n]。若G是一個(gè)無權(quán)圖,則G地鄰接矩陣定義為:G.Edge[i][j]=A1=A2=無權(quán)圖地鄰接矩陣表示G1G27.2.1圖地順序存儲(chǔ)結(jié)構(gòu)——鄰接矩陣若G是一個(gè)網(wǎng),則G地鄰接矩陣定義為:G.Edge[i][j]=網(wǎng)地鄰接矩陣表示7.2.1圖地順序存儲(chǔ)結(jié)構(gòu)——鄰接矩陣圖地鄰接矩陣存儲(chǔ)結(jié)構(gòu)具有以下特點(diǎn):(1)無向圖地鄰接矩陣是對(duì)稱地,采用壓縮矩陣進(jìn)行存儲(chǔ)。(2)有向圖地鄰接矩陣不一定對(duì)稱,因此采用鄰接矩陣存儲(chǔ)具有n個(gè)頂點(diǎn)地有向圖時(shí),需求n2個(gè)存儲(chǔ)單元。(3)無向圖鄰接矩陣地第i行（或第i列）非零元素地個(gè)數(shù),就是頂點(diǎn)i地度。(4)有向圖鄰接矩陣地第i行非零元素地個(gè)數(shù),就是頂點(diǎn)i地出度,第i列非零元素地個(gè)數(shù),就是頂點(diǎn)i地入度。(5)利用鄰接矩陣可以較容易地確定圖兩頂點(diǎn)之間是否有邊。但若要確定圖一有多少條邊,則要逐行逐列進(jìn)行檢測(cè),耗費(fèi)地時(shí)間代價(jià)較大,這也是鄰接矩陣存儲(chǔ)結(jié)構(gòu)地局限性。7.2.1圖地順序存儲(chǔ)結(jié)構(gòu)——鄰接矩陣圖地鄰接矩陣存儲(chǔ)結(jié)構(gòu):#defineMAX_VERTEX_NUM20//最大頂點(diǎn)數(shù)constintinfinity=INT_MAX;//無窮大structArcCell{ intadj;//對(duì)無權(quán)圖有1,0表示是否相鄰,對(duì)帶權(quán)圖,則為權(quán)值類型 char*info;//該弧地有關(guān)信息};structMGraph{ stringvexs[MAX_VERTEX_NUM];//頂點(diǎn)表 ArcCellarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//鄰接矩陣,即邊表 intvexnum;//頂點(diǎn)數(shù) intarum;//邊數(shù) intkind;//鄰接矩陣存儲(chǔ)地圖地種類};7.2.1圖地順序存儲(chǔ)結(jié)構(gòu)——鄰接矩陣圖地建立:圖頂點(diǎn)號(hào)從1開始計(jì),數(shù)組下標(biāo)按C/C++習(xí)慣從0計(jì)算用鄰接矩陣建立無向圖地算法如下:intGraph::LocateVex(stringu){ for(inti=0;i<MAX_VERTEX_NUM;i++) { if(u==mgraph.vexs[i]){ returni; } } return-1;}7.2.1圖地順序存儲(chǔ)結(jié)構(gòu)——鄰接矩陣boolGraph::CreateUDG(){ inti,j; stringv1,v2; cout<<"請(qǐng)輸入無向圖地頂點(diǎn)個(gè)數(shù),邊地個(gè)數(shù):"; cin>>mgraph.vexnum>>mgraph.arum; cout<<"請(qǐng)輸入各個(gè)頂點(diǎn):"; for(i=0;i<mgraph.vexnum;i++){ cin>>mgraph.vexs[i]; } for(i=0;i<mgraph.vexnum;i++){ for(j=0;j<mgraph.vexnum;j++){ mgraph.arcs[i][j].adj=0; mgraph.arcs[i][j].info=false; } } 7.2.1圖地順序存儲(chǔ)結(jié)構(gòu)——鄰接矩陣 for(i=0;i<mgraph.arum;i++){ cout<<"請(qǐng)輸入一條邊依附地兩個(gè)頂點(diǎn):"; cin>>v1>>v2; intm=LocateVex(v1); intn=LocateVex(v2); mgraph.arcs[m][n].adj=1; mgraph.arcs[n][m].adj=1; } mgraph.kind=2; returntrue;}7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鄰接表是圖地一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。基本思想:鄰接表只存儲(chǔ)有關(guān)聯(lián)地信息,對(duì)圖存在地相鄰頂點(diǎn)之間邊地信息進(jìn)行存儲(chǔ),而對(duì)不相鄰地頂點(diǎn)則不保留信息。設(shè)圖G具有n個(gè)頂點(diǎn),則用頂點(diǎn)數(shù)組表與邊表（弧表）來表示圖G。頂點(diǎn)數(shù)組表:用于存儲(chǔ)頂點(diǎn)vi地名稱或其它有關(guān)信息地?cái)?shù)組,也稱為數(shù)據(jù)域。該數(shù)組地大小為圖地頂點(diǎn)個(gè)數(shù)n。頂點(diǎn)數(shù)組表地?cái)?shù)據(jù)元素也稱為表頭結(jié)點(diǎn)。每個(gè)表頭結(jié)點(diǎn)由兩個(gè)域組成:data:結(jié)點(diǎn)地?cái)?shù)據(jù)域,用于保存結(jié)點(diǎn)地?cái)?shù)據(jù)值firstarc:結(jié)點(diǎn)地指針域,指向指向自該結(jié)點(diǎn)出發(fā)地第一條邊（弧）地邊（?。┙Y(jié)點(diǎn)datafirstarc7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)邊表（弧表）:圖每個(gè)頂點(diǎn)建立一個(gè)單鏈表,第i個(gè)單鏈表地結(jié)點(diǎn)表示依附于頂點(diǎn)vi地邊（對(duì)有向圖是以頂點(diǎn)vi為尾地弧）。該單鏈表地結(jié)點(diǎn)也稱為邊結(jié)點(diǎn)。每個(gè)邊結(jié)點(diǎn)由3個(gè)域組成:adjvex:指示該邊（?。┧赶虻仨旤c(diǎn)在圖地位置（例如頂點(diǎn)在頂點(diǎn)數(shù)組表地下標(biāo)）,也稱為鄰接點(diǎn)域nextarc:邊（?。┙Y(jié)點(diǎn)地指針域,指向下一條邊（?。┙Y(jié)點(diǎn)info:存儲(chǔ)與邊（?。┯嘘P(guān)地信息,如權(quán)值等。若不是網(wǎng),則info域可省去7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)例:有向圖G1adj0123v2^v1v3v412^0^3^adj01234v2v1v3v4v510034^124^4^12^3^無向圖G2鄰接表鄰接表7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)空間:若無向圖有n個(gè)結(jié)點(diǎn),e條邊,若采取鄰接表作為存儲(chǔ)結(jié)構(gòu):無向圖:需求n個(gè)頭結(jié)點(diǎn)與2e個(gè)表結(jié)點(diǎn)。所以在e<<n(n-1)/2地邊稀疏地情況下,用鄰接表表示圖比用鄰接矩陣節(jié)省存儲(chǔ)空間。有向圖:需求n個(gè)頭結(jié)點(diǎn)與e個(gè)表結(jié)點(diǎn)。G11234v2^v1v3v412^0^3^G27.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)圖地度:在無向圖地鄰接表,頂點(diǎn)vi地度恰恰為第i個(gè)單鏈表地結(jié)點(diǎn);在有向圖,第i個(gè)單鏈表地結(jié)點(diǎn)數(shù)只是頂點(diǎn)vi地出度,為求頂點(diǎn)vi地入度,需要遍歷整個(gè)鄰接表,然后在所有單鏈表查找鄰接點(diǎn)地值為i地結(jié)點(diǎn)并計(jì)數(shù)求與。由此可見,對(duì)于用鄰接表存儲(chǔ)地有向圖,求頂點(diǎn)vi地入度并不方便,需求掃描整個(gè)鄰接表才能得到結(jié)果。7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)解決方法:建立有向圖地逆鄰接表,即為每個(gè)頂點(diǎn)vi建立一個(gè)所有以頂點(diǎn)vi為弧頭地邊鏈表。這樣求頂點(diǎn)vi地入度即是計(jì)算逆鄰接表第i個(gè)頂點(diǎn)地邊鏈表結(jié)點(diǎn)地個(gè)數(shù)。01234v2v1v3v43^0^2^0^有向圖G1地逆鄰接表表示7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有向圖鄰接表建立算法步驟:1）輸入所要?jiǎng)?chuàng)建地有向圖地頂點(diǎn)個(gè)數(shù),邊地個(gè)數(shù)與弧地有關(guān)信息。2）初始化頂點(diǎn)集3）依次輸入每一條邊（或弧）地信息,構(gòu)造表結(jié)點(diǎn)鏈表7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)十字鏈表:是有向圖地一種鏈?zhǔn)酱鎯?chǔ)方法。十字鏈表可以看成將鄰接表與逆鄰接表結(jié)合起來得到地一種新地鏈表。在十字鏈表,對(duì)應(yīng)于有向圖每一條弧有一個(gè)弧結(jié)點(diǎn),對(duì)應(yīng)于圖地每個(gè)頂點(diǎn)也有一個(gè)頂點(diǎn)結(jié)點(diǎn),其結(jié)構(gòu)如下:tailvexheadvexhlinkthinkinfo弧結(jié)點(diǎn)tailvexheadvexhlinktlinkinfodatafirstinfirstout頂點(diǎn)結(jié)點(diǎn)7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)tailvexheadvexhlinktlinkinfo弧結(jié)點(diǎn)tailvex域:弧尾結(jié)點(diǎn),即弧尾在頂點(diǎn)表地下標(biāo)。headvex域:弧頭結(jié)點(diǎn),即弧頭在頂點(diǎn)表地下標(biāo)。hlink域:指向弧頭相同地下一條弧。tlink域:指向弧尾相同地下一條弧。info域:存儲(chǔ)該弧地有關(guān)信息。tailvex域:弧尾結(jié)點(diǎn),即弧尾在頂點(diǎn)表地下標(biāo)。7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)datafirstinfirstout頂點(diǎn)結(jié)點(diǎn)data域:存儲(chǔ)與該頂點(diǎn)有關(guān)地信息。firstout域:指向以該頂點(diǎn)為弧尾地第1個(gè)弧結(jié)點(diǎn)。firstin域:指向以該頂點(diǎn)為弧頭地第1個(gè)弧結(jié)點(diǎn)。7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)若將有向圖地鄰接矩陣看成稀疏矩陣地話,則十字鏈表也可以看成鄰接矩陣地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。有向圖G有向圖G地十字鏈表7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)弧結(jié)點(diǎn)tailvexheadvexhlinktlinkinfodatafirstinfirstout頂點(diǎn)結(jié)點(diǎn)#defineMAX_VERTEX_NUM20#defineMAX_INFO10structArcBox{ inttailvex,headvex; ArcBox*hlink,*tlink; char*info;};structVexNode{ stringdata; ArcBox*firstin,*firstout;};structOLGraph{ VexNodexlist[MAX_VERTEX_NUM]; intvexnum,arum;};7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鄰接多重表:是無向圖地一種鏈?zhǔn)酱鎯?chǔ)方式。鄰接多重表地存儲(chǔ)結(jié)構(gòu)與十字鏈表類似,在鄰接多重表,每一條邊用一個(gè)邊結(jié)點(diǎn)表示,其存儲(chǔ)結(jié)構(gòu)如下圖所示。markivexilinkjvexjlinkinfomark:代表域,可以標(biāo)記該邊是否被搜索過。ivex,jvex:與該邊依附地兩個(gè)頂點(diǎn)在頂點(diǎn)表地下標(biāo)。ilink,jlink:指針域,分別指向下一條依附于頂點(diǎn)ivex,jvex地邊。info:存儲(chǔ)與邊有關(guān)地各種信息。datafirstedgedata:存儲(chǔ)與該點(diǎn)有關(guān)地信息。firstedge:指示第一條依附于該頂點(diǎn)地邊。7.2.2圖地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)v1v2v3v4v501010^3^212341^4^2^在鄰接多重表,所有依附于同一頂點(diǎn)地邊結(jié)點(diǎn)串聯(lián)在同一鏈表,由于每條邊依附于兩個(gè)頂點(diǎn),因此每個(gè)邊結(jié)點(diǎn)同時(shí)鏈接在兩個(gè)鏈表。第七章圖7.1圖地基本概念7.2圖地存儲(chǔ)結(jié)構(gòu)7.3圖地遍歷7.4最小生成樹7.5有向無環(huán)圖與其應(yīng)用7.6最短路徑7.3圖地遍歷圖地遍歷是指給定一個(gè)圖G與其任意一個(gè)頂點(diǎn)v0,從v0出發(fā),沿著圖各邊訪遍圖所有頂點(diǎn),且每個(gè)頂點(diǎn)僅被訪問一次。因?yàn)閳D地任一頂點(diǎn)都可能與其余頂點(diǎn)相鄰接。所以若圖存在回路,則回路上地任一頂點(diǎn)在被訪問之后,都有可能會(huì)沿著回路再次被訪問。為了避免此類重復(fù),需求利用一個(gè)代表數(shù)組visited[0…n-1]記錄頂點(diǎn)是否已被訪問過。與樹結(jié)構(gòu)類似,圖地遍歷算法也有很多種。圖地兩種常見遍歷形式:1.深度優(yōu)先搜索2.廣度優(yōu)先搜索7.3.1深度優(yōu)先搜索深度優(yōu)先搜索（DFS）訪問方式:從圖某個(gè)頂點(diǎn)v出發(fā),作為當(dāng)前頂點(diǎn)。訪問此頂點(diǎn),并設(shè)置該頂點(diǎn)地訪問代表。從v地未被訪問地鄰接點(diǎn)找出一個(gè)作為下一步探查地當(dāng)前頂點(diǎn)。倘若當(dāng)前頂點(diǎn)地所有鄰接點(diǎn)都被訪問過,則退回一步,將前一步訪問地頂點(diǎn)重新取出,作為當(dāng)前探查頂點(diǎn)。重復(fù)上述過程,直至圖地最初指定起點(diǎn)地所有鄰接頂點(diǎn)都被訪問到。7.3.1深度優(yōu)先搜索ABCDEFGHABDHEFCGABCDEFGH深度優(yōu)先生成樹7.3.1深度優(yōu)先搜索深度優(yōu)先搜索遞歸實(shí)現(xiàn):voidGraph::DFSTraverse(intv){ cout<<mgraph.vexs[v];visited[v]=1; for(intj=0;j<mgraph.vexnum;j++) if(mgraph.arcs[v][j].adj==1&&visited[j]==0) DFSTraverse(j);}7.3.1深度優(yōu)先搜索當(dāng)圖為鄰接表時(shí):ABCDEFGHABCDEFGH0123456712^034^056^17^17^27^27^3456^當(dāng)圖為鄰接表時(shí):adjdfs(adj,A)dfs(adj,B)ABdfs(adj,D)Ddfs(adj,H)Hdfs(adj,E)Edfs(adj,F)Fdfs(adj,C)Cdfs(adj,G)G7.3.2廣度優(yōu)先搜索廣度優(yōu)先搜索（BFS）訪問方式:訪問頂點(diǎn)v,設(shè)置訪問代表。依次訪問v地各個(gè)未曾訪問過地鄰接點(diǎn)。依次從這些鄰接點(diǎn)出發(fā)訪問它們地鄰接點(diǎn),并使得"先被訪問地頂點(diǎn)地鄰接點(diǎn)"先于"后被訪問地頂點(diǎn)地鄰接點(diǎn)"被訪問,直至圖所有已被訪問地頂點(diǎn)地鄰接點(diǎn)都被訪問到。若此時(shí)圖尚有頂點(diǎn)未被訪問,則另選圖一個(gè)未曾被訪問過地頂點(diǎn)作為起始點(diǎn),重復(fù)上述過程,直至圖所有頂點(diǎn)都被訪問到為止。7.3.2廣度優(yōu)先搜索v12v1v2v11v3v4v6v10v7v5v8v9圖地廣度優(yōu)先搜索訪問次序:v1v2v12v11v3v6v7v10v4v5v8v9v12v1v2v11v3v4v6v10v7v5v8v9BFS樹適用地?cái)?shù)據(jù)結(jié)構(gòu):隊(duì)列7.3.2廣度優(yōu)先搜索voidGraph::BFSTraverse(intv){ CQueueQ(10); cout<<mgraph.vexs[v]; visited[v]=1; Q.EnQueue(v);//被訪問頂點(diǎn)入隊(duì) while(!Q.Empty()){ v=Q.DeQueue();//將隊(duì)頭元素出隊(duì)并送到v for(intj=0;j<mgraph.vexnum;j++) if(mgraph.arcs[v][j].adj==1&&visited[j]==0){ out<<mgraph.vexs[j]; visited[j]=1; Q.EnQueue(j);} }}7.3.2廣度優(yōu)先搜索v12v1v2v11v3v4v6v10v7v5v8v9v1v2v12v11v12v11v3v6v11v3v6v3v6v7v10v6v7v10v4v7v10v4v5v10v4v5v8v4v5v8v9v5v8v9v8v9v97.3.3連通分量與重連通分量當(dāng)無向圖為非連通圖時(shí),利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法,無法遍歷圖地所有頂點(diǎn),而只能遍歷到該頂點(diǎn)所在最大連通子圖地所有頂點(diǎn),這些頂點(diǎn)構(gòu)成一個(gè)連通分量。在無向圖每一個(gè)連通分量,分別從某個(gè)頂點(diǎn)出發(fā)進(jìn)行一次遍歷,就可以遍歷到無向圖地所有連通分量。7.3.3連通分量與重連通分量圖地鄰接表表示ABCDEFGHIJKLMNOP進(jìn)行DFS遍歷得到非連通圖地連通分量7.3.3連通分量與重連通分量在無向連通圖G,頂點(diǎn)v被稱作一個(gè)關(guān)節(jié)點(diǎn),當(dāng)且僅當(dāng)刪去v以與依附于v地所有邊之后G將被分割成至少兩個(gè)連通分量。一個(gè)沒有關(guān)節(jié)點(diǎn)地連通圖稱為重連通圖。在重連通圖,任何一對(duì)頂點(diǎn)之間至少存在有兩條路徑,在刪去某個(gè)頂點(diǎn)與與該頂點(diǎn)有關(guān)聯(lián)地邊后,也不破壞圖地連通性。7.3.3連通分量與重連通分量一般地,若一個(gè)連通圖G不重連通,它必然包含多個(gè)重連通分量。重連通分量連通圖7.3.3連通分量與重連通分量任一連通圖本身就是一個(gè)重連通分量。為了找出無向連通圖G地各個(gè)重連通分量,可以利用DFS樹。v1v2v3v4v5v6v7v8v9v10從v4出發(fā)進(jìn)行DFS遍歷并得到DFS樹12345678910v9v5v6v3v2v1v7v8v10v47.3.3連通分量與重連通分量由深度優(yōu)先生成樹可得出以下兩類關(guān)節(jié)點(diǎn)地特性:（1）若生成樹地根有兩棵或兩棵以上地子樹,則此根頂點(diǎn)必為關(guān)節(jié)點(diǎn)。因?yàn)閳D不存在連接不同子樹頂點(diǎn)地邊,因此,若刪去根頂點(diǎn),生成樹便變成生成森林。（2）若生成樹某個(gè)非葉子頂點(diǎn)v,其某棵子樹地根與子樹其它結(jié)點(diǎn)均沒有指向v地祖先地回邊,則v為關(guān)節(jié)點(diǎn)。因?yàn)?若刪去v,則其子樹與圖地其它部分被分割開來。第七章圖7.1圖地基本概念7.2圖地存儲(chǔ)結(jié)構(gòu)7.3圖地遍歷7.4最小生成樹7.5有向無環(huán)圖與其應(yīng)用7.6最短路徑7.4.1最小生成樹地定義連通圖地每一棵生成樹,都是原圖地極小連通子圖,也就是原圖地一個(gè)極大無環(huán)子圖,它包含原圖地所有頂點(diǎn),而且有盡可能少地邊。這意味著對(duì)于生成樹來說,若刪除它地一條邊,就會(huì)使該生成樹變成非連通圖;若給它增加一條邊,就會(huì)形成圖地一個(gè)回路。按照不同地遍歷算法,得到地生成樹不同;從不同地頂點(diǎn)出發(fā),得到地生成樹也有所不同。7.4.1最小生成樹地定義設(shè)G=(V,E)是一個(gè)無向連通網(wǎng),其生成樹上任一條邊地權(quán)值稱為該邊地代價(jià)（Cost）,一棵生成樹地代價(jià)就是樹上各邊代價(jià)之與。在G地所有生成樹,代價(jià)最小地生成樹稱為最小代價(jià)生成樹,簡(jiǎn)稱最小生成樹。124356616555634212435615342最小生成樹例:例:7.4.1最小生成樹地定義按照生成樹地定義,若連通帶權(quán)圖由n個(gè)頂點(diǎn)組成,則其生成樹必含n個(gè)頂點(diǎn)n-1條邊。因此,構(gòu)造最小代價(jià)生成樹地準(zhǔn)則有以下3條。（1）只能使用該網(wǎng)絡(luò)地邊來構(gòu)造最小生成樹。（2）能且只能使用n-1條邊來連接網(wǎng)絡(luò)地n個(gè)頂點(diǎn)。（3）選用地n-1條邊不能產(chǎn)生回路。7.4.2最小生成樹地構(gòu)造算法1.Kruskal算法設(shè)一個(gè)有n個(gè)頂點(diǎn)地連通網(wǎng)絡(luò)N=(V,E)。首先構(gòu)造一個(gè)由這n個(gè)頂點(diǎn)組成,不含任何邊地圖T=(V,Φ),其每個(gè)頂點(diǎn)自成一個(gè)連通分量。不斷從E取出代價(jià)最小地一條邊（若有多條,任取其一）,若該邊地兩個(gè)頂點(diǎn)來自T不同地連通分量,則將此邊加入到T,否則舍去此邊選擇下一條代價(jià)最小地邊。依此類推,直到T所有地頂點(diǎn)在同一個(gè)連通分量上為止。7.4.1最小生成樹地定義例:v1v2v3v4v7v5v6v1v2v3v4v7v5v6186523128101520254745681218Kruskal算法構(gòu)造最小生成樹適合于求邊稀疏地網(wǎng)地最小生成樹;實(shí)現(xiàn)時(shí)主要解決回路判定問題7.4.2最小生成樹地構(gòu)造算法2.Prim算法任意給定一個(gè)帶權(quán)連通網(wǎng)絡(luò)N={V,E},T=(U,TE)是G地最小生成樹。算法始終將頂點(diǎn)集合V分為不重疊地兩部分,V=U(V-U),T地初始狀態(tài)為U={u0}(u0∈V),TE=φ,然后重復(fù)執(zhí)行以下操作:在所有u∈U,v∈V-U地邊找出一條代價(jià)最小地邊(u0,v0)并入集合TE,同時(shí)v0并入U(xiǎn),直至U=V為止。此時(shí)TE必有n-1條邊,T就是G地最小生成樹。7.4.1最小生成樹地定義例:v1v2v3v4v7v5v6v1v2v3v4v7v5v61865231281015202547Prim算法構(gòu)造最小生成樹45812186第七章圖7.1圖地基本概念7.2圖地存儲(chǔ)結(jié)構(gòu)7.3圖地遍歷7.4最小生成樹7.5有向無環(huán)圖與其應(yīng)用7.6最短路徑7.5有向無環(huán)圖與其應(yīng)用一個(gè)無環(huán)地有向圖稱為有向無環(huán)圖。如:DAG圖有向樹有向圖7.5.1AOV網(wǎng)與拓?fù)渑判蛩械毓こ袒蛘吣撤N流程可以分成若干個(gè)小地工程或階段,這些小地工程或階段就稱為活動(dòng)。若以圖地頂點(diǎn)來表示活動(dòng),有向邊表示活動(dòng)之間地優(yōu)先關(guān)系,則這樣活動(dòng)在頂點(diǎn)上地有向圖稱為AOV網(wǎng)。在AOV網(wǎng),若從頂點(diǎn)i到頂點(diǎn)j之間存在一條有向路徑,稱頂點(diǎn)i是頂點(diǎn)j地前驅(qū),或者頂點(diǎn)j是頂點(diǎn)i地后繼。若<i,j>是圖地弧,則稱頂點(diǎn)i是頂點(diǎn)j地前驅(qū),頂點(diǎn)j是頂點(diǎn)i地后繼。7.5.1AOV網(wǎng)與拓?fù)渑判蛘n程代號(hào)課程名稱先修課C1程序設(shè)計(jì)基礎(chǔ)無C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1,C2C4語(yǔ)言地設(shè)計(jì)與分析C1C5計(jì)算機(jī)原理C3,C4C6程序設(shè)計(jì)基礎(chǔ)C11C7編譯原理C3,C5C8操作系統(tǒng)C3,C6C9高等數(shù)學(xué)無C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C1,C9,C10C1C2C3C4C5C7C8C9C10C11C12C6AOV網(wǎng)7.5.1AOV網(wǎng)與拓?fù)渑判蛲負(fù)渑判蚓褪怯赡硞€(gè)集合上地一個(gè)偏序得到該集合上地一個(gè)全序地操作。若集合X上地關(guān)系R滿足自反,反對(duì)稱與傳遞性,則稱R是集合X上地偏序關(guān)系。設(shè)R是集合X上地偏序,如果對(duì)x,y∈X必有xRy或yRx,則稱R是集合X上地全序關(guān)系。AOV網(wǎng)不應(yīng)該出現(xiàn)有向環(huán),因?yàn)榇嬖诃h(huán)意味著AOV網(wǎng)地某項(xiàng)活動(dòng)應(yīng)以自己為先決條件。對(duì)給定地AOV網(wǎng)應(yīng)首先判斷網(wǎng)是否存在環(huán),檢測(cè)方法是構(gòu)造有向圖頂點(diǎn)地拓?fù)溆行蛐蛄小Ｈ魣D所有地頂點(diǎn)都在它地拓?fù)溆行蛐蛄?則該AOV網(wǎng)必定不存在環(huán)。7.5.1AOV網(wǎng)與拓?fù)渑判蛲負(fù)渑判虻亟Y(jié)果并不是唯一地。如:v1v2v3v4v5v6拓?fù)渑判?:{v1,v5,v4,v3,v2,v6}拓?fù)渑判?:{v5,v1,v4,v3,v2,v6}7.5有向無環(huán)圖與其應(yīng)用構(gòu)造有向圖頂點(diǎn)地拓?fù)渑判虻夭襟E如下。（1）在有向圖選一個(gè)沒有前驅(qū)地頂點(diǎn),輸出之。（2）從圖刪除該頂點(diǎn)以與從該點(diǎn)出發(fā)地全部有向邊。（3）重復(fù)上述兩步,直至全部頂點(diǎn)均已輸出,或者當(dāng)前圖不 存在無前驅(qū)地頂點(diǎn)。v1v3v6v5v2v4v1v2v3v4v5v6v7輸出:v77.5.1AOV網(wǎng)與拓?fù)渑判蛲負(fù)渑判蛩惴ǖ貙?shí)現(xiàn):采用鄰接表作為有向圖地存儲(chǔ)結(jié)構(gòu),并在頭結(jié)點(diǎn)增加一個(gè)存放頂點(diǎn)入度地?cái)?shù)組。入度為0地頂點(diǎn)即為沒有前驅(qū)地頂點(diǎn);刪除結(jié)點(diǎn)與從它出發(fā)地全部有向邊地操作,可以用弧頭頂點(diǎn)入度減1地方式來實(shí)現(xiàn)。1234567123456^7^4^345^67^7^7^0123456adj00121131234567indegree對(duì)應(yīng)結(jié)點(diǎn)號(hào):123456^7^4^345^67^7^7^7.5.1AOV網(wǎng)與拓?fù)渑判蛩惴枋?（1）把鄰接表入度為0地頂點(diǎn)依此進(jìn)棧（2）若棧不空,則棧頂元素vj退棧并輸出;在鄰接表查找vj地直接后繼vk,把vk地入度減1;若vk地入度為0則進(jìn)棧

若?？諘r(shí)輸出地頂點(diǎn)個(gè)數(shù)不是n,則有向圖有環(huán);否則,拓?fù)渑判蛲戤叀?.5.1AOV網(wǎng)與拓?fù)渑判騜oolALGraph::TopologicalSort(){inti,k,count=0;intindegree[MAX_VERTEX_NUM];SqStacks(20);Arode*p;FindInDegree(indegree); for(i=0;i<algraph.vexnum;i++){ if(!indegree[i]){ s.Push(i); } }7.5.1AOV網(wǎng)與拓?fù)渑判騱hile(!s.StackEmpty{ i=s.Pop(); cout<<algraph.vertices[i].data<<""; count++; for(p=algraph.vertices[i].firstarc;p;p=p->nextarc){ k=p->adjvex; if(!(--indegree[k])){ s.Push(k); } } }7.5.1AOV網(wǎng)與拓?fù)渑判?if(count<algraph.vexnum){ cout<<"此有向圖有回路"<<endl; returnfalse; } else{ cout<<"為一個(gè)拓?fù)湫蛄?<<endl; returntrue; }}7.5.1AOV網(wǎng)與拓?fù)渑判?23456^7^4^345^67^7^7^indegree對(duì)應(yīng)結(jié)點(diǎn)號(hào):adj0123456001211312345670棧167210451020343210056輸出:7.5.2AOE網(wǎng)與關(guān)鍵路徑AOE網(wǎng),即邊表示活動(dòng)地網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)地有向無環(huán)圖。其,頂點(diǎn)表示事件,弧表示活動(dòng),權(quán)表示活動(dòng)持續(xù)地時(shí)間。通常,AOE網(wǎng)可以用來表示工程地進(jìn)度計(jì)劃。源點(diǎn):表示整個(gè)工程地開始點(diǎn)（入度為0）。匯點(diǎn):表示整個(gè)工程地完成點(diǎn)（出度為0）;活動(dòng)（有向邊）:它地權(quán)值定義為活動(dòng)進(jìn)行所需求地時(shí)間。方向表示事件地優(yōu)先關(guān)系。7.5.2AOE網(wǎng)與關(guān)鍵路徑關(guān)鍵路徑:從源點(diǎn)到匯點(diǎn)地最長(zhǎng)路徑地長(zhǎng)度事件地最早開始時(shí)間（e(i)）:從v1到vi地最長(zhǎng)路徑長(zhǎng)度事件地最遲開始時(shí)間（l(i)）:在不推遲整個(gè)工程完成地前提下,活動(dòng)ai最遲需要開始地時(shí)間時(shí)間余量:l(i)-e(i)地差關(guān)鍵活動(dòng):時(shí)間余量為0地活動(dòng)活動(dòng)ai由弧<j,k>表示,持續(xù)時(shí)間記為dut<j,k>,則有:jkaidut<j,k>活動(dòng)地最早開始時(shí)間:e(i)=ve(j)活動(dòng)地最遲開始時(shí)間:l(i)=vl(k)-dut(<j,k>)7.5.2AOE網(wǎng)與關(guān)鍵路徑ve(j)與vl(j)地求法:(1)從ve(0)=0開始向前遞推i1i2jim6754910其,T是所有以第j個(gè)頂點(diǎn)為頭地弧地集合7.5.2AOE網(wǎng)與關(guān)鍵路徑(2)從vl(n-1)=ve(n-1)起向后遞推j1j2ijm1518207910

=n-2,…,0其,S是所有以i個(gè)頂點(diǎn)為尾地弧地集合求關(guān)鍵路徑例子:98645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a11=47a10=2V1V2V3V4V5V6V7V8V9頂點(diǎn)VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng)ell-e00002266046258377077071031616014140033活動(dòng)地最早開始時(shí)間:e(i)=ve(j)活動(dòng)地最遲開始時(shí)間:l(i)=vl(k)-dut(<j,k>)作業(yè)列出下面AOE網(wǎng)地關(guān)鍵路徑αωAJHIGFECDBK68101634312712610511864499321第七章圖7.1圖地基本概念7.2圖地存儲(chǔ)結(jié)構(gòu)7.3圖地遍歷7.4最小生成樹7.5有向無環(huán)圖與其應(yīng)用7.6最短路徑7.6最短路徑一個(gè)交通咨詢網(wǎng)絡(luò)采用圖結(jié)構(gòu)表示,圖:頂點(diǎn)——表示城市邊——城市間地交通路線權(quán)——兩個(gè)城市間地距離在帶權(quán)圖,則把從一個(gè)頂點(diǎn)到圖其余任一個(gè)頂點(diǎn)地一條路徑上所通過邊上地權(quán)值之與定義為該路徑地帶權(quán)圖路徑長(zhǎng)度,由于可能不止一條路徑,因此把帶權(quán)圖路徑長(zhǎng)度最短（權(quán)值最?。┑啬菞l路徑也稱作最短路徑,其權(quán)值之與也稱作最短路徑或最短路徑長(zhǎng)度7.6.1單源最短路徑單源最短路徑問題:給定帶權(quán)有向圖G與源點(diǎn)v,求從v到G其余各點(diǎn)地最短路徑。迪杰斯特拉(Dijkstra)算法:按路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑輔助數(shù)組:dist[]:存放集合S內(nèi)頂點(diǎn)到S外各頂點(diǎn)地路徑上地當(dāng)前最小權(quán)值。path[]:記錄頂點(diǎn)是否已加入集合S。7.6.1單源最短路徑v1v3v4v5v2v6v7327171013265830設(shè)一個(gè)集合S,記錄已求得最短路徑地頂點(diǎn),初始時(shí)把源點(diǎn)u0放入S。序號(hào)v1v2v3v4v5v6v7dist值138∞30∞32path值-1000000第一條路:v1到v2,v3,v5,v7之一取path[i]≠-1且dist[i]最小,為3,將v3加入到S第二條路:v1到v2,v4,v5,v7之一。且,v3加到S后,某些頂點(diǎn)地dist與v3地path值應(yīng)調(diào)整13-1如果下一條最短路徑到達(dá)頂點(diǎn)x,則從源點(diǎn)到x地間點(diǎn)必定都在S算法實(shí)現(xiàn)分析7.6.1單源最短路徑Dijkstra算法描述圖用鄰接矩陣表示,設(shè)置集合S與輔助數(shù)組dist[],path[]。源點(diǎn)u0圖地頂點(diǎn)數(shù)為n。(1)在dist[]選擇path[i]≠-1且dist[i]最小地邊i,用v標(biāo)記它(2)將path[v]改成-1,表示它已加入集合S。將邊(path[v],v,dist[v])加入生成樹地邊集合。(3)取dist[i]=min{dist[i],Edge[v][i]}(4)如果從集合S外頂點(diǎn)i到剛加入該集合地頂點(diǎn)v地距離比原來它到集合S頂點(diǎn)地最短路徑還要近,則修改nearestx[i]=v17v1