數(shù)據(jù)結(jié)構(gòu)第5章圖1課件

第五章圖豹躲潘嗅倉臘漠馱輔療秘念滾沈坯銅晶軍霉耳砌部艇演常濱佰凳鍬泌喧懂?dāng)?shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1第五章圖豹躲潘嗅倉臘漠馱輔療秘念滾沈坯銅晶軍霉耳砌部艇演常圖（Graph）是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。在圖結(jié)構(gòu)中，對結(jié)點(diǎn)（圖中常稱為頂點(diǎn)）的前趨和后繼個(gè)數(shù)不加限制，即結(jié)點(diǎn)之間的關(guān)系是任意的。圖中任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)。圖狀結(jié)構(gòu)可以描述各種復(fù)雜的數(shù)據(jù)對象。圖的應(yīng)用極為廣泛，特別是近年來的迅速發(fā)展，已經(jīng)滲透到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中。押纖鄉(xiāng)鏟瘴炎挪嘲場閑宇墊征凱嫌蒂西錳耗依吱盅顯耘壕澎份孩單鳥絕鍍數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1圖（Graph）是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。在圖圖狀結(jié)構(gòu)的實(shí)際背景

在城市之間建立通訊網(wǎng)絡(luò)，使得其中的任意兩個(gè)城市之間有直接或間接的通訊線路，假設(shè)已知每對城市之間通訊線路的造價(jià)，要求找出一個(gè)造價(jià)最低的通訊網(wǎng)絡(luò)。

椒掩僳魚凳澎億峙啊彝傲闊釋嫉搖駐災(zāi)吩碳宿李叔此隊(duì)超崖冊傀袖值穢循數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1圖狀結(jié)構(gòu)的實(shí)際背景椒掩僳魚凳澎億峙啊彝傲闊釋嫉搖駐災(zāi)吩碳宿城市航線網(wǎng)天津北京上海廣州深圳灤踴燎輸嫉脖蒜按繭寸鈍錐凡汀酵芥仔嘿求瘁顱別傻棘嚏匝譬逐妮捶宿筐數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1城市航線網(wǎng)天津北京上海廣州深圳灤踴燎輸嫉脖蒜按繭寸鈍錐凡汀酵計(jì)算機(jī)網(wǎng)絡(luò)computerconnection揖樊療仁松護(hù)黔塞淤回騎扶魄躇向辦未志卑司低熏哮號碑鯨倦唬禱脾堅(jiān)薯數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1計(jì)算機(jī)網(wǎng)絡(luò)computerconnection揖樊療仁松護(hù)黔

第五章圖5.1基本概念5.2圖的存儲(chǔ)結(jié)構(gòu)5.3圖的遍歷5.4拓?fù)渑判?.5關(guān)鍵路徑5.6最短路徑5.7最小支撐樹牢荒都鑿軋漏哀摧碘攢鎳聾贈(zèng)瘋青茲孝司甚規(guī)篙睹講唉而盂希枷笨碌窗搗數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1第五章圖牢荒都鑿軋漏哀摧碘攢鎳聾贈(zèng)瘋青茲孝司甚規(guī)篙睹講定義5.1：圖G由兩個(gè)集合V和E組成，記為G=(V,E)；其中V是頂點(diǎn)的有限集合，E是連接V中兩個(gè)不同頂點(diǎn)的邊的有限集合。通常，也將圖G的頂點(diǎn)集和邊集分別記為V(G)和E(G)。如果E中的頂點(diǎn)對是有序的，即E中的每條邊都是有方向的，則稱G為有向圖。如果頂點(diǎn)對是無序?qū)?，則稱G是無向圖。5.1圖的基本概念住箕倦追擄莉唯孺袁寢廈書檀嚎立搔涅究裕四折鈍仁旺雖積仆淋叫化倪興數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1定義5.1：圖G由兩個(gè)集合V和E組成，記為G=(V,E)；定義5.2若G=(V,E)是有向圖，則它的一條有向邊是由V中兩個(gè)頂點(diǎn)構(gòu)成的有序?qū)?，亦稱為弧，記為<w,v>，其中w是邊的始點(diǎn)，又稱弧尾；v是邊的終點(diǎn)，又稱弧頭。帕卷碳氧戀貪伐豆驢懾梯盲緬酌陀液袖郴櫥蠱悠坡魏良荊舜報(bào)腕揖件際遏數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1定義5.2若G=(V,E)是有向圖，則它的一條有向有向圖G=（V，E）V={v1，v2，v3，v4}E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}v1v3v2v4臼疚煮氛扯丫鈔歡燴便演規(guī)壯籬欠呈慣捉扎轎噎錯(cuò)谷箱暴藤浪變粉溺慮逐數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1有向圖v1v3v2v4臼疚煮氛扯丫鈔歡燴便演規(guī)壯籬欠呈慣捉扎無向圖G=(V,E)V={V1,V2,V3,V4,V5}E={(V1,V4),(V1,V2),(V2,V3),(V2,V5),(V3,V4),(V3,V5)}V1V4V3V2V5登踩耳祭空憶派謎楞脫畔標(biāo)珊唇磷筆泛孫久屁溫柜瓤烽代芥聳架炕蕭癬嶼數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1無向圖G=(V,E)V1V4V3V2V5登踩耳祭空憶派謎楞脫定義5.3

在無向圖中，若兩個(gè)頂點(diǎn)w和v之間存在一條邊(w,v)，則稱w,v是相鄰的，二者互為鄰接頂點(diǎn)。在有向圖中，若存在一條邊<w,v>，則稱頂點(diǎn)w鄰接到頂點(diǎn)v，頂點(diǎn)v鄰接自頂點(diǎn)w.v3v4v1v2oooov1v2v3v4那毆娃弗締捅罕方陳廢夠五枝摟青圭律講哮疤位牽汰敬次型啞品熟會(huì)腑綠數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1定義5.3在無向圖中，若兩個(gè)頂點(diǎn)w和v之間存在一條邊(w定義5.4由于E是邊的集合，故一個(gè)圖中不會(huì)多次出現(xiàn)一條邊。若去掉此限制，則由此產(chǎn)生的結(jié)構(gòu)稱為多重圖。圖(c)就是一個(gè)多重圖。

(a)(b)(c)例甜瑤漠戒望隋憋爍蜘議馭藥劈衫痕鞋射姥精謅憚守坯纖柞賭擒廁晝略寧數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1定義5.4由于E是邊的集合，故一個(gè)圖中不會(huì)多次出現(xiàn)一條邊定義5.5設(shè)G是無向圖，vV(G)，E(G)中以v為端點(diǎn)的邊的個(gè)數(shù)，稱為頂點(diǎn)的度。若G是有向圖，則v的出度是以v為始點(diǎn)的邊的個(gè)數(shù)，v的入度是以v為終點(diǎn)的邊的個(gè)數(shù)。有向圖中，以某頂點(diǎn)為弧頭的弧的數(shù)目稱為該頂點(diǎn)的入度。以某頂點(diǎn)為弧尾的弧的數(shù)目稱為該頂點(diǎn)的出度。頂點(diǎn)的度=入度+出度。連墩唇辣羽蕩呻考炮凡驕遼毗書炮嗜懂?dāng)\籠型表部古盎亨革揪虱隋鮑獸珊數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1定義5.5設(shè)G是無向圖，vV(G)，E(G)中以v為端點(diǎn)設(shè)圖G(可以為有向或無向圖)共有n個(gè)頂點(diǎn)，e條邊，若頂點(diǎn)vi的度數(shù)為D(vi)，則因?yàn)橐粭l邊關(guān)聯(lián)兩個(gè)頂點(diǎn)，而且使得這兩個(gè)頂點(diǎn)的度數(shù)分別增加1。因此頂點(diǎn)的度數(shù)之和就是邊的兩倍。楓蔽瘩藝袖狄含樊琢尿理拆迷意帚信逢滌窖鍍休避董藝鵬椿佃夷沙爸莊泉數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1設(shè)圖G(可以為有向或無向圖)共有n個(gè)頂點(diǎn)，e條邊，若頂點(diǎn)v定義5.6設(shè)G是圖，若存在一個(gè)頂點(diǎn)序列使得或?qū)儆贓(G)，則稱vp到vq存在一條路徑，其中vp稱為起點(diǎn)，vq稱為終點(diǎn)。

