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

1、Page 12022-2-14p 畫出下列二叉鏈表代表的二叉樹（畫出下列二叉鏈表代表的二叉樹（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-2-14第第8-1講講 圖的基礎(chǔ)知識圖的基礎(chǔ)知識

3、清華大學(xué)清華大學(xué) 自動化系自動化系 黃雙喜黃雙喜 博士、副教授博士、副教授Page 32022-2-14q學(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)的特點(diǎn)及其結(jié)構(gòu)的特點(diǎn)及其選用原則選用原則。v熟練掌握圖的兩種熟練掌握圖的兩種遍歷遍歷算法及應(yīng)用。算法及應(yīng)用。v理解各種圖的理解各種圖的應(yīng)用問題的算法應(yīng)用問題的算法。q重點(diǎn)和難點(diǎn)重點(diǎn)和難點(diǎn)v重點(diǎn)：圖的各種應(yīng)用問題的算法都比較經(jīng)典，注意重點(diǎn)：圖的各種應(yīng)用問題的算法都比較經(jīng)典，注意理理解各種圖的算法及其應(yīng)用場合解各種圖的算法及其應(yīng)用場合。Page

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

5、歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級數(shù)論的歐拉常數(shù)，復(fù)變函數(shù)的程的歐拉方程，級數(shù)論的歐拉常數(shù)，復(fù)變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計(jì)他那不倦的一生，共寫下歐拉公式等等。據(jù)統(tǒng)計(jì)他那不倦的一生，共寫下了了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-2-14能否從某個(gè)地方出發(fā)，穿過所有的橋僅一次能否從某個(gè)地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點(diǎn)？

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

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

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

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

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

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

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

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

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

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

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

