數(shù)據(jù)結(jié)構(gòu)課件-圖講述

1、Page 12022-3-17p 畫出下列二叉鏈表代表的二叉樹（畫出下列二叉鏈表代表的二叉樹（0代表代表NULL指針），并指針），并完成其先序線索鏈表完成其先序線索鏈表InfoInfoA AB BC CD DE EF FG GH HI IJ JK KL LM MN NLtagLtagLchildLchild2 24 46 60 07 70 010100 0121213130 00 00 00 0RtagRtagRchildRchild3 35 50 00 08 89 911110 00 00 014140 00 00 0InfoInfoA AB BC CD DE EF FG GH HI IJ

2、JK KL LM MN NLtagLtag0 00 00 01 10 01 10 01 10 00 01 11 11 11 1LchildLchild2 24 46 62 27 73 3101014141212131313139 910101111RtagRtag0 00 01 11 10 00 00 01 11 11 10 01 11 11 1RchildRchild3 35 56 65 58 89 911113 31212131314140 011118 81 2 3 4 5 6 7 8 9 10 11 12 13 14Page 22022-3-17第第8-1講講 圖的基礎(chǔ)知識圖的基礎(chǔ)知識

3、清華大學(xué)清華大學(xué) 自動化系自動化系 黃雙喜黃雙喜 博士、副教授博士、副教授Page 32022-3-17q學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo)v領(lǐng)會領(lǐng)會圖的基本概念圖的基本概念。v熟悉熟悉圖的各種存儲結(jié)構(gòu)圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲及其構(gòu)造算法，了解各種存儲結(jié)構(gòu)的特點及其結(jié)構(gòu)的特點及其選用原則選用原則。v熟練掌握圖的兩種熟練掌握圖的兩種遍歷遍歷算法及應(yīng)用。算法及應(yīng)用。v理解各種圖的理解各種圖的應(yīng)用問題的算法應(yīng)用問題的算法。q重點和難點重點和難點v重點：圖的各種應(yīng)用問題的算法都比較經(jīng)典，注意重點：圖的各種應(yīng)用問題的算法都比較經(jīng)典，注意理理解各種圖的算法及其應(yīng)用場合解各種圖的算法及其應(yīng)用場合。Page

4、42022-3-17q知識點知識點v圖的類型定義圖的類型定義v圖的存儲表示圖的存儲表示v圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷v最小生成樹算法最小生成樹算法v拓撲排序拓撲排序v關(guān)鍵路徑關(guān)鍵路徑v最短路徑最短路徑q圖的概念與基本術(shù)語q圖的類型定義與存儲q圖的遍歷q圖的連通性與最小生成樹Page 52022-3-172022-3-17歐拉歐拉17071707年出生在瑞士的巴塞爾城，年出生在瑞士的巴塞爾城，1919歲開始發(fā)歲開始發(fā)表論文，直到表論文，直到7676歲。幾乎每一個數(shù)學(xué)領(lǐng)域都可以歲。幾乎每一個數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體看到

5、歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級數(shù)論的歐拉常數(shù)，復(fù)變函數(shù)的程的歐拉方程，級數(shù)論的歐拉常數(shù)，復(fù)變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計他那不倦的一生，共寫下歐拉公式等等。據(jù)統(tǒng)計他那不倦的一生，共寫下了了886886本書籍和論文，其中分析、代數(shù)、數(shù)論占本書籍和論文，其中分析、代數(shù)、數(shù)論占40%40%，幾何占，幾何占18%18%，物理和力學(xué)占，物理和力學(xué)占28%28%，天文，天文學(xué)占學(xué)占11%11%，彈道學(xué)、航海學(xué)、建筑學(xué)等

6、占，彈道學(xué)、航海學(xué)、建筑學(xué)等占3%3%。 17331733年，年僅年，年僅2626歲的歐拉擔(dān)任了彼得堡科學(xué)院歲的歐拉擔(dān)任了彼得堡科學(xué)院數(shù)學(xué)教授。數(shù)學(xué)教授。17411741年到柏林擔(dān)任科學(xué)院物理數(shù)學(xué)所年到柏林擔(dān)任科學(xué)院物理數(shù)學(xué)所所長，直到所長，直到17661766年，重回彼得堡，沒有多久，完年，重回彼得堡，沒有多久，完全失明。歐拉在數(shù)學(xué)上的建樹很多，對著名的哥全失明。歐拉在數(shù)學(xué)上的建樹很多，對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。Page 72022-3-17能否從某個地方出發(fā)，穿過所有的橋僅一次能否從某個地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點？

7、后再回到出發(fā)點？18世紀(jì)東普魯士哥尼斯堡被普列戈世紀(jì)東普魯士哥尼斯堡被普列戈爾河分為四塊爾河分為四塊, 它們通過七座橋相互它們通過七座橋相互連接。當(dāng)時該城的市民熱衷于這樣連接。當(dāng)時該城的市民熱衷于這樣一個游戲：一個游戲：“一個散步者怎樣才能一個散步者怎樣才能從某塊陸地出發(fā)，經(jīng)每座橋一次且從某塊陸地出發(fā)，經(jīng)每座橋一次且僅一次回到出發(fā)點？僅一次回到出發(fā)點？”2022-3-17CADB七橋問題的圖模型七橋問題的圖模型歐拉回路的判定規(guī)則：歐拉回路的判定規(guī)則：1.如果通奇數(shù)橋的地方多于如果通奇數(shù)橋的地方多于兩個，則不存在歐拉回路；兩個，則不存在歐拉回路；2.如果只有兩個地方通奇數(shù)如果只有兩個地方通奇數(shù)橋