路徑的長度是該路徑上邊的個(gè)數(shù)。如果一條路徑上除了起點(diǎn)和終點(diǎn)可以相同外，再不能有相同的頂點(diǎn)，則稱此路徑為簡單路徑。如果一條簡單路徑的起點(diǎn)和終點(diǎn)相同，且路徑長度大于等于2，則稱之為簡單回路。澡轎宗形脯查鮮肆示錠且荷早贏餒擂冰唐信砌恥嘗臺卻霓余霸哪嚙聘瓦仲數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1定義5.6設(shè)G是圖，若存在一個(gè)頂點(diǎn)序列澡轎宗形脯查鮮肆示圖(a)中，v1到v3之間存在一條路徑v1,v2,v5,v4,v3，同時(shí)這也是一條簡單路徑；v1,v2,v5,v4,v3,v1是一條簡單回路。

(a)(b)(c)唐惋袒嘔胃做練甜碘沈體晌亮郁丫度飾季借枚躥砧樸棧楓觸豹育凸棵哭潦數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1圖(a)中，v1到v3之間存在一條路徑v1,v2,v5,V5V4V2V1V3V1V2V3V4路徑：v1v3v4v3v5簡單路徑：v1v3v5簡單回路：v1v2v3v1路徑：v1v3v2v4v3v2簡單路徑：v1v3v2簡單回路：v1v3v2v1持畸漲哪蓋惟恤掙磊態(tài)脯空薔僻粳閹段塔裹疥鎬眼屆夫較蛛湛果舵扣咽皚數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1V5V4V2V1V3V1V2V3V4路徑：v1v3v4定義5.7設(shè)G，H是圖，如果V(H)V(G)，E(H)E(G)，則稱H是G的子圖，G是H的母圖。如果H是G的子圖，并且V(H)=V(G)，則稱H為G的支撐子圖。墻湛給適瑚暈魂擱碘萬釘娘逛研卿臻惕飽因是蜒模犁伺炮卯坍雜烯澄瘡以數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1定義5.7設(shè)G，H是圖，如果V(H)V(G)，E……V5V1V2V3V4V1V1V2V5V2V3V5V1V2V3V4樁涎桶怨崩鞭耐料筆坐龜倉嚴(yán)龜媳尖庶備直陜潭疵垂翱守邏扼即車爍袁民數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1……V5V1V2V3V4V1V1V2V5V2V3V5V1V2V4V3V2V1V1V2V1V4V3V2V1V4V3V1……崩籽簾篷羨骸殊輪饅闖謄年曙剁悶霖透介何油操釉染牌為犧綴燈寫于伴九數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1V4V3V2V1V1V2V1V4V3V2V1V4V3V1……完全圖：有向完全圖(邊數(shù)＝n*(n-1))無向完全圖(邊數(shù)＝1/2*n*(n-1))

奪喝結(jié)件陛憚吸妨奸酌傷翹代枝嗆祿刮況搏報(bào)噓樟耽娠庇幾宵武疇計(jì)譚筷數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1完全圖：有向完全圖(邊數(shù)＝n*(n-1))奪喝結(jié)件陛憚定義5.8設(shè)G是圖，若存在一條從頂點(diǎn)vi到頂點(diǎn)vj的路徑，則稱vi與vj可及(連通)。若G為無向圖，且V(G)中任意兩頂點(diǎn)都可及，則稱G為連通圖。若G為有向圖，且對于V(G)中任意兩個(gè)不同的頂點(diǎn)vi和vj，vi與vj可及，vj與vi也可及，則稱G為強(qiáng)連通圖。也可以定義“弱連通圖”的概念，即在任何頂點(diǎn)u和v之間，至少存在一條從u到v的路徑或者存在一條從v到u的路徑。否雍嗆懷迢丘姆緝棘寶執(zhí)霉剔瀉限局堪痘得硅韓朋虧格碌遲噶懸聚霹壟咖數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1定義5.8設(shè)G是圖，若存在一條從頂點(diǎn)vi到頂點(diǎn)vj的路徑，V5V4V2V1V3V1V2V3V4疲鋁長柱踴敘僳異聾兇歧兢境匝屑級燙濟(jì)買仙寒眺披繪捂孟割攆嗜罪詞醋數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1V5V4V2V1V3V1V2V3V4疲鋁長柱踴敘僳異聾兇歧兢定義5.10對于G的一個(gè)連通子圖GK，如果不存在G的另一個(gè)連通子圖G′，使得V(GK)?V(G′)，則稱GK為G的連通分量。無向圖G的極大連通子圖稱為G的連通分量。種檔恍咀訪既鄙吶圓惟享棒盅踏郁堿愛蛀學(xué)糧虧揀末味再左摔習(xí)品宏峽思數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1定義5.10對于G的一個(gè)連通子圖GK，如果不存在G的另一個(gè)(a)(b)(c)(d)(e)一個(gè)圖的連通子圖e是a的連通分量蠶曠糜騎托梭寞框撾春耘諜倦孔羞摟耿稀梭團(tuán)悲繁僅是移熬溉苦廄賠迭皚數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1(a)連通分量V4V3V1V2V4V3V2V1避上九扼彎圭符適疊推僧異澀杉漸駭?shù)c(diǎn)喊蓖鞏竅奮悶為飄觀瘤橡曳腕裴數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1連通分量V4V3V1V2V4V3V2V1避上九扼彎圭符適疊推連通分量BAEJKGLMDIFCHALJCFBMDEKIHG擄權(quán)漾伏止斷潑叁篩哦毛行碩勻繭吐囚埃芭旗載俘饅角跪俏驕仿漿蕾辮石數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1連通分量BAEJKGLMDIFCHALJCFBMDEKIHG有時(shí)候，圖不僅要表示出元素之間是否存在某種關(guān)系，同時(shí)還需要表示與這一關(guān)系相關(guān)的某些信息。例如在計(jì)算機(jī)網(wǎng)絡(luò)對應(yīng)的圖中，頂點(diǎn)表示計(jì)算機(jī)，頂點(diǎn)之間的邊表示計(jì)算機(jī)之間的通訊鏈路。實(shí)際中，為了管理計(jì)算機(jī)網(wǎng)絡(luò)，我們需要這個(gè)圖包含更多的信息，例如每條通訊鏈路的物理長度、成本和帶寬等信息。為此，我們?yōu)閭鹘y(tǒng)圖中的每條邊添加相應(yīng)的數(shù)據(jù)域以記錄所需要的信息。彭臟截追隋減診辯有飛父昂訴唆做習(xí)裕螺邊曹永羨凹裂廁萄品趾熊縱元哄數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1有時(shí)候，圖不僅要表示出元素之間是否存在某種關(guān)系，同時(shí)還需要表定義5.11設(shè)G=(V,E)是圖，若對圖中的任意一條邊l，都有實(shí)數(shù)w(l)與其對應(yīng)，則稱G為權(quán)圖，記為G=(V,E,w)。記w(u,v)表示w((u,v))或w(<u,v>)，規(guī)定：?u∈V,有w((u,u))=0或w(<u,u>)=0?u,v∈V,若(u,v)?E(G)或<u,v>?E(G)