18、的無向圖G中，各頂點(diǎn)中，各頂點(diǎn)的度之和與邊數(shù)之和的關(guān)系？的度之和與邊數(shù)之和的關(guān)系？ = = =niievTD12)(V1V2V3V4在具有在具有n個(gè)頂點(diǎn)、個(gè)頂點(diǎn)、e條邊的有向圖條邊的有向圖G中，各頂點(diǎn)中，各頂點(diǎn)的入度之和與各頂點(diǎn)的出度之和的關(guān)系？與邊的入度之和與各頂點(diǎn)的出度之和的關(guān)系？與邊數(shù)之和的關(guān)系？數(shù)之和的關(guān)系？evODvIDiiii= = = = = =11)()(nn2022-2-14權(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-2-14路徑：路徑：在無向圖在無向圖G=(V, E)中，從頂點(diǎn)中，從頂點(diǎn)vp到頂點(diǎn)到頂點(diǎn)vq之間之間的的路徑路徑是一個(gè)頂點(diǎn)序列是一個(gè)頂點(diǎn)序列(vp=vi0,vi1,vi2, , vim=vq)，其，其中，中，(vij-1,vij)E（1jm）。若）。若G是有向圖，則路徑是有向圖，則路徑也是有方向的，頂點(diǎn)序列滿足也是有方向的，頂點(diǎn)序列滿足E。V1V2V3V4V5一般情況下，圖中兩個(gè)頂點(diǎn)之間的路徑不唯一。一般情況下，圖中兩個(gè)頂點(diǎn)之間的路徑不唯一。在什么情況下唯一？在什么情況下唯一？V1 到到V4的路徑：的路徑： V1 V4 V1 V2 V3 V4 V1 V2 V5

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

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

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

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

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

25、成森林q圖的概念與基本術(shù)語q圖的類型定義與存儲q圖的遍歷q圖的連通性與最小生成樹Page 362022-2-142022-2-14圖的抽象數(shù)據(jù)類型定義如下：圖的抽象數(shù)據(jù)類型定義如下：ADT ADT GraphGraph 數(shù)據(jù)對象數(shù)據(jù)對象V V ：V V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂是具有相同特性的數(shù)據(jù)元素的集合，稱為頂 點(diǎn)集。點(diǎn)集。數(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-2-14G1

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-2-14CreateGraph(&G, V, VR);CreateGraph(&G, V, VR);初

27、始條件：初始條件：V V 是圖的頂點(diǎn)集，是圖的頂點(diǎn)集，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 中頂點(diǎn)有相同特征。中頂點(diǎn)有相同特征。操作結(jié)果：若操作結(jié)果：若 G G 中存在和中存在和 u u 相同的頂點(diǎn)，則相

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

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

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

31、的弧及其相關(guān)的弧。2022-2-14InsertArc(&G, v, w);InsertArc(&G, v, w);初始條件：圖初始條件：圖 G G 存在，存在，v v 和和 w w 是是 G G 中兩個(gè)頂點(diǎn)。中兩個(gè)頂點(diǎn)。操作結(jié)果：在操作結(jié)果：在 G G 中中增添弧增添弧，若，若 G G 是是無向的，則還無向的，則還 增添對稱弧增添對稱弧。DeleteArc(&G, v, w);DeleteArc(&G, v, w);初始條件：圖初始條件：圖 G G 存在，存在，v v 和和 w w 是是 G G 中兩個(gè)頂點(diǎn)。中兩個(gè)頂點(diǎn)。操作結(jié)果：在操作結(jié)果：在 G G 中中刪

32、除弧刪除弧，若若 G G 是是無向的，則還無向的，則還 刪除對稱弧刪除對稱弧。Page 432022-2-14DFSTraverse(G, Visit();DFSTraverse(G, Visit();初始條件：圖初始條件：圖 G G 存在，存在，Visit Visit 是頂點(diǎn)的應(yīng)用函數(shù)。是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對圖操作結(jié)果：對圖 G G 進(jìn)行進(jìn)行深度優(yōu)先深度優(yōu)先遍歷。遍歷過程中對每遍歷。遍歷過程中對每 個(gè)頂點(diǎn)調(diào)用函數(shù)個(gè)頂點(diǎn)調(diào)用函數(shù)Visit Visit 一次且僅一次。一旦一次且僅一次。一旦 visit() visit() 失敗，則操作失敗。失敗，則操作失敗。BFSTraverse(G,

33、Visit();BFSTraverse(G, Visit();初始條件：圖初始條件：圖 G G 存在，存在，Visit Visit 是頂點(diǎn)的應(yīng)用函數(shù)。是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對圖操作結(jié)果：對圖 G G 進(jìn)行進(jìn)行廣度優(yōu)先廣度優(yōu)先遍歷。遍歷過程中對每遍歷。遍歷過程中對每 個(gè)頂點(diǎn)調(diào)用函數(shù)個(gè)頂點(diǎn)調(diào)用函數(shù)Visit Visit 一次且僅一次。一旦一次且僅一次。一旦 visit() visit() 失敗，則操作失敗。失敗，則操作失敗。 ADT Graph ADT Graph2022-2-14是否可以采用頂點(diǎn)的順序存儲結(jié)構(gòu)存儲圖是否可以采用頂點(diǎn)的順序存儲結(jié)構(gòu)存儲圖?圖的特點(diǎn)：頂點(diǎn)之間的關(guān)系是圖的特點(diǎn)：頂

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

35、維數(shù)組中即構(gòu)成圖的數(shù)組表即構(gòu)成圖的數(shù)組表示。示。v假設(shè)圖中頂點(diǎn)數(shù)為假設(shè)圖中頂點(diǎn)數(shù)為n n，則鄰接矩陣，則鄰接矩陣A A定義為定義為=，其它0E(G)v,v或)v,(v若1,jijijiA網(wǎng)的鄰接矩陣的定義為，當(dāng)網(wǎng)的鄰接矩陣的定義為，當(dāng)v vi i到到v vj j有弧相鄰接時(shí)，有弧相鄰接時(shí)，a aijij的值應(yīng)為該弧上的權(quán)值，否則為的值應(yīng)為該弧上的權(quán)值，否則為。1 1、圖的鄰接矩陣表示法、圖的鄰接矩陣表示法2022-2-14v圖的數(shù)組圖的數(shù)組( (鄰接矩陣鄰接矩陣) )存儲表示存儲表示#define INFINITY #define INFINITY INT_MAX; INT_MAX; / /

36、最大值最大值#define MAX_VERTEX_NUM #define MAX_VERTEX_NUM 20;20;/ / 最大頂點(diǎn)個(gè)數(shù)最大頂點(diǎn)個(gè)數(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是頂點(diǎn)關(guān)系類型。對無權(quán)圖，用是頂點(diǎn)關(guān)系類型。對無權(quán)圖，用

37、1 1或或0 0 / / 表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。InfoType 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; ; / / 頂點(diǎn)信息頂點(diǎn)信息

38、AdjMatrix AdjMatrix arcsarcs; ; / / 鄰接矩陣鄰接矩陣int int vexnum, arcnumvexnum, arcnum; ; / / 圖的當(dāng)前頂點(diǎn)數(shù)和弧圖的當(dāng)前頂點(diǎn)數(shù)和弧( (邊邊) )數(shù)數(shù)GraphKind GraphKind kindkind; ; / / 圖的種類標(biāo)志圖的種類標(biāo)志 MGraphMGraph; ;2022-2-14G1G1BDAC0 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.a

39、rcnum=4G1.kind=DGPage 482022-2-14V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何求頂點(diǎn)如何求頂點(diǎn) i 的出度？的出度？鄰接矩陣的第鄰接矩陣的第 i 行元素之和。行元素之和。Page 492022-2-14V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何求頂點(diǎn)如何求頂點(diǎn) i 的入度？的入度？鄰接矩陣的第鄰接矩陣的第 i 列元素之和

40、。列元素之和。2022-2-14V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何判斷從頂點(diǎn)如何判斷從頂點(diǎn) i 到頂點(diǎn)到頂點(diǎn) j 是否存在邊？是否存在邊？測試鄰接矩陣中相應(yīng)位置的元素測試鄰接矩陣中相應(yīng)位置的元素arcij是否為是否為1。2022-2-14AECBDG2G20 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.vex

41、s=A,B,C,D,EG2.vexnum=5G2.arcnum=6G2.kind=UDG2022-2-14如何求頂點(diǎn)如何求頂點(diǎn)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列）非零元素的個(gè)數(shù)。列）非零元素的個(gè)數(shù)。2022-2-14如何判斷頂點(diǎn)如何判斷頂點(diǎn) i 和和 j 之間是否存在邊？之間是否存在邊？V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=

42、V1 V2 V3 V4V1V2V3V4測試鄰接矩陣中相應(yīng)位置的元素測試鄰接矩陣中相應(yīng)位置的元素arcij是否為是否為1。Page 542022-2-14如何求頂點(diǎn)如何求頂點(diǎn) i 的所有鄰接點(diǎn)？的所有鄰接點(diǎn)？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，則，則頂點(diǎn)頂點(diǎn) j 為頂點(diǎn)為頂點(diǎn) i 的鄰接點(diǎn)。的鄰接點(diǎn)。網(wǎng)圖的鄰接矩陣定義：網(wǎng)圖的鄰接矩陣定義： arcij wij 若若(vi, vj)E（或（或E

43、） /0 若若i=j 其他其他V1V2V3V42785 2 5 8 7 arc=Page 562022-2-145 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-2-14v鄰接矩陣表示的特點(diǎn)鄰接矩陣表示的特點(diǎn)：無向圖無向圖的鄰接的鄰接矩陣對稱矩陣對稱，可，可壓縮存儲壓縮存儲；有；有n n個(gè)頂點(diǎn)的無向圖需個(gè)頂

44、點(diǎn)的無向圖需存儲空間為存儲空間為n(n+1)/2n(n+1)/2。有向圖有向圖鄰接鄰接矩陣不一定對稱矩陣不一定對稱；有；有n n個(gè)頂點(diǎn)的有向圖需存儲空間個(gè)頂點(diǎn)的有向圖需存儲空間為為n n。無向圖無向圖中頂點(diǎn)中頂點(diǎn)ViVi的度的度TD(Vi)TD(Vi)是鄰接矩陣是鄰接矩陣A A中第中第i i行元素之和行元素之和。有向圖有向圖中，中，頂點(diǎn)頂點(diǎn)ViVi的的出度是出度是A A中第中第i i行元素之和行元素之和。頂點(diǎn)頂點(diǎn)ViVi的的入度是入度是A A中第中第i i列元素之和列元素之和。v鄰接矩陣的優(yōu)缺點(diǎn)鄰接矩陣的優(yōu)缺點(diǎn)優(yōu)點(diǎn)優(yōu)點(diǎn)：容易判定頂點(diǎn)間有無邊（?。┖陀?jì)算頂點(diǎn)的度（出度、：容易判定頂點(diǎn)間有無邊（弧

45、）和計(jì)算頂點(diǎn)的度（出度、 入度）。入度）。缺點(diǎn)缺點(diǎn)：邊數(shù)較少時(shí)，空間浪費(fèi)較大。：邊數(shù)較少時(shí)，空間浪費(fèi)較大。2022-2-142 2、圖的鄰接表表示法、圖的鄰接表表示法q 引入原因引入原因v鄰接矩陣在稀疏圖時(shí)空間浪費(fèi)較大。鄰接矩陣在稀疏圖時(shí)空間浪費(fèi)較大。q 實(shí)現(xiàn)實(shí)現(xiàn)v為圖中為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表（邊表）每個(gè)頂點(diǎn)建立一個(gè)單鏈表（邊表），第，第i i個(gè)單鏈表中的結(jié)個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)點(diǎn)表示依附于頂點(diǎn)ViVi的邊（有向圖中指以的邊（有向圖中指以ViVi為尾的?。槲驳幕。每個(gè)鏈表附設(shè)一個(gè)表頭結(jié)點(diǎn)（頂點(diǎn)結(jié)點(diǎn)）每個(gè)鏈表附設(shè)一個(gè)表頭結(jié)點(diǎn)（頂點(diǎn)結(jié)點(diǎn)）。表結(jié)點(diǎn)表結(jié)點(diǎn)adjvexadjvex

46、nextarcnextarcinfoinfo與與ViVi鄰接的鄰接的點(diǎn)在表頭數(shù)點(diǎn)在表頭數(shù)組中的位置組中的位置頭結(jié)點(diǎn)頭結(jié)點(diǎn)datadatafirstarcfirstarcPage 592022-2-14#define MAX_VERTEX_NUM 20;#define MAX_VERTEX_NUM 20;typedef struct ArcNode typedef struct ArcNode int int adjvex; adjvex; / / 該弧所指向的頂點(diǎn)的位置該弧所指向的頂點(diǎn)的位置struct ArcNode struct ArcNode * *nextarc;nextarc; /

47、/ 指向下一條弧的指針指向下一條弧的指針I(yè)nfoType InfoType * *info;info; / / 該弧相關(guān)信息的指針該弧相關(guān)信息的指針 ArcNode; ArcNode; / / 邊表結(jié)點(diǎn)邊表結(jié)點(diǎn)typedef struct VNode typedef struct VNode VertexType VertexType data;data;/ / 頂點(diǎn)信息頂點(diǎn)信息ArcNode ArcNode * *firstarc;firstarc; / / 指向第一條依附該頂點(diǎn)的弧指向第一條依附該頂點(diǎn)的弧 AdjListMAX_VERTEX_NUMAdjListMAX_VERTEX_NUM

48、; ; /頂點(diǎn)表頂點(diǎn)表typedef struct typedef struct AdjList AdjList verticesvertices; ; / / 頂點(diǎn)數(shù)組頂點(diǎn)數(shù)組int vexnum, arcnum;int vexnum, arcnum; / / 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)int kind;int kind; / / 圖的種類標(biāo)志圖的種類標(biāo)志 ALGraphALGraph; ;Page 602022-2-1410323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2邊表中的結(jié)點(diǎn)表示什么？邊表中的結(jié)點(diǎn)表示什么？每個(gè)結(jié)點(diǎn)對應(yīng)圖中的

49、一條邊，每個(gè)結(jié)點(diǎn)對應(yīng)圖中的一條邊，鄰接表的空間復(fù)雜度為鄰接表的空間復(fù)雜度為O(n+2e)。2022-2-1410323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2如何求頂點(diǎn)如何求頂點(diǎn) i 的度？的度？頂點(diǎn)頂點(diǎn)i的邊表中結(jié)點(diǎn)的個(gè)數(shù)。的邊表中結(jié)點(diǎn)的個(gè)數(shù)。無向圖的鄰接表無向圖的鄰接表2022-2-14如何判斷頂點(diǎn)如何判斷頂點(diǎn) i 和頂點(diǎn)和頂點(diǎn) j之間是否存在邊之間是否存在邊?測試頂點(diǎn)測試頂點(diǎn) i 的邊表中是否存的邊表中是否存在終點(diǎn)為在終點(diǎn)為 j 的結(jié)點(diǎn)。的結(jié)點(diǎn)。10323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2P

50、age 63有向圖的鄰接表有向圖的鄰接表V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求頂點(diǎn)如何求頂點(diǎn) i 的出度？的出度？頂點(diǎn)頂點(diǎn) i 的出邊表中結(jié)點(diǎn)的個(gè)數(shù)。的出邊表中結(jié)點(diǎn)的個(gè)數(shù)。2022-2-14V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求頂點(diǎn)如何求頂點(diǎn) i 的入度？的入度？各頂點(diǎn)的出邊表中以頂點(diǎn)各頂點(diǎn)的出邊表中以頂點(diǎn) i 為為終點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)。終點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)。Page 652022-2-14V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求頂點(diǎn)如何求頂

51、點(diǎn) i 的所有鄰接點(diǎn)？的所有鄰接點(diǎn)？遍歷頂點(diǎn)遍歷頂點(diǎn) i 的邊表，該邊表中的的邊表，該邊表中的所有終點(diǎn)都是頂點(diǎn)所有終點(diǎn)都是頂點(diǎn) i 的鄰接點(diǎn)。的鄰接點(diǎn)。Page 662022-2-14網(wǎng)圖的鄰接表網(wǎng)圖的鄰接表V1V2V3V427852 1 V1 V2 V3 V40123vertex firstedge5 28 37 02022-2-14v優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)優(yōu)點(diǎn)優(yōu)點(diǎn)：空間較?。粺o向圖容易求各頂點(diǎn)的度；有向：空間較??；無向圖容易求各頂點(diǎn)的度；有向圖容易求頂點(diǎn)的出度；圖容易求頂點(diǎn)的出度；缺點(diǎn)缺點(diǎn)：求有向圖頂點(diǎn)的入度則不容易，要遍歷整個(gè)：求有向圖頂點(diǎn)的入度則不容易，要遍歷整個(gè)表。表。為了求頂點(diǎn)的入度，有時(shí)可

52、設(shè)逆鄰接表（指向某頂為了求頂點(diǎn)的入度，有時(shí)可設(shè)逆鄰接表（指向某頂點(diǎn)的鄰接點(diǎn)鏈接成單鏈表）。點(diǎn)的鄰接點(diǎn)鏈接成單鏈表）。bdac0123acdbdata firstarc3 0 02adjvex next逆鄰接表逆鄰接表2022-2-143 3 圖的十字鏈表表示法圖的十字鏈表表示法q 引入原因引入原因v對于同一個(gè)對于同一個(gè)有向圖需要同時(shí)用鄰接表和逆鄰接表有向圖需要同時(shí)用鄰接表和逆鄰接表時(shí)，不方便。時(shí)，不方便。q 實(shí)現(xiàn)實(shí)現(xiàn)v將在有向圖的將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個(gè)結(jié)鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個(gè)結(jié)點(diǎn)表示點(diǎn)表示，由于在鄰接表和逆鄰接表中的頂點(diǎn)，由于在鄰接表和逆鄰接

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

54、表和逆鄰接表中的頂點(diǎn)，由于在鄰接表和逆鄰接表中的頂點(diǎn)數(shù)據(jù)數(shù)據(jù)是相同的，則在是相同的，則在十字鏈表中十字鏈表中只需要出現(xiàn)一次只需要出現(xiàn)一次，但需，但需保留分別指向第一條保留分別指向第一條 出弧出弧 和和第一條第一條 入弧入弧 的指針的指針。G1G1bdac逆鄰接表逆鄰接表0123acdbdatafirstarc3 0 02adjvex next2022-2-14弧結(jié)點(diǎn)弧結(jié)點(diǎn)tailvextailvex headvexheadvexhlinkhlinktlinktlinkinfoinfo頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)datadatafirstinfirstinfirstoutfirstout弧尾弧尾位置位置弧頭