8、，可以從這兩個地方之一橋，可以從這兩個地方之一出發(fā)，找到歐拉回路；出發(fā)，找到歐拉回路；3.如果沒有一個地方是通奇如果沒有一個地方是通奇數(shù)橋的，則無論從哪里出發(fā)，數(shù)橋的，則無論從哪里出發(fā)，都能找到歐拉回路。都能找到歐拉回路。Page 92022-3-17最短路問題（SPPshortest path problem） 一名貨柜車司機奉命在最短的時間內(nèi)將一車貨物從甲地運往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運行速度是恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的最短路。旅行商問題（TSPtraveling salesman proble

9、m） 一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題。中國郵遞員問題（CPPChinese postman problem） 一名郵遞員負責(zé)投遞某個街區(qū)的郵件。如何為他（她）設(shè)計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。運輸問題(transportation problem) 某種原材料有N個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往M個使用這些原材料的工廠。假定

10、N個產(chǎn)地的產(chǎn)量和M家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運費已知，那么如何安排運輸方案可以使總運輸成本最低？公路連接問題 某一地區(qū)有若干個主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市。假定已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最小？上述問題有兩個共同的特點： 一、 它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為最優(yōu)化或優(yōu)化（optimization）問題； 二、 它們都易于用圖形的形式直觀地描述和表達，數(shù)學(xué)上把這種與

11、圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡(luò)（network）。 與圖和網(wǎng)絡(luò)相關(guān)的最優(yōu)化問題就是。 q線性表線性表v每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。q樹形結(jié)構(gòu)樹形結(jié)構(gòu)v每個數(shù)據(jù)元素只有一個直接前驅(qū)，但可能有多個直接后繼。每個數(shù)據(jù)元素只有一個直接前驅(qū)，但可能有多個直接后繼。q圖形結(jié)構(gòu)圖形結(jié)構(gòu)v每個數(shù)據(jù)元素可能有多個直接前驅(qū)和多個直接后繼。每個數(shù)據(jù)元素可能有多個直接前驅(qū)和多個直接后繼。 圖是比線性表和樹復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于計圖是比線性表和樹復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于計算機、邏輯學(xué)、物理、化學(xué)等領(lǐng)域。算機、邏輯學(xué)、物理、化學(xué)等領(lǐng)域。圖的基本特性圖的基本特性網(wǎng)絡(luò)拓

12、撲結(jié)構(gòu)網(wǎng)絡(luò)拓撲結(jié)構(gòu)社交網(wǎng)絡(luò)社交網(wǎng)絡(luò)圖像處理圖像處理物理化學(xué)結(jié)構(gòu)物理化學(xué)結(jié)構(gòu)電腦游戲電腦游戲2022-3-17圖的定義圖的定義圖是由圖是由頂點頂點的的有窮非空有窮非空集合和頂點之間集合和頂點之間邊邊的集合組的集合組成，通常表示為：成，通常表示為： G=(V，E)其中：其中：G表示一個圖，表示一個圖，V是圖是圖G中頂點的集合，中頂點的集合，E是是圖圖G中頂點之間邊的集合。中頂點之間邊的集合。 在線性表中，元素個數(shù)可以為零，稱為空表；在線性表中，元素個數(shù)可以為零，稱為空表；在樹中，結(jié)點個數(shù)可以為零，稱為空樹；在樹中，結(jié)點個數(shù)可以為零，稱為空樹；在圖中，頂點個數(shù)不能為零，但可以沒有邊。在圖中，頂點個數(shù)

13、不能為零，但可以沒有邊。Page 15如果圖的任意兩個頂點之間的邊都如果圖的任意兩個頂點之間的邊都是是無向邊，則稱該圖為無向邊，則稱該圖為無向圖無向圖。若頂點若頂點vi和和vj之間的邊沒有方向，則之間的邊沒有方向，則稱這條邊為稱這條邊為無向邊無向邊，表示為，表示為(vi, ,vj)。若從頂點若從頂點vi到到vj的邊有方向，則稱這的邊有方向，則稱這條邊為條邊為有向邊有向邊，表示為，表示為。 如果圖的任意兩個頂點之間的邊都如果圖的任意兩個頂點之間的邊都是是有向邊，則稱該圖為有向邊，則稱該圖為有向圖有向圖。V1V2V3V4V5V1V2V3V4圖的基本術(shù)語圖的基本術(shù)語 Page 16簡單圖：簡單圖：在

14、圖中，若不存在頂點到其自身的邊，且同在圖中，若不存在頂點到其自身的邊，且同一條邊不重復(fù)出現(xiàn)一條邊不重復(fù)出現(xiàn)。V3V4V5V1V2V3V4V5V1V2非簡單圖非簡單圖 非簡單圖非簡單圖 簡單圖簡單圖V1V2V3V4V5v 數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖。數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖。鄰接、依附鄰接、依附無向圖無向圖中，對于任意兩個頂點中，對于任意兩個頂點vi和頂點和頂點vj，若存在，若存在邊邊(vi，vj)，則稱頂點，則稱頂點vi和頂點和頂點vj互為鄰接點，同時稱邊互為鄰接點，同時稱邊(vi，vj)依附于頂點依附于頂點vi和頂點和頂點vj。V1V2V3V4V5V1的鄰接點：的鄰接點：V2的鄰接點：的鄰

15、接點：V2 、V4V1 、V3 、V52022-3-17鄰接、依附鄰接、依附有向圖有向圖中，對于任意兩個頂點中，對于任意兩個頂點vi和頂點和頂點vj，若存在，若存在弧弧，則稱頂點，則稱頂點vi鄰接到頂點鄰接到頂點vj，頂點，頂點vj鄰接自頂鄰接自頂點點vi，同時稱弧同時稱弧依附于頂點依附于頂點vi和頂點和頂點vj 。 V1V2V3V4V1的鄰接點：的鄰接點：V3的鄰接點：的鄰接點：V2 、V3V42022-3-17無向完全圖無向完全圖：在無向圖中，如果任意兩個頂點之：在無向圖中，如果任意兩個頂點之間都存在邊，間都存在邊，則稱該圖為無向完全圖。則稱該圖為無向完全圖。有向完全圖有向完全圖：在有向圖