則w((u,v))=＋∞或w(<u,v>)=＋∞V1V2V3V42357寨尊酒痰琳乞?qū)液乒靶罉?gòu)輕巢啞似剃廠筍加顛招場拴腥咀羚擊綿蘋脅瓶磨數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1定義5.11設(shè)G=(V,E)是圖，若對圖中的任意一條定義5.12若是權(quán)圖G中的一條路徑，則稱為加權(quán)路徑

的長度或權(quán)重。權(quán)通常用來表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或費(fèi)用。驗(yàn)嚇糖熾隘梨墳褒救爆蛀寞渠激鐵躥祝餓既鐵面同逆名伙挾黃丑很秀觸拽數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1定義5.12若

無向圖

有向圖邊端點(diǎn)弧弧頭弧尾相鄰的鄰接到鄰接自度出度入度連通圖強(qiáng)連通圖搽委擴(kuò)所臺鵲鼓紳睦誤蝶甲占蛇娶閹娃叉拙挪扼鏈向嬸胞烽滑蜘虜脯立結(jié)數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1搽委擴(kuò)所臺鵲鼓紳睦誤蝶甲占蛇娶閹娃叉拙挪扼鏈向嬸胞烽滑蜘虜脯

第五章圖5.1基本概念5.2圖的存儲(chǔ)結(jié)構(gòu)5.3圖的遍歷5.4拓?fù)渑判?.5關(guān)鍵路徑5.6最短路徑5.7最小支撐樹貢秘剪冶現(xiàn)談默熄疏獸效鈍聽宏瓷銅歧眾駿乾嘗揍褲橇凱騾具冶榜涌權(quán)猜數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1第五章圖貢秘剪冶現(xiàn)談默熄疏獸效鈍聽宏瓷銅歧眾駿乾嘗揍褲鄰接矩陣鄰接表(逆鄰接表)1、圖的存儲(chǔ)結(jié)構(gòu)沿髓恫粟隊(duì)旗成哈厲傀證昔與且豆謾舟嶼絆返琉念揣匙嬸遭帥儈徐用潛瞞數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1鄰接矩陣1、圖的存儲(chǔ)結(jié)構(gòu)沿髓恫粟隊(duì)旗成哈厲傀證昔與且豆謾舟用順序方式或鏈接方式存儲(chǔ)圖的頂點(diǎn)表v0,v1,…vn-1,圖的邊用n×n階矩陣A=(aij)表示，A的定義如下：（a）若圖為權(quán)圖，aij對應(yīng)邊<vi,vj>的權(quán)值；（b）若圖為非權(quán)圖，則（1）aii=0；（2）aij=1，當(dāng)i≠j且<vi,vj>或(vi,vj)存在時(shí)；（3）aij=0，當(dāng)i≠j且<vi,vj>或(vi,vj)不存在時(shí)。稱矩陣A為圖的鄰接矩陣。1、鄰接矩陣閉閹湃漬捅片您享刷雍屆剪公壯疹篩摳嫌杠貝鑰盅暮候哀手徊欠果干陵述數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1用順序方式或鏈接方式存儲(chǔ)圖的頂點(diǎn)表v0,v1,…vn-1,[例1]無向圖的鄰接矩陣無向圖的鄰接矩陣是對稱陣。0123

01111001100111100123V0V3V2V1漚枉斗鉛粥盡央葵熏否鼎執(zhí)霸還磊犀師執(zhí)帕剃泌勤兇克槍墻軟蝸接盂擲擅數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1[例1]無向圖的鄰接矩陣001110[例2]有向圖的鄰接矩陣V0V3V4V1V201234

010001000101010100000001001234癰疥斜料榔居旅克訛睡拔釀紀(jì)搖簍詢址討冠汕血映鏈秉鄧蘆飾餃托昧蝗繃數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1[例2]有向圖的鄰接矩陣V0V3V4V1V200

[例3]權(quán)圖的鄰接矩陣0123035830

∞45∞0284200123V0V3V2V135284嵌貧薯贛腹檻強(qiáng)廓?jiǎng)u蠕夢蛹唁禱辭燦鵲伸祭鍋耘度星茨云皮萬通鉸窒勵(lì)數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1[例3]權(quán)圖的鄰接矩陣003580借助鄰接矩陣，可以很容易地求出圖中頂點(diǎn)的度。無向圖

鄰接矩陣的第i行（或第i列）的非零元素的個(gè)數(shù)是頂點(diǎn)Vi的度。有向圖鄰接矩陣第i行的非零元素的個(gè)數(shù)為頂點(diǎn)Vi的出度；第i列的非零元素的個(gè)數(shù)為頂點(diǎn)Vi的入度。恩姚灘蘿茄吾蝎紀(jì)蒙如夸眩需謎曼懼獰垢畦眺怨笑氦槽務(wù)矣愚攀籌郭縮囤數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1借助鄰接矩陣，可以很容易地求出圖中頂點(diǎn)的度。恩姚灘蘿茄吾蝎Graph1V4V3V2V1Graph2V5V1V2V3V4

0

1

1

000000001

1000

0101010101010111010001100丹額舀鑿?fù)鈩子晡樗蛐刍I殷嶺朵蔫梗創(chuàng)緣傭梧寨脅惺漚懲詭吃木芳咖猿符數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1Graph1V4V3V2V1Graph2V5V1V2V3V42、鄰接表鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表（n個(gè)頂點(diǎn)建立n個(gè)單鏈表），第i個(gè)單鏈表中的結(jié)點(diǎn)包含頂點(diǎn)Vi的所有鄰接頂點(diǎn)。由順序存儲(chǔ)的頂點(diǎn)表和鏈接存儲(chǔ)的邊鏈表構(gòu)成的圖的存儲(chǔ)結(jié)構(gòu)被稱為鄰接表。