55、弧頭位置位置弧頭相同的下弧頭相同的下一條弧指針一條弧指針弧相關(guān)信息弧相關(guān)信息的指針的指針弧尾相同的下弧尾相同的下一條弧指針一條弧指針指向該頂點(diǎn)指向該頂點(diǎn)第一條入弧第一條入弧指向該頂點(diǎn)指向該頂點(diǎn)第一條出弧第一條出弧2022-2-14 0 2 0 1 2 3 2 0 3 2 3 1 3 0bdacab cd0123求結(jié)點(diǎn)的入度求結(jié)點(diǎn)的入度和出度的方法？和出度的方法？弧頭弧頭弧尾弧尾出邊出邊入邊入邊同尾同尾同頭同頭Page 722022-2-144 4 圖的鄰接多重表表示法圖的鄰接多重表表示法 q 引入原因引入原因v無向圖的鄰接表中無向圖的鄰接表中每一條邊有兩個(gè)結(jié)點(diǎn)，每一條邊有兩個(gè)結(jié)點(diǎn)，給對圖的邊進(jìn)

56、行訪問的給對圖的邊進(jìn)行訪問的操作帶來不便。有些時(shí)候需要同時(shí)找到表示同一條邊的兩個(gè)結(jié)點(diǎn)操作帶來不便。有些時(shí)候需要同時(shí)找到表示同一條邊的兩個(gè)結(jié)點(diǎn)（如刪除一條邊）。（如刪除一條邊）。aecbd0123acdbdatafirstarc 3 1 0 1adjvex next4e 3 2 4 0 42 12Page 73q 實(shí)現(xiàn)實(shí)現(xiàn)v每條邊用一個(gè)結(jié)點(diǎn)表示。每條邊用一個(gè)結(jié)點(diǎn)表示。邊結(jié)點(diǎn)邊結(jié)點(diǎn)markmarkivexivexilinkilinkjvexjvexjlinkjlinkinfoinfo頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)markmarkfirstedgefirstedge訪問訪問標(biāo)記標(biāo)記邊依附的邊依附的一個(gè)頂點(diǎn)一個(gè)頂點(diǎn)