16、中，如果任意兩個頂點之：在有向圖中，如果任意兩個頂點之間都存在方向相反的兩條弧，間都存在方向相反的兩條弧，則稱該圖為有向完則稱該圖為有向完全圖。全圖。 V1V2V3V1V2V3V42022-3-17含有含有n個頂點的無向完全圖有個頂點的無向完全圖有多少多少條邊？條邊？含有含有n個頂點的有向完全圖有個頂點的有向完全圖有多少多少條??？條弧？ 含有含有n個頂點的無向完全圖有個頂點的無向完全圖有n(n-1)/2條邊。條邊。 含有含有n個頂點的有向完全圖有個頂點的有向完全圖有n(n-1)條邊。條邊。 V1V2V3V1V2V3V42022-3-17稀疏圖：稀疏圖：稱邊數(shù)很少的圖為稀疏圖；稱邊數(shù)很少的圖為稀

17、疏圖；稠密圖：稠密圖：稱邊數(shù)很多的圖為稠密圖。稱邊數(shù)很多的圖為稠密圖。頂點的度：頂點的度：在無向圖中，頂點在無向圖中，頂點v的的度度是指依附于該頂是指依附于該頂點的邊數(shù)，通常記為點的邊數(shù)，通常記為TD (v)。頂點的入度：頂點的入度：在有向圖中，頂點在有向圖中，頂點v的的入度入度是指以該頂是指以該頂點為點為弧頭弧頭的弧的數(shù)目，的弧的數(shù)目，記為記為ID (v)；頂點頂點的的出度：出度：在有向圖中，頂點在有向圖中，頂點v的的出度出度是指以該頂是指以該頂點為點為弧尾弧尾的弧的數(shù)目，記為的弧的數(shù)目，記為OD (v)。2022-3-17V1V2V3V4V5在具有在具有n個頂點、個頂點、e條邊的無向圖條邊

18、的無向圖G中，各頂點中，各頂點的度之和與邊數(shù)之和的關(guān)系？的度之和與邊數(shù)之和的關(guān)系？ = = =niievTD12)(V1V2V3V4在具有在具有n個頂點、個頂點、e條邊的有向圖條邊的有向圖G中，各頂點中，各頂點的入度之和與各頂點的出度之和的關(guān)系？與邊的入度之和與各頂點的出度之和的關(guān)系？與邊數(shù)之和的關(guān)系？數(shù)之和的關(guān)系？evODvIDiiii= = = = = =11)()(nn2022-3-17權(quán)：權(quán)：是指對邊賦予的有意義的數(shù)值量。是指對邊賦予的有意義的數(shù)值量。網(wǎng)：網(wǎng)：邊上帶權(quán)的圖，也稱網(wǎng)圖。邊上帶權(quán)的圖，也稱網(wǎng)圖。V1V2V3V42785圖結(jié)構(gòu)中的權(quán)和哈夫曼樹中的權(quán)有什么區(qū)別？圖結(jié)構(gòu)中的權(quán)和哈

19、夫曼樹中的權(quán)有什么區(qū)別？2022-3-17路徑：路徑：在無向圖在無向圖G=(V, E)中，從頂點中，從頂點vp到頂點到頂點vq之間之間的的路徑路徑是一個頂點序列是一個頂點序列(vp=vi0,vi1,vi2, , vim=vq)，其，其中，中，(vij-1,vij)E（1jm）。若）。若G是有向圖，則路徑是有向圖，則路徑也是有方向的，頂點序列滿足也是有方向的，頂點序列滿足E。V1V2V3V4V5一般情況下，圖中兩個頂點之間的路徑不唯一。一般情況下，圖中兩個頂點之間的路徑不唯一。在什么情況下唯一？在什么情況下唯一？V1 到到V4的路徑：的路徑： V1 V4 V1 V2 V3 V4 V1 V2 V5

20、V3 V42022-3-17路徑長度：路徑長度：非帶權(quán)圖非帶權(quán)圖路徑路徑上邊的上邊的個數(shù)個數(shù)帶權(quán)圖帶權(quán)圖路徑上路徑上各邊的各邊的權(quán)之和權(quán)之和V1V2V3V4V5V1 V4：長度為：長度為1V1 V2 V3 V4 ：長度為：長度為3V1 V2 V5V3 V4 ：長度為：長度為42022-3-17路徑長度：路徑長度：非帶權(quán)圖非帶權(quán)圖路徑路徑上邊的上邊的個數(shù)個數(shù)帶權(quán)圖帶權(quán)圖路徑上路徑上各邊的各邊的權(quán)之和權(quán)之和V1 V4：長度為：長度為8V1 V2 V3 V4 ：長度為：長度為7V1 V2 V5V3 V4 ：長度為：長度為15V1V2V3V4V52563282022-3-17回路（環(huán)）回路（環(huán)）：第一

21、個頂點和最后一個頂點相同的路徑。：第一個頂點和最后一個頂點相同的路徑。簡單路徑：簡單路徑：序列中頂點不重復(fù)出現(xiàn)的路徑。序列中頂點不重復(fù)出現(xiàn)的路徑。簡單回路（簡單環(huán)）：簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點外，除了第一個頂點和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路。其余頂點不重復(fù)出現(xiàn)的回路。V1V2V3V4V5V1V2V3V42022-3-17子圖：子圖：若圖若圖G=（V，E），），G=（V，E），如果），如果V V 且且E E ，則稱圖，則稱圖G是是G的子圖。的子圖。V1V2V3V4V5V1V2V3V4V5V1V3V42022-3-17連通圖：連通圖：在無向圖中，如果從一個頂點在無

22、向圖中，如果從一個頂點vi到另一個頂?shù)搅硪粋€頂點點vj(ij)有路徑，則稱頂點有路徑，則稱頂點vi和和vj是連通的。如果圖中是連通的。如果圖中任意兩個頂點都是連通的，則稱該圖是連通任意兩個頂點都是連通的，則稱該圖是連通圖。圖。連通分量：連通分量：非連通圖的極大連通子圖稱為連通分量。非連通圖的極大連通子圖稱為連通分量。 如何求得一個非連通圖的連通分量如何求得一個非連通圖的連通分量? ?1.含有極大含有極大頂點頂點數(shù)；數(shù)；2. 依附于這些頂點的所有依附于這些頂點的所有邊邊。2022-3-17連通分量連通分量1 V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量連通分量2v連通分量是對