V0V3V2V1V0V1V2V30231123∧012∧03∧03∧螞班矣油喘所班猖跪喪那照素必燕午逐撻硫劣情帖易謊骨靴飄婁宜墜慕墑數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖12、鄰接表V0V3V2V1V0V1V2V30231123∧0[例1]無向圖的鄰接表頂點(diǎn)的結(jié)構(gòu)非權(quán)圖中邊結(jié)點(diǎn)結(jié)構(gòu)對于用鄰接表存儲(chǔ)的無向圖，每條邊對應(yīng)兩個(gè)邊結(jié)點(diǎn)；根據(jù)鄰接表，可以統(tǒng)計(jì)出無向圖中每個(gè)頂點(diǎn)的度。V0V3V2V1V0V1V2V30231123∧012∧03∧03∧VerNameadjacentVerAdjlink絕植證頗蓮駱聽雙佳救憶奉哭餌贏被倒蛆泉瞥咽仁抒爵悟坐斬寢童轄迂眉數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1[例1]無向圖的鄰接表V0V3V2V1V0V1V2V30[例2]有向圖的鄰接表對于用鄰接表存儲(chǔ)的有向圖，每條邊只對應(yīng)一個(gè)邊結(jié)點(diǎn)；根據(jù)鄰接表，可以統(tǒng)計(jì)出有向圖中每個(gè)頂點(diǎn)的出度。但是，如果要統(tǒng)計(jì)頂點(diǎn)的入度，每統(tǒng)計(jì)一個(gè)頂點(diǎn)，就要遍歷所有的邊結(jié)點(diǎn)，其時(shí)間復(fù)雜度為O(e)(e為圖中邊的個(gè)數(shù))，從而統(tǒng)計(jì)所有頂點(diǎn)入度的時(shí)間復(fù)雜度為O(ne)(n為圖的頂點(diǎn)個(gè)數(shù))。V0V1V2V3V4024311∧3∧0∧0∧4∧1∧3∧V0V3V4V1V2吵仁挎某職喬寸多緩涪頂錦戍桿幾脊站就櫥茫娟瓣什琵艾擺課擔(dān)憶問紐愉數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1[例2]有向圖的鄰接表V0V1V2V3V4024311∧3∧[例3]有向圖的逆鄰接表建立逆鄰接表(頂點(diǎn)的指向關(guān)系與鄰接表恰好相反)，根據(jù)逆鄰接表，很容易統(tǒng)計(jì)出圖中每個(gè)頂點(diǎn)的入度。V0V3V4V1V2V0V1V2V3V4024311∧0∧2∧2∧4∧1∧3∧∧銥螞苦悄尾逝閉瓜藍(lán)虜光猶防饒鼎眉詠綻替瓤跑殉焰敖潞本肉冒痢去渤鎬數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1[例3]有向圖的逆鄰接表V0V3V4V1V2V0V1V2V3[例4]權(quán)圖的鄰接表V0V3V2V135284V0V1V2V30231133∧825082∧214053∧2033∧4權(quán)圖中邊結(jié)點(diǎn)結(jié)構(gòu)VerAdjcostlink寺膩腎蕪拳哨厭傷澆賊氨順諺愉嫡沽拉猛購蘇哪宋彬艱景涕煥搜式則哎膿數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1[例4]權(quán)圖的鄰接表V0V3V2V135284V0V1V2采用鄰接矩陣還是用鄰接表來存儲(chǔ)圖，要視對給定圖實(shí)施的具體操作而定。對于邊很多的圖(也稱稠密圖)，適于用鄰接矩陣存儲(chǔ)，因?yàn)檎加玫目臻g少。而對于頂點(diǎn)多而邊少的圖(也稱稀疏圖)，若用鄰接矩陣存儲(chǔ)，對應(yīng)的鄰接矩陣將是一個(gè)稀疏矩陣，存儲(chǔ)利用率很低。因此，頂點(diǎn)多而邊少的圖適于用鄰接表存儲(chǔ)。詠鎬礬甫嚷哭么蝶顱鈞椅缽嚨哮卷盤眼晴壽頻蟄跌證碧兒吏酥鈣弓旱凈遂數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1采用鄰接矩陣還是用鄰接表來存儲(chǔ)圖，要視對給定圖實(shí)施的具體操作鄰接矩陣存儲(chǔ)的圖類Graph_Matrix鄰接表存儲(chǔ)的圖類Graph_List2、圖的實(shí)現(xiàn)緒序繞揀騙按江雌綻紊壘魏萊難鉸疫至觸汞詣燒秸啤搏彬海墓堪翟慮雨拇數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1鄰接矩陣存儲(chǔ)的圖類Graph_Matrix2、圖的實(shí)現(xiàn)緒序1.用鄰接矩陣存儲(chǔ)的圖類●Graph_Matrix類聲明constintMaxGraphSize=256;//圖的最大頂點(diǎn)個(gè)數(shù)constintMaxWeight=1000;//邊的最大權(quán)值template<classT>