57、邊依附的另邊依附的另一個(gè)頂點(diǎn)一個(gè)頂點(diǎn)依附這個(gè)頂依附這個(gè)頂點(diǎn)的下一條點(diǎn)的下一條邊指針邊指針依附這個(gè)頂依附這個(gè)頂點(diǎn)的下一條點(diǎn)的下一條邊指針邊指針訪問訪問標(biāo)記標(biāo)記指向第一條指向第一條 依附該頂點(diǎn)的依附該頂點(diǎn)的邊邊2022-2-14aecbd0123acdb4e 0 1 0 3 2 3 2 1 2 4 4 1q圖的概念與基本術(shù)語q圖的類型定義與存儲q圖的遍歷q圖的連通性與最小生成樹Page 752022-2-142022-2-14q 圖的遍歷圖的遍歷v從圖中某一頂點(diǎn)出發(fā)，訪問圖中其余頂點(diǎn)，使每個(gè)頂點(diǎn)被訪問一從圖中某一頂點(diǎn)出發(fā)，訪問圖中其余頂點(diǎn)，使每個(gè)頂點(diǎn)被訪問一次且只被訪問一次次且只被訪問一次。v可以

58、從圖中可以從圖中任意一個(gè)頂點(diǎn)出發(fā)任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷。進(jìn)行遍歷。v遍歷中需解決的問題遍歷中需解決的問題確定一搜索路徑確定一搜索路徑；確保確保每個(gè)頂點(diǎn)被訪問到每個(gè)頂點(diǎn)被訪問到；確保每個(gè)頂點(diǎn)確保每個(gè)頂點(diǎn)只能被訪問一次只能被訪問一次。v解決方法解決方法深度優(yōu)先和廣度優(yōu)先。深度優(yōu)先和廣度優(yōu)先。設(shè)設(shè)輔助數(shù)組輔助數(shù)組visitedvisited，初始時(shí)，數(shù)組元素的值均為，初始時(shí)，數(shù)組元素的值均為0 0或或falsefalse，表示未被遍歷，一旦遍歷，就置為表示未被遍歷，一旦遍歷，就置為1 1或或truetrue。Page 771 1 深度優(yōu)先搜索深度優(yōu)先搜索q 方法方法v從圖的某一頂點(diǎn)從圖的某一頂點(diǎn)V