23、無向圖的一種劃分。連通分量是對無向圖的一種劃分。Page 322022-3-17強連通圖：強連通圖：在在有向圖有向圖中，對圖中任意一對頂點中，對圖中任意一對頂點vi和和vj (ij)，若從頂點，若從頂點vi到頂點到頂點vj和從頂點和從頂點vj到頂點到頂點vi均有路徑均有路徑，則稱該有向圖是強連通圖。，則稱該有向圖是強連通圖。強連通分量：強連通分量：非強連通圖非強連通圖的極大強連通子圖。的極大強連通子圖。 如何求得一個有向非連通圖的強連通分量如何求得一個有向非連通圖的強連通分量? ?2022-3-17V1V2V3V4強連通分量強連通分量1 強連通分量強連通分量2V1V3V4V22022-3-17

24、生成樹：生成樹：n個頂點的連通圖個頂點的連通圖G的生成樹是包含的生成樹是包含G中中全全部頂點部頂點的一個極小連通的一個極小連通子圖。子圖。 生成森林：生成森林：在非連通圖中，由每個連通分量都可以得在非連通圖中，由每個連通分量都可以得到一棵生成樹，這些連通分到一棵生成樹，這些連通分量的生成樹就組成了一個量的生成樹就組成了一個非連通圖的非連通圖的生成森林生成森林。 如何理解極小連通子圖如何理解極小連通子圖?多多構(gòu)成回路構(gòu)成回路少少不連通不連通含有含有n-1條邊條邊2022-3-17V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成樹生成樹生成森林生

25、成森林q圖的概念與基本術(shù)語q圖的類型定義與存儲q圖的遍歷q圖的連通性與最小生成樹Page 362022-3-172022-3-17圖的抽象數(shù)據(jù)類型定義如下：圖的抽象數(shù)據(jù)類型定義如下：ADT ADT GraphGraph 數(shù)據(jù)對象數(shù)據(jù)對象V V ：V V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂是具有相同特性的數(shù)據(jù)元素的集合，稱為頂 點集。點集。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R R ：R=VRR=VRVRVR| v,wV| v,wV且且P(v,w)P(v,w)，表示從表示從v v到到w w的的 弧，弧，謂詞謂詞P(v,w)P(v,w)定義了弧定義了弧的意義的意義 或信息或信息 Page 382022-3-17G1

26、=(G1=(V1V1, , VR1VR1) )V1 = A, B, C, D, EV1 = A, B, C, D, EVR1=,VR1=, , ,G2=(G2=(V2V2, , VR2VR2) )V2=A, B, C, D, E, FV2=A, B, C, D, E, FVR2=(A,B),(A,E),(B,E),(C,D),VR2=(A,B),(A,E),(B,E),(C,D), (D,F),(B,F),(C,F) (D,F),(B,F),(C,F) Page 392022-3-17CreateGraph(&G, V, VR);CreateGraph(&G, V, VR);初始條件：初始條件

27、：V V 是圖的頂點集，是圖的頂點集，VR VR 是圖中弧的集合。是圖中弧的集合。操作結(jié)果：按操作結(jié)果：按 V V 和和 VR VR 的定義的定義構(gòu)造圖構(gòu)造圖 G G。DestroyGraph(&G);DestroyGraph(&G);初始條件：圖初始條件：圖 G G 存在。存在。操作結(jié)果：操作結(jié)果：銷毀圖銷毀圖 G G。LocateVex(G, u);LocateVex(G, u);初始條件：圖初始條件：圖 G G 存在，存在，u u 和和 G G 中頂點有相同特征。中頂點有相同特征。操作結(jié)果：若操作結(jié)果：若 G G 中存在和中存在和 u u 相同的頂點，則相同的頂點，則返回該頂點返回該頂點

28、 在圖中位置在圖中位置；否則返回其它信息。；否則返回其它信息。GetVex(G, v);GetVex(G, v);初始條件：圖初始條件：圖 G G 存在，存在，v v 是是 G G 中某個頂點。中某個頂點。操作結(jié)果：返回操作結(jié)果：返回 v v 的值的值。FirstAdjVex(G, v);FirstAdjVex(G, v);初始條件：圖初始條件：圖 G G 存在，存在，v v 是是 G G 中某個頂點。中某個頂點。操作結(jié)果：操作結(jié)果：返回返回 v v 的第一個鄰接點。的第一個鄰接點。若該頂點在若該頂點在 G G 中沒中沒 有鄰接點，則返回有鄰接點，則返回“空空”。NextAdjVex(G, v

29、, w);NextAdjVex(G, v, w);初始條件：圖初始條件：圖 G G 存在，存在，v v 是是 G G 中某個頂點，中某個頂點，w w 是是 v v 的的 鄰接頂點。鄰接頂點。操作結(jié)果：操作結(jié)果：返回返回 v v 的（相對于的（相對于 w w 的）下一個鄰接點。的）下一個鄰接點。若若 w w 是是 v v 的最后一個鄰接點，則返回的最后一個鄰接點，則返回“空空”。Page 412022-3-17PutVex(&G, v, value);PutVex(&G, v, value);初始條件：圖初始條件：圖 G G 存在，存在，v v 是是 G G 中某個頂點。中某個頂點。操作結(jié)果：操