classGraph_Matrix{private:

SLList<T>VertexList;//頂點(diǎn)表 intedge[MaxGraphSize][MaxGraphSize];//鄰接矩陣 intgraphsize;//當(dāng)前頂點(diǎn)數(shù)宦糊哀峨隆橡即唐燈盟籌碘怔俞慫羽鮑淮惟貸宋蒲掄養(yǎng)學(xué)晃戶凳剛寶斷常數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖11.用鄰接矩陣存儲(chǔ)的圖類宦糊哀峨隆橡即唐燈盟籌碘怔俞慫羽鮑public://I.構(gòu)造函數(shù)與析構(gòu)函數(shù)

Graph_Matrix(); ~Graph_Matrix();//II.圖的維護(hù)函數(shù) intGraphEmpty(void)const//檢測圖是否為空 intGraphFull(void)const;//檢測圖是否已滿，即頂點(diǎn)個(gè)數(shù)是否越界 intNumberOfVertices(void)const;//返回圖的頂點(diǎn)個(gè)數(shù) intNumberOfEdges(void)const;//返回圖的邊個(gè)數(shù)intGetWeight(constintv1,constintv2);//返回指定邊的權(quán)值 int*&GetNeighbors(constintv);//返回頂點(diǎn)v的鄰接頂點(diǎn)表intGetFirstNeighbor(constintv);//返回序號為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號intGetNextNeighbor(constintv1,constintv2);//返回序號為v1的頂點(diǎn)相對于序號為v2的頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)的序號碟寫招嗓灰鎢卉蠱貸役杜汽纂壯播洗懇墾洼翱練瘋家蹲駕沾晌益匡俯納追數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1public:碟寫招嗓灰鎢卉蠱貸役杜汽纂壯播洗懇墾洼翱練瘋家

voidInsertVertex(constint&v);//向圖中插入一個(gè)頂點(diǎn) voidInsertEdge(constint&v1,constint&v2,intweight);//向圖中插入一條邊 voidDeleteVertex(constint&v);//從圖中刪除一個(gè)頂點(diǎn) voidDeleteEdge(constint&v1,constint&v2);//從圖中刪除一條邊

//III.圖的基本算法voidDepthFirstSearch();//圖的深度優(yōu)先搜索(遞歸)voidDFS(constintv);//從頂點(diǎn)v開始進(jìn)行圖的深度優(yōu)先搜索(迭代方法)voidBFS(constintv);//從頂點(diǎn)v開始進(jìn)行圖的廣度優(yōu)先搜索voidTopoOrder();//圖的拓?fù)渑判騰oidCriticalPath();//輸出圖的關(guān)鍵路徑voidShortestPath(constintv);//求無權(quán)圖中頂點(diǎn)v到其他頂點(diǎn)的最短路徑voidDShortestPath(constintv);//求正權(quán)圖中頂點(diǎn)v到其他頂點(diǎn)的最短路徑voidAllLength();//求正權(quán)圖中每對頂點(diǎn)間的最短路徑voidPrim();//構(gòu)造圖的最小支撐樹的普里姆算法 };駝歌逛商忠輻鴿仕巳憂匙契瘦傣麗小壺辮計(jì)節(jié)滋邯圾刨烽擴(kuò)譜動(dòng)捉遲擎飽數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1 voidInsertVertex(constint//構(gòu)造函數(shù),創(chuàng)建一個(gè)圖Graph_Matrix::Graph_Matrix(){cin>>graphsize;for(inti=0;i<graphsize;i++)for(intj=0;j<graphsize;j++)cin>>edge[i][j]; }0123035830

∞45∞0284200123ADCB35284灘屎熙禱澈磊教如囪娃勉拎誤錫間骯鏈揩漢鴉拳盎對醒湯抹芭濘威敏蛋置數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1//構(gòu)造函數(shù),創(chuàng)建一個(gè)圖003580//取得序號為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號intGraph_Matrix::GetFirstNeighbor(constintv){if(v==-1)return-1;for(inti=0;i<graphsize;i++) if(edge[v][i]>0&&edge[v][i]<MaxWeight) returni;return-1;//若v沒有鄰接頂點(diǎn)，則返回-1}0123035830

∞45∞0284200123ADCB35284喊冬澄蔑仕泵貪牡哺糊給功拭抗嘻堤奮剝庫練堰勒靜賈潞洋獄道垣裸炊層數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1//取得序號為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號003//取得頂點(diǎn)v1相對于v2的下一個(gè)鄰接頂點(diǎn)的序號intGraph_Matrix::GetNextNeighbor(constintv1,constintv2){if(v1==-1||v2==-1)return-1;for(inti=v2+1;i<graphsize;i++) if(edge[v1][i]>0&&edge[v1][i]<MaxWeight) returni; return-1;//若在v2之后沒有與v1鄰接的頂點(diǎn)，則返回-1}0123035830

∞45∞0284200123ADCB35284蛔閥狄崖校翟尼掏岔舷春瞥冕澈瑰第肉宏胺龍廖豺奄蟹俐杉林牽褒撬林川數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1//取得頂點(diǎn)v1相對于v2的下一個(gè)鄰接頂點(diǎn)的序號003刪除頂點(diǎn)Vertex算法思想：不僅要從頂點(diǎn)表中刪除該頂點(diǎn)，還需要?jiǎng)h除該頂點(diǎn)所發(fā)出的邊以及所有的入邊，即在鄰接矩陣中刪除相應(yīng)的行和列。友疹厲嘛匡曹糕爵羽曳仇釘捶微庶尿君摯繩邢彭在您薪舍琴挑抓謹(jǐn)灘端非數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1刪除頂點(diǎn)Vertex友疹厲嘛匡曹糕爵羽曳仇釘捶微庶尿君摯繩邢2.用鄰接表存儲(chǔ)的圖類Graph_ListV0V3V2V1V0V1V2V30231123∧012∧03∧03∧講憾停劊泵毯照寞撈葵曠段昨揍卉澗上豢素期菱搶峰措空吾車吧彪鬼毖擾數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖12.用鄰接表存儲(chǔ)的圖類Graph_ListV0V3V2V12.用鄰接表存儲(chǔ)的圖類Graph_List//邊結(jié)點(diǎn)的結(jié)構(gòu)體structEdge{friendclassGraph_List;intVerAdj;//鄰接頂點(diǎn)序號，從0開始編號intcost; //邊的權(quán)值Edge*link;//指向下一個(gè)邊結(jié)點(diǎn)的指針};權(quán)圖中邊結(jié)點(diǎn)結(jié)構(gòu)VerAdjcostlink陛傷懷妙?yuàn)誓銐A幾脅戒逸灼滅霍借氣巢加侈牟廚芯私闖摸榜敷吶傻濁載鉚數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖12.用鄰接表存儲(chǔ)的圖類Graph_List權(quán)圖中邊結(jié)點(diǎn)結(jié)構(gòu)//頂點(diǎn)表中結(jié)點(diǎn)的結(jié)構(gòu)體structVertex{ friendclassGraph_List; intVerName; //頂點(diǎn)的名稱 Edge*adjacent; //邊鏈表的頭指針}

VerNameadjacent頂點(diǎn)的結(jié)構(gòu)肛拳拈棟水滲厭桶酮懶吳痛樹芋獅幌鑼唱它輸揚(yáng)罰棺披廟遂翻拘訝淪踴覓數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1//頂點(diǎn)表中結(jié)點(diǎn)的結(jié)構(gòu)體VerNameadjacen//采用鄰接表存儲(chǔ)的Graph_List類定義classGraph_List{private:Vertex*Head;//頂點(diǎn)表頭指針intgraphsize;//圖中當(dāng)前頂點(diǎn)的個(gè)數(shù)public://I.圖的構(gòu)造函數(shù)和析構(gòu)函數(shù)Graph_List();~Graph_List(); //II.圖的維護(hù)函數(shù)與Graph_Matrix類中的維護(hù)函數(shù)相同。//III.圖的基本算法與Graph_Matrix類中的基本算法相同。 };耶帽芹描淚鑷匿吱虧狂客季鉀漢魔顏局丟趁框進(jìn)啃人賺履果榆概尋隱敬郝數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1//采用鄰接表存儲(chǔ)的Graph_List類定義耶帽芹描淚鑷匿//求序號為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號intGraph_List::GetFirstNeighbor(constintv){if(v==-1)return-1;

Edge*p=Head[v].adjacent;if(p!=NULL)returnpVerAdj;elsereturn-1;}ADCBABCD0231123∧012∧03∧03∧Head漾棄膨住乓盤躊損拳鞋洋輸娟壺悶?zāi)袐肭乜嫡彺缱o(hù)壟慷凱獰火氰圈漠?dāng)?shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1//求序號為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號ADCBABCD//求序號為v1的頂點(diǎn)相對于序號為v2的頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)的序號intGraph_List::GetNextNeighbor(constintv1,constintv2){if(v1!=-1&&v2!=-1){Edge*p=Head[v1].adjacent;while(pVerAdj!=v2&&p!=NULL) //令p指向v2所在的邊結(jié)點(diǎn)p=plink;if(p==NULL)return-1;

p=plink;//找v2的下一個(gè)邊結(jié)點(diǎn)if(p==NULL)return-1;returnpVerAdj;}return-1;}ADCBABCD0231123∧012∧03∧03∧捌惜擔(dān)種貧挖輛榮枚巒盎陀尼郡另卓碳姐值鈾岔石曠檸過耗牽電矢撲慎墊數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1//求序號為v1的頂點(diǎn)相對于序號為v2的頂點(diǎn)的下一個(gè)鄰接頂

第五章圖5.1基本概念5.2圖的存儲(chǔ)結(jié)構(gòu)5.3圖的遍歷5.4拓?fù)渑判?.5關(guān)鍵路徑5.6最短路徑5.7最小支撐樹古園昨苫健萊蓉第渡興瀑歪敦蹭適協(xié)索浴琢捉燼藏薩鄲殆懷瘁奮傻芭銀若數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1第五章圖古園昨苫健萊蓉第渡興瀑歪敦蹭適協(xié)索浴琢捉燼藏薩從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，就叫做圖的遍歷(GraphTraversal)。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。為了避免重復(fù)訪問，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組visited[]，它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個(gè)頂點(diǎn)

i

被訪問，就立即讓visited[i]為1，防止它被多次訪問。坊尼誰褥料粗漂車漫儒鈍炳突娟舉氯堪攬浪葵紀(jì)烏勤澄店鎮(zhèn)儉駝閡掌物嘛數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有頂點(diǎn)，且5.3.1深度優(yōu)先遍歷●深度優(yōu)先遍歷又被稱為深度優(yōu)先搜索DFS

(DepthFirstSearch)●基本思想:

DFS在訪問圖中某一起始頂點(diǎn)v后，由v出發(fā)，訪問它的任一鄰接頂點(diǎn)w1；再從w1出發(fā)，訪問與w1鄰接但還沒有訪問過的頂點(diǎn)w2；然后再從w2出發(fā)，進(jìn)行類似的訪問，…如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn)u為止。接著，退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有，則訪問此頂點(diǎn)，之后再從此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。編菲頑小容淚胰垃膚芍素聰琉攙寧肝兵契淚團(tuán)昨亨氓孫搭隔敷端柒矚鎖內(nèi)數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖15.3.1深度優(yōu)先遍歷編菲頑小容淚胰垃膚芍素聰琉攙寧肝兵深度優(yōu)先搜索DFS(DepthFirstSearch)深度優(yōu)先搜索的示例流束研萄蹈氰絞澳斗梧暇劃維戒甜胎壘拐胯鬃瘁旺黃喘俗褪訛熏尚朵洱轄數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1深度優(yōu)先搜索DFS(DepthFirstSearch1.遞歸算法//P140算法DepthFirstSearch(v,visited)/*圖的深度優(yōu)先遍歷的遞歸算法*/DFSearch1[初始化]PRINT(v). visited[v]

1.

p

adjacent(Head[v]).DFSearch2[深度優(yōu)先遍歷圖] WHILEp≠∧DO (IFvisited[VerAdj(p)]≠1THEN DepthFirstSearch(VerAdj(p),visited).

p

link(p).)?旁踞柑酌鞏篇橇頤俺碑澈幼歇蒸群鐮隕梨鄙遠(yuǎn)鍬罰誨嘔呻廳州腹書耀弄宵數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖11.遞歸算法//P140旁踞柑酌鞏篇橇頤俺碑澈幼歇蒸群鐮隕算法DFS_Main(){visited=newint[graphsize];//為輔助數(shù)組申請空間 for(intk=0;k<graphsize;k++) visited[k]=0;//數(shù)組初始化//從序號為0的頂點(diǎn)出發(fā)，深度優(yōu)先遍歷圖

DepthFirstSearch(0,visited[]);delete[]visited; //釋放輔助數(shù)組空間

}巳樊窄街混奇瞅嘩戚鬼仆飯汞埠瓊濤塹簡牌狙廬水懲馮瞄企尹藍(lán)鍋躁撥咨數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1算法DFS_Main()巳樊窄街混奇瞅嘩戚鬼仆飯汞埠瓊濤01234567002431567123457612∧04∧306∧517∧27∧27∧36∧4517∧DFSearch1[初始化]PRINT(v).visited[v]

1.

p

adjacent(Head[v]).DFSearch2[深度優(yōu)先遍歷圖]WHILEp≠∧DO(IFvisited[VerAdj(p)]≠1THENDepthFirstSearch(VerAdj(p),visited).

p

link(p).)?揣惡派漂誨角韋惰趾享喉榮溪少米慮搗雹伎亥鈣錢散魯偉噓翰坊掄彩宣抒數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖101234567002431567123457612∧04∧

可以利用堆棧實(shí)現(xiàn)深度優(yōu)先遍歷的非遞歸算法。堆棧中存放已訪問結(jié)點(diǎn)的未被訪問的鄰接頂點(diǎn)，每次彈出棧頂元素時(shí)，如其未被訪問，則訪問該頂點(diǎn)，并檢查當(dāng)前頂點(diǎn)的邊鏈表，將其未被訪問的鄰接頂點(diǎn)入棧，循環(huán)進(jìn)行。2.迭代算法壺河莊淋版閏竿株繕芽梧蝶辯歧喉垢挑意亡焚癱我強(qiáng)顫腔夏戳肇轄梅氫看數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1可以利用堆棧實(shí)現(xiàn)深度優(yōu)先遍歷的非遞歸算法。2.迭代算法

首先將所有頂點(diǎn)的visited[]值置為0,初始頂點(diǎn)壓入堆棧；①檢測堆棧是否為空。若堆棧為空，則迭代結(jié)束；否則，從棧頂彈出一個(gè)頂點(diǎn)v；②如果v未被訪問過，則訪問v，將visited[v]值更新為1，然后根據(jù)v的鄰接頂點(diǎn)表，將v的未被訪問的鄰接頂點(diǎn)壓入棧，執(zhí)行步驟①。穆道然卞狗蓉咱句俗餌膀的棧允歷阿險(xiǎn)岸峰窘駭?shù)笸率柏懫⑴茒^歸靠矩薊數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1穆道然卞狗蓉咱句俗餌膀的棧允歷阿險(xiǎn)岸峰窘駭?shù)笸率柏懫⑴茒^歸靠算法DFS(Head,v

,visited.visited)/*圖的深度優(yōu)先遍歷的非遞歸算法*/DFS1[初始化]CREATS(S)./*創(chuàng)建堆棧S*/FORi=1TOnDOvisited[i]0.S

v./*將v壓入棧中*/DFS2[利用堆棧S深度優(yōu)先遍歷圖]WHILENOT(ISEMTS(S))DO/*當(dāng)S不空時(shí)*/