59、0V0出發(fā)，訪問此頂點(diǎn)；出發(fā)，訪問此頂點(diǎn)；v然后依次從然后依次從V0V0的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和至圖中所有和V0V0相通的頂點(diǎn)都被訪問到；相通的頂點(diǎn)都被訪問到；v若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。訪問任意一個(gè)與訪問任意一個(gè)與V0V0鄰接的頂點(diǎn)鄰接的頂點(diǎn)W1W1，再從，再從W1W1出發(fā)；出發(fā)；訪問與訪問與W1W1鄰接且未被訪問過的任意頂點(diǎn)鄰接且未

60、被訪問過的任意頂點(diǎn)W2W2，再從，再從W2W2出發(fā)；出發(fā)；重復(fù)以上過程，直到一個(gè)所有鄰接點(diǎn)都被訪問過的頂點(diǎn)為止；重復(fù)以上過程，直到一個(gè)所有鄰接點(diǎn)都被訪問過的頂點(diǎn)為止；退回到尚有鄰接點(diǎn)未被訪問過的頂點(diǎn)，再從該頂點(diǎn)出發(fā)；退回到尚有鄰接點(diǎn)未被訪問過的頂點(diǎn)，再從該頂點(diǎn)出發(fā)；直到所有的被訪問過的頂點(diǎn)的鄰接點(diǎn)都已被訪問過為止。直到所有的被訪問過的頂點(diǎn)的鄰接點(diǎn)都已被訪問過為止。Page 782022-2-14深一層遞歸深一層遞歸遞歸返回遞歸返回深度優(yōu)先遍歷序列深度優(yōu)先遍歷序列?入棧序列入棧序列?出棧序列出棧序列?V1V3V2V4V5V6V7V8 V1遍歷序列：遍歷序列：V1V2 V2V4 V4V5 V5Page 792022-2-14深一層遞歸深一層遞歸遞歸返回遞歸返回深度優(yōu)先遍歷序列深度優(yōu)先遍歷序列?入棧