30、作結(jié)果：對對 v v 賦值賦值 valuevalue。InsertVex(&G, v);InsertVex(&G, v);初始條件：圖初始條件：圖 G G 存在，存在，v v 和圖中頂點有相同特征。和圖中頂點有相同特征。操作結(jié)果：在圖操作結(jié)果：在圖 G G 中中增添新頂點增添新頂點 v v。DeleteVex(&G, v);DeleteVex(&G, v);初始條件：圖初始條件：圖 G G 存在，存在，v v 是是 G G 中某個頂點。中某個頂點。操作結(jié)果：操作結(jié)果：刪除刪除 G G 中頂點中頂點 v v 及其相關(guān)的弧及其相關(guān)的弧。2022-3-17InsertArc(&G, v, w);In

31、sertArc(&G, v, w);初始條件：圖初始條件：圖 G G 存在，存在，v v 和和 w w 是是 G G 中兩個頂點。中兩個頂點。操作結(jié)果：在操作結(jié)果：在 G G 中中增添弧增添弧，若，若 G G 是是無向的，則還無向的，則還 增添對稱弧增添對稱弧。DeleteArc(&G, v, w);DeleteArc(&G, v, w);初始條件：圖初始條件：圖 G G 存在，存在，v v 和和 w w 是是 G G 中兩個頂點。中兩個頂點。操作結(jié)果：在操作結(jié)果：在 G G 中中刪除弧刪除弧，若若 G G 是是無向的，則還無向的，則還 刪除對稱弧刪除對稱弧。Page 432022-3-17D