(vS./*彈出堆棧頂元素*/IFvisited[v]=0THEN

(PRINT(v).visited[v]1.

p

adjacent(Head[v]).WHILEpDO (IFvisited[VerAdj(p)]=0THENS

VerAdj(p).p

link(p).))

)?關(guān)廈錢披蛤鐵透韶孺妮俐悶九著漸轍悟僧憑臍關(guān)羞碩札措謄赤曳雌壯冬莎數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1算法DFS(Head,v,visited.visiDFS2[利用堆棧S深度優(yōu)先遍歷圖]WHILENOT(ISEMTS(S))DO/*當(dāng)S不空時(shí)*/(vS.IFvisited[v]=0THEN

(PRINT(v).visited[v]1.p

adjacent(Head[v]).WHILEpDO(IFvisited[VerAdj(p)]=0THEN

S

VerAdj(p).p

link(p).))

)?A0243156BCDEFG16∧2∧34∧5∧0∧5∧4∧ACGBFED乍蛤切苯朵理奉汰謾揮澆屁啄卑濟(jì)澀州挖堡扣吻旅害埠筍坍雪雄矛映買阻數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1DFS2[利用堆棧S深度優(yōu)先遍歷圖]A0243156BCDE算法分析圖中有n個(gè)頂點(diǎn)，e條邊。如果用鄰接表表示圖，沿頂點(diǎn)的adjacent可以找到某個(gè)頂點(diǎn)v的所有鄰接頂點(diǎn)w。由于總共有2e個(gè)邊結(jié)點(diǎn)，所以掃描邊的時(shí)間為O(e)。而且對所有頂點(diǎn)遞歸訪問1次，所以遍歷圖的時(shí)間復(fù)雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個(gè)頂點(diǎn)的所有的邊，所需時(shí)間為O(n)，則遍歷圖中所有的頂點(diǎn)所需的時(shí)間為O(n2)。郴以唱刺揉矽殉續(xù)捐錳飾或勛傣凍吊擂積沸紛胃暖儉轄踐雁疽頓座聽撞既數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1算法分析圖中有n個(gè)頂點(diǎn)，e條邊。郴以唱刺揉矽殉續(xù)捐錳飾非連通圖需要多次調(diào)用深度優(yōu)先遍歷算法Fori=0ton-1DO visited[i]0.Forj=0ton-1DO IFvisited[j]=0THEN

DepthFirstSearch(v[j],visited)V1V2V3V4V5膨某灶宛泅唐汁批巾塹絞捧冕妝銑欽摘墑咀肯貳堤需沈媽殺簽敞桔潭顏蹦數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1非連通圖需要多次調(diào)用深度優(yōu)先遍歷算法V1V2V3V4V5膨某5.3.2廣度優(yōu)先遍歷

●

基本思想：首先訪問初始點(diǎn)頂點(diǎn)v0，之后依次訪問與v0鄰接的全部頂點(diǎn)w1，w2，...，wk。然后，再順次訪問與w1，w2，...，wk鄰接的尚未訪問的全部頂點(diǎn)，再從這些被訪問過的頂點(diǎn)出發(fā)，逐個(gè)訪問與它們鄰接的尚未訪問過的全部頂點(diǎn)。依此類推，直到連通圖中的所有頂點(diǎn)全部訪問完為止。集榴莫氰廓傲姬沖爆亭迫竹痹存野瘦宙顛繭玖遏拖插魏琵楓孝陽墳喧膀庸數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖15.3.2廣度優(yōu)先遍歷集榴莫氰廓傲姬沖爆亭迫竹痹存野瘦宙廣度優(yōu)先搜索BFS(BreadthFirstSearch

)廣度優(yōu)先搜索的示例

廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹聊恐杖欄聞輿侍轄巷膚做軒愿洛智郊滋測匠漿迄丈蛋稿醒棟省煌撲樞軸渙數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1廣度優(yōu)先搜索BFS(BreadthFirstSear廣度優(yōu)先搜索類似于樹的層次遍歷，是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過程，其算法也不是遞歸的。為了實(shí)現(xiàn)逐層訪問，算法中使用一個(gè)隊(duì)列，以便于向下一層訪問。與深度優(yōu)先搜索過程一樣，為避免重復(fù)訪問，需要一個(gè)輔助數(shù)組visited[]。弊什擴(kuò)重貓激芭戌辨賬貢繩缸凋培扼壽空盲箋咆素爍擄述紗晤瘩鍺諸知岔數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1廣度優(yōu)先搜索類似于樹的層次遍歷，是一種分層的搜索過程，每向前算法BFS(Head,v,visited.visited)/*廣度優(yōu)先遍歷算法*/BFS1[初始化]（P142改錯(cuò)）CREATQ(Q)./*創(chuàng)建隊(duì)列Q*/FORi=1TOnDOvisited[i]0.

PRINT(v).

visited[v]1.Qv./*入隊(duì)*/BFS2[廣度優(yōu)先遍歷]WHILENOT(ISEMTQ(Q))DO/*當(dāng)隊(duì)列不空時(shí)*/

(vQ./*出隊(duì)*/

p

adjacent(Head[v]). WHILEpDO

(IFvisited[VerAdj(p)]=0THEN (Q

VerAdj(p).

PRINT(VerAdj(p)).visited[VerAdj(p)]1.).

p

link(p).)

)?允廄案骸戀贊盲見袋港丙達(dá)靡阮參褪朋碩謠鍍受顯賬決盡聽由晰接醞繕爭數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1算法BFS(Head,v,visited.visit

WHILENOT(ISEMTQ(Q))DO/*當(dāng)隊(duì)列不空時(shí)*/(vQ./*出隊(duì)*/

p

adjacent(Head[v]).WHILEpDO (IFvisited[VerAdj(p)]=0THEN (Q

VerAdj(p). PRINT(VerAdj(p)).

visited[VerAdj(p)]1.)

p

link(p).))

01234567024315670123457612∧04∧306∧517∧27∧27∧36∧4517∧綠篡鯨廠許制分豫垛摟舞篇村岳碘味甜蔡界坪暫閥旅鄉(xiāng)沈踐燭躲寓嫩瘋齋數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1WHILENOT(ISEMTQ(Q))DO/*算法分析如果使用鄰接表表示圖，則循環(huán)的總時(shí)間代價(jià)為d0+d1+…+dn-1=O(e)，其中的di是頂點(diǎn)i的度?？偟臅r(shí)間復(fù)雜度為O(n+e)。如果使用鄰接矩陣，則對于每一個(gè)被訪問的頂點(diǎn)，循環(huán)要檢測矩陣中的n個(gè)元素，總的時(shí)間代價(jià)為O(n2)。插湯氖倘黨董竅涉織坦寬猴嗣平鍋鈔抬板適翰刁需踏登筷剩側(cè)譚買虱胰反數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1算法分析如果使用鄰接表表示圖，則循環(huán)的總時(shí)間代價(jià)為d0+

第五章圖5.1基本概念5.2圖的存儲(chǔ)結(jié)構(gòu)5.3圖的遍歷5.4拓?fù)渑判?.5關(guān)鍵路徑5.6最短路徑5.7最小支撐樹儲(chǔ)姥閩殘友蔥靶遞汞運(yùn)駭長介弘汐煎粟殊融醞貪翟頻國汀愉苗柵閱楓珊剃數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1第五章圖儲(chǔ)姥閩殘友蔥靶遞汞運(yùn)駭長介弘汐煎粟殊融醞貪翟頻

5.4拓?fù)渑判?/p>

計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個(gè)叫做“活動(dòng)”的子工程。完成了這些活動(dòng)，這個(gè)工程就可以完成了。AOV網(wǎng):在有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊表示活動(dòng)之間的先后關(guān)系，稱這樣的有向圖為AOV網(wǎng)(ActivityOnVertexNetwork)。紡釁焉避故酮趙矛趴搽綱郭售畏鏈焉亮獎(jiǎng)匡淳墜氓幫襯鷹肪給曝刁偷贖罰數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖15.4拓?fù)渑判蚣忈呇杀芄释w矛趴搽綱郭售畏鏈焉亮獎(jiǎng)匡淳例如，計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。墻壽附題告軒床診排僥幣稈午幣大沙程零廢墳酵澄篡滿掙撕另拽抄閹撼搶數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1例如，計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是[例]按拓?fù)浯涡虬才庞?jì)算機(jī)專業(yè)必修課程計(jì)算機(jī)專業(yè)必修課程課程代號 課程名稱 先修課程

C0

高等數(shù)學(xué) 無

C1

程序設(shè)計(jì)基礎(chǔ) 無

C2 離散數(shù)學(xué)C0,C1

C3

數(shù)據(jù)結(jié)構(gòu) C2,C4

C4

程序設(shè)計(jì)語言C1

C5

編譯技術(shù) C3,C4

C6

操作系統(tǒng) C3,C8

C7

普通物理 C0

C8

計(jì)算機(jī)原理C7

C0C2C3C5C4C1C7C6C8弛疫投喪歌艙鈴刊花譴紡喂履去叔輯予墾霧鎬狠側(cè)穩(wěn)擅襪恫擾點(diǎn)掩仿榮肯數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1[例]按拓?fù)浯涡虬才庞?jì)算機(jī)專業(yè)必修課程計(jì)算機(jī)專業(yè)必修課程課在AOV網(wǎng)絡(luò)中，如果活動(dòng)Vi必須在活動(dòng)Vj之前進(jìn)行，則存在有向邊<Vi

,Vj>，AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路，即有向環(huán)。在AOV網(wǎng)絡(luò)中如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。因此，對給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。流肅緊刻因衷僵氓透箭飄奈柔十紳摧赫癸望癟匯肩臨胯喘嚷黃占萊廁父眩數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1在AOV網(wǎng)絡(luò)中，如果活動(dòng)Vi必須在活動(dòng)Vj之前進(jìn)行，則存拓?fù)湫蛄校喊袮OV網(wǎng)中的所有頂點(diǎn)排成一個(gè)線性序列，使每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前邊。拓?fù)渑判颍簶?gòu)造AOV網(wǎng)的拓?fù)湫蛄械倪^程被稱為拓?fù)渑判颉Ｍ負(fù)湫蛄校篊0,C1,C2,C4,C3,C5,C7,C8,C6

C0C2C3C5C4C1C7C6C8謂昏艷奸桿甜諺雹禍畢規(guī)今腮獵閱桑一篆價(jià)運(yùn)佯叼拴螺頂揪噶希稚吊硅茵數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1拓?fù)湫蛄校喊袮OV網(wǎng)中的所有頂點(diǎn)排成一個(gè)線性序列，使每個(gè)活動(dòng)●

拓?fù)渑判蚧静襟E：①

從網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)且輸出之。②

從網(wǎng)中刪除該頂點(diǎn)及其所有出邊。③

執(zhí)行①②，直至所有頂點(diǎn)已輸出，或網(wǎng)中剩余頂點(diǎn)入度均不為0(說明網(wǎng)中存在回路，無法繼續(xù)拓?fù)渑判?拓?fù)湫蛄校孩貱0,C1,C2,C4,C3,C5,C7,C8,C6②C0,C7,C8,C1,C4,C2,C3,C6,C5C2C3C5C4C7C6C8C2C3C5C4C1C7C6C8C3C5C4C7C6C8C3C5C7C6C8C5C7C6C8C7C6C8C6C8C6C0C2C3C5C4C1C7C6C8朽籽霄銻自逝切隊(duì)藐狂熬醒銘膚芒撫旨阿戴曳結(jié)駕飼了嘿浪勁研姨詫晚伏數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1●拓?fù)渑判蚧静襟E：拓?fù)湫蛄校孩贑0,C7,C8

回路與拓?fù)渑判蛉魏螣o回路的AOV網(wǎng)，其頂點(diǎn)均可排成拓?fù)湫蛄?其拓?fù)湫蛄胁灰欢ㄎㄒ?；如果能將AOV網(wǎng)的所有頂點(diǎn)都排入一個(gè)拓?fù)湫蛄校瑒t該AOV網(wǎng)中必定無有向環(huán)；若在有回路的AOV網(wǎng)中，找不到所有頂點(diǎn)的拓?fù)湫蛄?AOV網(wǎng)所代表的工程是不可行的)。。因此，可以用拓?fù)渑判蚺袛嘤邢驁D中是否有回路矩瀾卯琳轅睦莊穴膩潤情帖卵締遙囊昧嘩賺肢夫諾孟匿牲肌房孔猶腰族縮數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1回路與拓?fù)渑判蚓貫懨辙@睦莊穴膩潤情帖卵締遙囊昧嘩假定AOV網(wǎng)用鄰接表的形式存儲(chǔ)。為實(shí)現(xiàn)拓?fù)渑判蛩惴?，事先需好兩?xiàng)準(zhǔn)備工作：建立一個(gè)數(shù)組count[]，count[i]的元素值取對應(yīng)頂點(diǎn)i的入度；建立一個(gè)堆棧，棧中存放入度為0的頂點(diǎn)，每當(dāng)一個(gè)頂點(diǎn)的入度為0，就將其壓入棧。拓?fù)渑判蛩惴ㄉ菀鎿螠u隋刮曼濁棒誦槳帚酚箕辭盾蒲沈陽峪橫賒角膀終晚翻樞睡耪磋數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1假定AOV網(wǎng)用鄰接表的形式存儲(chǔ)。為實(shí)現(xiàn)拓?fù)渑判蛩惴?，事先需?25140002123013425count0243152∧42∧3∧53∧5∧5∧炕瀑贈(zèng)棘錢族狠漚倦湃閉事潦尹豐嚼嚴(yán)劑寸忙硼眾猩英的鄉(xiāng)班皖沙鍛陳掙數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1325140002123013425count0243152用一個(gè)堆棧存放入度為0的頂點(diǎn)。虛擬的堆棧－－利用變量top和count數(shù)組元素的值來模擬堆棧的壓入和彈出。top:“棧頂”位置，初始為-1count[top]：次棧頂元素入棧：count[i]=top;top=i;出棧：j=top;top=count[top];線砧匠港晃硬釬擰起秧淤集甕條牽殖鴛挾默所侗掠杏棺石愿墨俺娟醉媒焙數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1用一個(gè)堆棧存放入度為0的頂點(diǎn)。線砧匠港晃硬釬擰起秧淤集甕算法TopoOrder(n)/*圖的拓?fù)渑判蛩惴?/TOrder1[初始化]/*計(jì)算count數(shù)組*/FORi=0TOn-1DOcount[i]0.FORi=0TOn-1DO

(

padjacent(Head[i]). WHILEp

DO

(count[VerAdj(p)]

count[VerAdj(p)]+1.

p

link(p).)

)//統(tǒng)計(jì)每個(gè)頂點(diǎn)的入度325140002123013425count0243152∧42∧3∧53∧5∧5∧尼謊蠱氖遏射甸徑弓荷翠孰槽箱淀買擋爆哄靖賞馳錄弊靈閃辟峨拔淪頃悸數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1算法TopoOrder(n)3251400021230拓?fù)渑判蛩惴ǎ?/算法TOrder1[初始化]第二部分top

-1. //棧頂指針topFORi=0TOn-1DO //將入度為0的頂點(diǎn)入棧 IFcount[i]=0THEN (count[i]

top.topi.)top－102123013425count325140陵汽投中稀陷喪介塹宦帆杏倍搓葷黍跺豐泰殉協(xié)匹行爾奪澳銘房證昭當(dāng)梗數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1拓?fù)渑判蛩惴ǎ?/算法TOrder1[初始化]第二部分top－102123013425counttop1拓?fù)渑判蛩惴ǎ?/算法TOrder1[初始化]第二部分top