32、FSTraverse(G, Visit();DFSTraverse(G, Visit();初始條件：圖初始條件：圖 G G 存在，存在，Visit Visit 是頂點的應(yīng)用函數(shù)。是頂點的應(yīng)用函數(shù)。操作結(jié)果：對圖操作結(jié)果：對圖 G G 進行進行深度優(yōu)先深度優(yōu)先遍歷。遍歷過程中對每遍歷。遍歷過程中對每 個頂點調(diào)用函數(shù)個頂點調(diào)用函數(shù)Visit Visit 一次且僅一次。一旦一次且僅一次。一旦 visit() visit() 失敗，則操作失敗。失敗，則操作失敗。BFSTraverse(G, Visit();BFSTraverse(G, Visit();初始條件：圖初始條件：圖 G G 存在，存在，Vi

33、sit Visit 是頂點的應(yīng)用函數(shù)。是頂點的應(yīng)用函數(shù)。操作結(jié)果：對圖操作結(jié)果：對圖 G G 進行進行廣度優(yōu)先廣度優(yōu)先遍歷。遍歷過程中對每遍歷。遍歷過程中對每 個頂點調(diào)用函數(shù)個頂點調(diào)用函數(shù)Visit Visit 一次且僅一次。一旦一次且僅一次。一旦 visit() visit() 失敗，則操作失敗。失敗，則操作失敗。 ADT Graph ADT Graph2022-3-17是否可以采用頂點的順序存儲結(jié)構(gòu)存儲圖是否可以采用頂點的順序存儲結(jié)構(gòu)存儲圖?圖的特點：頂點之間的關(guān)系是圖的特點：頂點之間的關(guān)系是m: :n，即，即任何兩任何兩個頂點之間都可能存在關(guān)系（邊），無法通過個頂點之間都可能存在關(guān)系（邊

34、），無法通過存儲位置表示這種任意的邏輯關(guān)系，所以，圖存儲位置表示這種任意的邏輯關(guān)系，所以，圖無法采用順序存儲結(jié)構(gòu)。無法采用順序存儲結(jié)構(gòu)。如何存儲圖如何存儲圖?考慮圖的定義，圖是由頂點和邊組成的，分別考慮圖的定義，圖是由頂點和邊組成的，分別考慮如何存儲頂點、如何存儲邊?？紤]如何存儲頂點、如何存儲邊。q 數(shù)組表示法數(shù)組表示法( (鄰接矩陣鄰接矩陣) )v將圖的將圖的頂點信息存儲在一個一維數(shù)組中頂點信息存儲在一個一維數(shù)組中，并將它的，并將它的鄰接矩陣存儲在一個二維數(shù)組中鄰接矩陣存儲在一個二維數(shù)組中即構(gòu)成圖的數(shù)組表即構(gòu)成圖的數(shù)組表示。示。v假設(shè)圖中頂點數(shù)為假設(shè)圖中頂點數(shù)為n n，則鄰接矩陣，則鄰接矩陣

35、A A定義為定義為=，其它0E(G)v,v或)v,(v若1,jijijiA網(wǎng)的鄰接矩陣的定義為，當(dāng)網(wǎng)的鄰接矩陣的定義為，當(dāng)v vi i到到v vj j有弧相鄰接時，有弧相鄰接時，a aijij的值應(yīng)為該弧上的權(quán)值，否則為的值應(yīng)為該弧上的權(quán)值，否則為。1 1、圖的鄰接矩陣表示法、圖的鄰接矩陣表示法2022-3-17v圖的數(shù)組圖的數(shù)組( (鄰接矩陣鄰接矩陣) )存儲表示存儲表示#define INFINITY #define INFINITY INT_MAX; INT_MAX; / / 最大值最大值#define MAX_VERTEX_NUM #define MAX_VERTEX_NUM 20;2

36、0;/ / 最大頂點個數(shù)最大頂點個數(shù)typedef enum DG,DN,UDG,UDN GraphKind;typedef enum DG,DN,UDG,UDN GraphKind;/ / 有向圖有向圖, ,有向網(wǎng)有向網(wǎng), ,無向圖無向圖, ,無向網(wǎng)無向網(wǎng) typedef struct ArcCell typedef struct ArcCell VRType VRType adj; adj; / VRType/ VRType是頂點關(guān)系類型。對無權(quán)圖，用是頂點關(guān)系類型。對無權(quán)圖，用1 1或或0 0 / / 表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。InfoTyp

37、e InfoType * *info; info; / / 該弧的相關(guān)信息該弧的相關(guān)信息 ArcCell, ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUMAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; ;typedef struct typedef struct VertexType VertexType vexsMAX_VERTEX_NUMvexsMAX_VERTEX_NUM; ; / / 頂點信息頂點信息AdjMatrix AdjMatrix arcsarcs; ; / / 鄰接矩陣鄰接矩陣int int vexn

38、um, arcnumvexnum, arcnum; ; / / 圖的當(dāng)前頂點數(shù)和弧圖的當(dāng)前頂點數(shù)和弧( (邊邊) )數(shù)數(shù)GraphKind GraphKind kindkind; ; / / 圖的種類標(biāo)志圖的種類標(biāo)志 MGraphMGraph; ;2022-3-17G1G1BDAC0 01 11 10 00 00 00 00 0G G1 1. .a ar rc cs s = =0 00 00 01 11 10 00 00 0G1.vexs=A,B,C,DG1.vexnum=4G1.arcnum=4G1.kind=DGPage 482022-3-17V1V2V3V4V1 V2 V3 V4vert

39、ex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何求頂點如何求頂點 i 的出度？的出度？鄰接矩陣的第鄰接矩陣的第 i 行元素之和。行元素之和。Page 492022-3-17V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何求頂點如何求頂點 i 的入度？的入度？鄰接矩陣的第鄰接矩陣的第 i 列元素之和。列元素之和。2022-3-17V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0

40、0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何判斷從頂點如何判斷從頂點 i 到頂點到頂點 j 是否存在邊？是否存在邊？測試鄰接矩陣中相應(yīng)位置的元素測試鄰接矩陣中相應(yīng)位置的元素arcij是否為是否為1。2022-3-17AECBDG2G20 01 10 01 10 01 10 01 10 01 1G G2 2. .a ar rc cs s = =0 01 10 01 11 11 10 01 10 00 00 01 11 10 00 0G2.vexs=A,B,C,D,EG2.vexnum=5G2.arcnum=6G2.kind=UDG2022-3-17如何求

41、頂點如何求頂點i的度？的度？V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4鄰接矩陣的第鄰接矩陣的第i行（或第行（或第i列）非零元素的個數(shù)。列）非零元素的個數(shù)。2022-3-17如何判斷頂點如何判斷頂點 i 和和 j 之間是否存在邊？之間是否存在邊？V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4測試鄰接矩陣中相應(yīng)位置的元素測試鄰接矩陣中相應(yīng)位置的元素arcij是否為是

42、否為1。Page 542022-3-17如何求頂點如何求頂點 i 的所有鄰接點？的所有鄰接點？V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4將數(shù)組中第將數(shù)組中第 i 行元素掃描一遍，若行元素掃描一遍，若arcij為為1，則，則頂點頂點 j 為頂點為頂點 i 的鄰接點。的鄰接點。網(wǎng)圖的鄰接矩陣定義：網(wǎng)圖的鄰接矩陣定義： arcij wij 若若(vi, vj)E（或（或E） /0 若若i=j 其他其他V1V2V3V42785 2 5 8 7 arc=Page 562022-3-17

43、5 57 73 35 54 48 8G G3 3. .a ar rc cs s = =7 72 21 14 42 26 63 38 81 16 6A AD DE EB BC C7 75 53 31 18 86 64 42 2G3G3G3.vexs=A,B,C,D,EG3.vexnum=5G3.arcnum=8G3.kind=UDN2022-3-17v鄰接矩陣表示的特點鄰接矩陣表示的特點：無向圖無向圖的鄰接的鄰接矩陣對稱矩陣對稱，可，可壓縮存儲壓縮存儲；有；有n n個頂點的無向圖需個頂點的無向圖需存儲空間為存儲空間為n(n+1)/2n(n+1)/2。有向圖有向圖鄰接鄰接矩陣不一定對稱矩陣不一定對

44、稱；有；有n n個頂點的有向圖需存儲空間個頂點的有向圖需存儲空間為為n n。無向圖無向圖中頂點中頂點ViVi的度的度TD(Vi)TD(Vi)是鄰接矩陣是鄰接矩陣A A中第中第i i行元素之和行元素之和。有向圖有向圖中，中，頂點頂點ViVi的的出度是出度是A A中第中第i i行元素之和行元素之和。頂點頂點ViVi的的入度是入度是A A中第中第i i列元素之和列元素之和。v鄰接矩陣的優(yōu)缺點鄰接矩陣的優(yōu)缺點優(yōu)點優(yōu)點：容易判定頂點間有無邊（?。┖陀嬎沩旤c的度（出度、：容易判定頂點間有無邊（弧）和計算頂點的度（出度、 入度）。入度）。缺點缺點：邊數(shù)較少時，空間浪費較大。：邊數(shù)較少時，空間浪費較大。202

45、2-3-17q 引入原因引入原因v鄰接矩陣在稀疏圖時空間浪費較大。鄰接矩陣在稀疏圖時空間浪費較大。q 實現(xiàn)實現(xiàn)v為圖中為圖中每個頂點建立一個單鏈表（邊表）每個頂點建立一個單鏈表（邊表），第，第i i個單鏈表中的結(jié)個單鏈表中的結(jié)點表示依附于頂點點表示依附于頂點ViVi的邊（有向圖中指以的邊（有向圖中指以ViVi為尾的弧）。為尾的?。每個鏈表附設(shè)一個表頭結(jié)點（頂點結(jié)點）每個鏈表附設(shè)一個表頭結(jié)點（頂點結(jié)點）。表結(jié)點表結(jié)點adjvexadjvexnextarcnextarcinfoinfo與與ViVi鄰接的鄰接的點在表頭數(shù)點在表頭數(shù)組中的位置組中的位置頭結(jié)點頭結(jié)點datadatafirstarcf

46、irstarcPage 592022-3-17#define MAX_VERTEX_NUM 20;#define MAX_VERTEX_NUM 20;typedef struct ArcNode typedef struct ArcNode int int adjvex; adjvex; / / 該弧所指向的頂點的位置該弧所指向的頂點的位置struct ArcNode struct ArcNode * *nextarc;nextarc; / / 指向下一條弧的指針指向下一條弧的指針I(yè)nfoType InfoType * *info;info; / / 該弧相關(guān)信息的指針該弧相關(guān)信息的指針 Ar

47、cNode; ArcNode; / / 邊表結(jié)點邊表結(jié)點typedef struct VNode typedef struct VNode VertexType VertexType data;data;/ / 頂點信息頂點信息ArcNode ArcNode * *firstarc;firstarc; / / 指向第一條依附該頂點的弧指向第一條依附該頂點的弧 AdjListMAX_VERTEX_NUMAdjListMAX_VERTEX_NUM; ; /頂點表頂點表typedef struct typedef struct AdjList AdjList verticesvertices; ;

48、/ / 頂點數(shù)組頂點數(shù)組int vexnum, arcnum;int vexnum, arcnum; / / 圖的當(dāng)前頂點數(shù)和弧數(shù)圖的當(dāng)前頂點數(shù)和弧數(shù)int kind;int kind; / / 圖的種類標(biāo)志圖的種類標(biāo)志 ALGraphALGraph; ;Page 602022-3-1710323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2邊表中的結(jié)點表示什么？邊表中的結(jié)點表示什么？每個結(jié)點對應(yīng)圖中的一條邊，每個結(jié)點對應(yīng)圖中的一條邊，鄰接表的空間復(fù)雜度為鄰接表的空間復(fù)雜度為O(n+2e)。2022-3-1710323101 V1 V2 V3 V4012

49、3vertex firstedgeV1V3V4V2如何求頂點如何求頂點 i 的度？的度？頂點頂點i的邊表中結(jié)點的個數(shù)。的邊表中結(jié)點的個數(shù)。無向圖的鄰接表無向圖的鄰接表2022-3-17如何判斷頂點如何判斷頂點 i 和頂點和頂點 j之間是否存在邊之間是否存在邊?測試頂點測試頂點 i 的邊表中是否存的邊表中是否存在終點為在終點為 j 的結(jié)點。的結(jié)點。10323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2Page 63有向圖的鄰接表有向圖的鄰接表V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求頂點如何求頂點 i

50、的出度？的出度？頂點頂點 i 的出邊表中結(jié)點的個數(shù)。的出邊表中結(jié)點的個數(shù)。2022-3-17V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求頂點如何求頂點 i 的入度？的入度？各頂點的出邊表中以頂點各頂點的出邊表中以頂點 i 為為終點的結(jié)點個數(shù)。終點的結(jié)點個數(shù)。Page 652022-3-17V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求頂點如何求頂點 i 的所有鄰接點？的所有鄰接點？遍歷頂點遍歷頂點 i 的邊表，該邊表中的的邊表，該邊表中的所有終點都是頂點所有終點都是頂點 i 的鄰接點。的鄰接點。P

51、age 662022-3-17網(wǎng)圖的鄰接表網(wǎng)圖的鄰接表V1V2V3V427852 1 V1 V2 V3 V40123vertex firstedge5 28 37 02022-3-17v優(yōu)缺點優(yōu)缺點優(yōu)點優(yōu)點：空間較??；無向圖容易求各頂點的度；有向：空間較省；無向圖容易求各頂點的度；有向圖容易求頂點的出度；圖容易求頂點的出度；缺點缺點：求有向圖頂點的入度則不容易，要遍歷整個：求有向圖頂點的入度則不容易，要遍歷整個表。表。為了求頂點的入度，有時可設(shè)逆鄰接表（指向某頂為了求頂點的入度，有時可設(shè)逆鄰接表（指向某頂點的鄰接點鏈接成單鏈表）。點的鄰接點鏈接成單鏈表）。bdac0123acdbdata fi

52、rstarc3 0 02adjvex next逆鄰接表逆鄰接表2022-3-17q 引入原因引入原因v對于同一個對于同一個有向圖需要同時用鄰接表和逆鄰接表有向圖需要同時用鄰接表和逆鄰接表時，不方便。時，不方便。q 實現(xiàn)實現(xiàn)v將在有向圖的將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結(jié)鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結(jié)點表示點表示，由于在鄰接表和逆鄰接表中的頂點，由于在鄰接表和逆鄰接表中的頂點數(shù)據(jù)數(shù)據(jù)是相同的，則在是相同的，則在十字鏈表中十字鏈表中只需要出現(xiàn)一次只需要出現(xiàn)一次，但需，但需保留分別指向第一條保留分別指向第一條 出弧出弧 和和第一條第一條 入弧入弧 的指針的指針。G

53、1G1bdac0123acdbdatafirstarc 2 1 3 0adjvex next鄰接表鄰接表2022-3-17q 引入原因引入原因v對于同一個對于同一個有向圖需要同時用鄰接表和逆鄰接表有向圖需要同時用鄰接表和逆鄰接表時，不方便。時，不方便。q 實現(xiàn)實現(xiàn)v將在有向圖的將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結(jié)鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結(jié)點表示點表示，由于在鄰接表和逆鄰接表中的頂點，由于在鄰接表和逆鄰接表中的頂點數(shù)據(jù)數(shù)據(jù)是相同的，則在是相同的，則在十字鏈表中十字鏈表中只需要出現(xiàn)一次只需要出現(xiàn)一次，但需，但需保留分別指向第一條保留分別指向第一條 出弧出弧 和

54、和第一條第一條 入弧入弧 的指針的指針。G1G1bdac逆鄰接表逆鄰接表0123acdbdatafirstarc3 0 02adjvex next2022-3-17弧結(jié)點弧結(jié)點tailvextailvex headvexheadvexhlinkhlinktlinktlinkinfoinfo頂點結(jié)點頂點結(jié)點datadatafirstinfirstinfirstoutfirstout弧尾弧尾位置位置弧頭弧頭位置位置弧頭相同的下弧頭相同的下一條弧指針一條弧指針弧相關(guān)信息弧相關(guān)信息的指針的指針指向該頂點指向該頂點第一條入弧第一條入弧指向該頂點指向該頂點第一條出弧第一條出弧2022-3-17 0 2 0

55、 1 2 3 2 0 3 2 3 1 3 0bdacab cd0123求結(jié)點的入度求結(jié)點的入度和出度的方法？和出度的方法？弧頭弧頭弧尾弧尾出邊出邊入邊入邊同尾同尾同頭同頭Page 722022-3-17q 引入原因引入原因v無向圖的鄰接表中無向圖的鄰接表中每一條邊有兩個結(jié)點，每一條邊有兩個結(jié)點，給對圖的邊進行訪問的給對圖的邊進行訪問的操作帶來不便。有些時候需要同時找到表示同一條邊的兩個結(jié)點操作帶來不便。有些時候需要同時找到表示同一條邊的兩個結(jié)點（如刪除一條邊）。（如刪除一條邊）。aecbd0123acdbdatafirstarc 3 1 0 1adjvex next4e 3 2 4 0 42

56、12Page 73q 實現(xiàn)實現(xiàn)v每條邊用一個結(jié)點表示。每條邊用一個結(jié)點表示。邊結(jié)點邊結(jié)點markmarkivexivexilinkilinkjvexjvexjlinkjlinkinfoinfo頂點結(jié)點頂點結(jié)點markmarkfirstedgefirstedge訪問訪問標(biāo)記標(biāo)記邊依附的邊依附的一個頂點一個頂點邊依附的另邊依附的另一個頂點一個頂點依附這個頂依附這個頂點的下一條點的下一條邊指針邊指針依附這個頂依附這個頂點的下一條點的下一條邊指針邊指針訪問訪問標(biāo)記標(biāo)記指向第一條指向第一條 依附該頂點的依附該頂點的邊邊2022-3-17aecbd0123acdb4e 0 1 0 3 2 3 2 1 2

57、4 4 1q圖的概念與基本術(shù)語q圖的類型定義與存儲q圖的遍歷q圖的連通性與最小生成樹Page 752022-3-172022-3-17q 圖的遍歷圖的遍歷v從圖中某一頂點出發(fā)，訪問圖中其余頂點，使每個頂點被訪問一從圖中某一頂點出發(fā)，訪問圖中其余頂點，使每個頂點被訪問一次且只被訪問一次次且只被訪問一次。v可以從圖中可以從圖中任意一個頂點出發(fā)任意一個頂點出發(fā)進行遍歷。進行遍歷。v遍歷中需解決的問題遍歷中需解決的問題確定一搜索路徑確定一搜索路徑；確保確保每個頂點被訪問到每個頂點被訪問到；確保每個頂點確保每個頂點只能被訪問一次只能被訪問一次。v解決方法解決方法深度優(yōu)先和廣度優(yōu)先。深度優(yōu)先和廣度優(yōu)先。設(shè)

58、設(shè)輔助數(shù)組輔助數(shù)組visitedvisited，初始時，數(shù)組元素的值均為，初始時，數(shù)組元素的值均為0 0或或falsefalse，表示未被遍歷，一旦遍歷，就置為表示未被遍歷，一旦遍歷，就置為1 1或或truetrue。Page 77q 方法方法v從圖的某一頂點從圖的某一頂點V0V0出發(fā)，訪問此頂點；出發(fā)，訪問此頂點；v然后依次從然后依次從V0V0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和至圖中所有和V0V0相通的頂點都被訪問到；相通的頂點都被訪問到；v若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂若此時圖中尚有頂點未被訪問，則另選圖

59、中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止。點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止。訪問任意一個與訪問任意一個與V0V0鄰接的頂點鄰接的頂點W1W1，再從，再從W1W1出發(fā)；出發(fā)；訪問與訪問與W1W1鄰接且未被訪問過的任意頂點鄰接且未被訪問過的任意頂點W2W2，再從，再從W2W2出發(fā)；出發(fā)；重復(fù)以上過程，直到一個所有鄰接點都被訪問過的頂點為止；重復(fù)以上過程，直到一個所有鄰接點都被訪問過的頂點為止；退回到尚有鄰接點未被訪問過的頂點，再從該頂點出發(fā)；退回到尚有鄰接點未被訪問過的頂點，再從該頂點出發(fā)；直到所有的被訪問過的頂點的鄰接點都已被訪問過為止。直到所有

60、的被訪問過的頂點的鄰接點都已被訪問過為止。Page 782022-3-17深一層遞歸深一層遞歸遞歸返回遞歸返回深度優(yōu)先遍歷序列深度優(yōu)先遍歷序列?入棧序列入棧序列?出棧序列出棧序列?V1V3V2V4V5V6V7V8 V1遍歷序列：遍歷序列：V1V2 V2V4 V4V5 V5Page 792022-3-17深一層遞歸深一層遞歸遞歸返回遞歸返回深度優(yōu)先遍歷序列深度優(yōu)先遍歷序列?入棧序列入棧序列?出棧序列出棧序列?V1V3V2V4V5V6V7V8 V1遍歷序列：遍歷序列：V1V2 V2V4 V4V5V8 V8Page 802022-3-17深一層遞歸深一層遞歸遞歸返回遞歸返回深度優(yōu)先遍歷序列深度優(yōu)先遍