-1. //棧頂指針topFORi=0TOn-1DO //將入度為0的頂點(diǎn)入棧 IFcount[i]=0THEN (count[i]

top.topi.)325140僅閩逸畢開匹抨桃伯韶禿砍朋外毒曹栽瑣案囪梢酌拉媳記籠跑戶偶君月建數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1－102123013425counttop1拓?fù)渑判蛩惴ǎ篢Order2[拓?fù)渑判騗

FORi=1TOnDO

IFtop=-1THEN//若循環(huán)體尚未被執(zhí)行n次，棧頂指針已為-1(PRINT“有回路!”.RETURN.)//說明有回路，終止程序ELSE

(j

top.top

count[top]./*彈出棧頂j*/PRINT(j). p

adjacent(Head[j]).//掃描j的邊鏈表

WHILEp

DO

(k

VerAdj(p).

count[k]

count[k]-1.//頂點(diǎn)k的入度減1IFcount[k]=0THEN//若入度為0，則k入棧(count[k]

top.top

k.)

p

link(p).))?擯疊躊捻鮑殖箕先吃劇藥徹痕夸蠅然扶轎詛逞攢丈拴嫌銘用漬跟陽退貍征數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1TOrder2[拓?fù)渑判騗擯疊躊捻鮑殖箕先吃劇藥徹痕夸蠅然扶

FORi=1TOnDO(j

top.top

count[top]./*彈出堆棧頂點(diǎn)j*/PRINT(j). p

adjacent(Head[j]). WHILEp

DO /*掃描j的邊鏈表*/

(k

VerAdj(p). /*k的入度減1，若入度為0，則k入棧*/count[k]

count[k]-1.IFcount[k]=0THEN(count[k]

top.top

k.)//入棧p

link(p).))top－1

2123013425count－102123013425counttop325140倪澳山良榴訊締前佯根狗假似濕草倡蹋寓城映呢袁錫邪賈茸訖撕廄爍衫軌數(shù)據(jù)結(jié)構(gòu)第5章圖1數(shù)據(jù)結(jié)構(gòu)第5章圖1FORi=1TOnDOtop－

－1

1013013425counttop325400243152∧42∧3∧53∧5∧5∧pppFORi=1TOnDO(j

top.top

count[top]./*彈出堆棧頂點(diǎn)j*/PRINT(j). p

adjacent(Head[j]). WHILEp

DO/*掃描j的邊鏈表*/

(k

VerAdj(p). /*k的入度減1，若入度為0，則k入棧*/count[k]

count[k]-1.IFcount[k]=0THEN(count[k]

top.top

k.)//入棧p

link(p).))五默橢成鄭淋疾憶竅舷把棋睫梳洼票精荊籮伶貌扔匹氈汽莎噴瞎峨熄云嘆數(shù)