數(shù)據(jù)結構課件-圖

1、Page 12021-12-15p 畫出下列二叉鏈表代表的二叉樹（畫出下列二叉鏈表代表的二叉樹（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 22021-12-15第第8-1講講 圖的基礎知識圖的基礎

3、知識清華大學清華大學 自動化系自動化系 黃雙喜黃雙喜 博士、副教授博士、副教授Page 32021-12-15q學習目標學習目標v領會領會圖的基本概念圖的基本概念。v熟悉熟悉圖的各種存儲結構圖的各種存儲結構及其構造算法，了解各種存儲及其構造算法，了解各種存儲結構的特點及其結構的特點及其選用原則選用原則。v熟練掌握圖的兩種熟練掌握圖的兩種遍歷遍歷算法及應用。算法及應用。v理解各種圖的理解各種圖的應用問題的算法應用問題的算法。q重點和難點重點和難點v重點：圖的各種應用問題的算法都比較經典，注意重點：圖的各種應用問題的算法都比較經典，注意理理解各種圖的算法及其應用場合解各種圖的算法及其應用場合。Pa

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、點、個頂點、e條邊的無向圖條邊的無向圖G中，各頂點中，各頂點的度之和與邊數(shù)之和的關系？的度之和與邊數(shù)之和的關系？ = = =niievTD12)(V1V2V3V4在具有在具有n個頂點、個頂點、e條邊的有向圖條邊的有向圖G中，各頂點中，各頂點的入度之和與各頂點的出度之和的關系？與邊的入度之和與各頂點的出度之和的關系？與邊數(shù)之和的關系？數(shù)之和的關系？evODvIDiiii= = = = = =11)()(nn2021-12-15權：權：是指對邊賦予的有意義的數(shù)值量。是指對邊賦予的有意義的數(shù)值量。網(wǎng)：網(wǎng)：邊上帶權的圖，也稱網(wǎng)圖。邊上帶權的圖，也稱網(wǎng)圖。V1V2V3V42785圖結構中的權和哈夫曼樹中

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

20、V2 V3 V4 V1 V2 V5V3 V42021-12-15路徑長度：路徑長度：非帶權圖非帶權圖路徑路徑上邊的上邊的個數(shù)個數(shù)帶權圖帶權圖路徑上路徑上各邊的各邊的權之和權之和V1V2V3V4V5V1 V4：長度為：長度為1V1 V2 V3 V4 ：長度為：長度為3V1 V2 V5V3 V4 ：長度為：長度為42021-12-15路徑長度：路徑長度：非帶權圖非帶權圖路徑路徑上邊的上邊的個數(shù)個數(shù)帶權圖帶權圖路徑上路徑上各邊的各邊的權之和權之和V1 V4：長度為：長度為8V1 V2 V3 V4 ：長度為：長度為7V1 V2 V5V3 V4 ：長度為：長度為15V1V2V3V4V5256328202

21、1-12-15回路（環(huán)）回路（環(huán)）：第一個頂點和最后一個頂點相同的路徑。：第一個頂點和最后一個頂點相同的路徑。簡單路徑：簡單路徑：序列中頂點不重復出現(xiàn)的路徑。序列中頂點不重復出現(xiàn)的路徑。簡單回路（簡單環(huán)）：簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點外，除了第一個頂點和最后一個頂點外，其余頂點不重復出現(xiàn)的回路。其余頂點不重復出現(xiàn)的回路。V1V2V3V4V5V1V2V3V42021-12-15子圖：子圖：若圖若圖G=（V，E），），G=（V，E），如果），如果V V 且且E E ，則稱圖，則稱圖G是是G的子圖。的子圖。V1V2V3V4V5V1V2V3V4V5V1V3V42021-12-15連

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

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

24、分量強連通分量2V1V3V4V22021-12-15生成樹：生成樹：n個頂點的連通圖個頂點的連通圖G的生成樹是包含的生成樹是包含G中中全全部頂點部頂點的一個極小連通的一個極小連通子圖。子圖。 生成森林：生成森林：在非連通圖中，由每個連通分量都可以得在非連通圖中，由每個連通分量都可以得到一棵生成樹，這些連通分到一棵生成樹，這些連通分量的生成樹就組成了一個量的生成樹就組成了一個非連通圖的非連通圖的生成森林生成森林。 如何理解極小連通子圖如何理解極小連通子圖?多多構成回路構成回路少少不連通不連通含有含有n-1條邊條邊2021-12-15V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2

25、V3V4V5V1V2V3V4V5生成樹生成樹生成森林生成森林q圖的概念與基本術語q圖的類型定義與存儲q圖的遍歷q圖的連通性與最小生成樹Page 362021-12-152021-12-15圖的抽象數(shù)據(jù)類型定義如下：圖的抽象數(shù)據(jù)類型定義如下：ADT ADT GraphGraph 數(shù)據(jù)對象數(shù)據(jù)對象V V ：V V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂是具有相同特性的數(shù)據(jù)元素的集合，稱為頂 點集。點集。數(shù)據(jù)關系數(shù)據(jù)關系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)定義了弧定義了弧的意義

26、的意義 或信息或信息 Page 382021-12-15G1=(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 392021-12-15CreateGraph(&G, V, V

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

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

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

30、ue);初始條件：圖初始條件：圖 G G 存在，存在，v v 是是 G G 中某個頂點。中某個頂點。操作結果：操作結果：對對 v v 賦值賦值 valuevalue。InsertVex(&G, v);InsertVex(&G, v);初始條件：圖初始條件：圖 G G 存在，存在，v v 和圖中頂點有相同特征。和圖中頂點有相同特征。操作結果：在圖操作結果：在圖 G G 中中增添新頂點增添新頂點 v v。DeleteVex(&G, v);DeleteVex(&G, v);初始條件：圖初始條件：圖 G G 存在，存在，v v 是是 G G 中某個頂點。中某個頂點。操作

31、結果：操作結果：刪除刪除 G G 中頂點中頂點 v v 及其相關的弧及其相關的弧。2021-12-15InsertArc(&G, v, w);InsertArc(&G, v, w);初始條件：圖初始條件：圖 G G 存在，存在，v v 和和 w w 是是 G G 中兩個頂點。中兩個頂點。操作結果：在操作結果：在 G G 中中增添弧增添弧，若，若 G G 是是無向的，則還無向的，則還 增添對稱弧增添對稱弧。DeleteArc(&G, v, w);DeleteArc(&G, v, w);初始條件：圖初始條件：圖 G G 存在，存在，v v 和和 w w 是是 G G

32、 中兩個頂點。中兩個頂點。操作結果：在操作結果：在 G G 中中刪除弧刪除弧，若若 G G 是是無向的，則還無向的，則還 刪除對稱弧刪除對稱弧。Page 432021-12-15DFSTraverse(G, Visit();DFSTraverse(G, Visit();初始條件：圖初始條件：圖 G G 存在，存在，Visit Visit 是頂點的應用函數(shù)。是頂點的應用函數(shù)。操作結果：對圖操作結果：對圖 G G 進行進行深度優(yōu)先深度優(yōu)先遍歷。遍歷過程中對每遍歷。遍歷過程中對每 個頂點調用函數(shù)個頂點調用函數(shù)Visit Visit 一次且僅一次。一旦一次且僅一次。一旦 visit() visit()

33、 失敗，則操作失敗。失敗，則操作失敗。BFSTraverse(G, Visit();BFSTraverse(G, Visit();初始條件：圖初始條件：圖 G G 存在，存在，Visit Visit 是頂點的應用函數(shù)。是頂點的應用函數(shù)。操作結果：對圖操作結果：對圖 G G 進行進行廣度優(yōu)先廣度優(yōu)先遍歷。遍歷過程中對每遍歷。遍歷過程中對每 個頂點調用函數(shù)個頂點調用函數(shù)Visit Visit 一次且僅一次。一旦一次且僅一次。一旦 visit() visit() 失敗，則操作失敗。失敗，則操作失敗。 ADT Graph ADT Graph2021-12-15是否可以采用頂點的順序存儲結構存儲圖是否可

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

35、中，并將它的，并將它的鄰接矩陣存儲在一個二維數(shù)組中鄰接矩陣存儲在一個二維數(shù)組中即構成圖的數(shù)組表即構成圖的數(shù)組表示。示。v假設圖中頂點數(shù)為假設圖中頂點數(shù)為n n，則鄰接矩陣，則鄰接矩陣A A定義為定義為=，其它0E(G)v,v或)v,(v若1,jijijiA網(wǎng)的鄰接矩陣的定義為，當網(wǎng)的鄰接矩陣的定義為，當v vi i到到v vj j有弧相鄰接時，有弧相鄰接時，a aijij的值應為該弧上的權值，否則為的值應為該弧上的權值，否則為。1 1、圖的鄰接矩陣表示法、圖的鄰接矩陣表示法2021-12-15v圖的數(shù)組圖的數(shù)組( (鄰接矩陣鄰接矩陣) )存儲表示存儲表示#define INFINITY #de

36、fine INFINITY INT_MAX; INT_MAX; / / 最大值最大值#define MAX_VERTEX_NUM #define MAX_VERTEX_NUM 20;20;/ / 最大頂點個數(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

37、/ VRType是頂點關系類型。對無權圖，用是頂點關系類型。對無權圖，用1 1或或0 0 / / 表示相鄰否；對帶權圖，則為權值類型。表示相鄰否；對帶權圖，則為權值類型。InfoType InfoType * *info; info; / / 該弧的相關信息該弧的相關信息 ArcCell, ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUMAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; ;typedef struct typedef struct VertexType VertexType vexsMAX_VERTEX_N

38、UMvexsMAX_VERTEX_NUM; ; / / 頂點信息頂點信息AdjMatrix AdjMatrix arcsarcs; ; / / 鄰接矩陣鄰接矩陣int int vexnum, arcnumvexnum, arcnum; ; / / 圖的當前頂點數(shù)和弧圖的當前頂點數(shù)和弧( (邊邊) )數(shù)數(shù)GraphKind GraphKind kindkind; ; / / 圖的種類標志圖的種類標志 MGraphMGraph; ;2021-12-15G1G1BDAC0 01 11 10 00 00 00 00 0G G1 1. .a ar rc cs s = =0 00 00 01 11 10

39、00 00 0G1.vexs=A,B,C,DG1.vexnum=4G1.arcnum=4G1.kind=DGPage 482021-12-15V1V2V3V4V1 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 行元素之和。行元素之和。Page 492021-12-15V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何

40、求頂點如何求頂點 i 的入度？的入度？鄰接矩陣的第鄰接矩陣的第 i 列元素之和。列元素之和。2021-12-15V1V2V3V4V1 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 到頂點到頂點 j 是否存在邊？是否存在邊？測試鄰接矩陣中相應位置的元素測試鄰接矩陣中相應位置的元素arcij是否為是否為1。2021-12-15AECBDG2G20 01 10 01 10 01 10 01 10 01 1G G2 2. .a ar rc cs s = =0 01 10 01

41、 11 11 10 01 10 00 00 01 11 10 00 0G2.vexs=A,B,C,D,EG2.vexnum=5G2.arcnum=6G2.kind=UDG2021-12-15如何求頂點如何求頂點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ù)。2021-12-15如何判斷頂點如何判斷頂點 i 和和 j 之間是否存在邊？之間是否存在邊？V1V3V4V2V1 V2 V3 V4

42、vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4測試鄰接矩陣中相應位置的元素測試鄰接矩陣中相應位置的元素arcij是否為是否為1。Page 542021-12-15如何求頂點如何求頂點 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)圖的

43、鄰接矩陣定義：網(wǎng)圖的鄰接矩陣定義： arcij wij 若若(vi, vj)E（或（或E） /0 若若i=j 其他其他V1V2V3V42785 2 5 8 7 arc=Page 562021-12-155 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=UDN2021-12-15v鄰接矩陣表示的特點鄰接矩陣表示的特點：無向圖

44、無向圖的鄰接的鄰接矩陣對稱矩陣對稱，可，可壓縮存儲壓縮存儲；有；有n n個頂點的無向圖需個頂點的無向圖需存儲空間為存儲空間為n(n+1)/2n(n+1)/2。有向圖有向圖鄰接鄰接矩陣不一定對稱矩陣不一定對稱；有；有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)缺點鄰接矩陣

45、的優(yōu)缺點優(yōu)點優(yōu)點：容易判定頂點間有無邊（?。┖陀嬎沩旤c的度（出度、：容易判定頂點間有無邊（?。┖陀嬎沩旤c的度（出度、 入度）。入度）。缺點缺點：邊數(shù)較少時，空間浪費較大。：邊數(shù)較少時，空間浪費較大。2021-12-152 2、圖的鄰接表表示法、圖的鄰接表表示法q 引入原因引入原因v鄰接矩陣在稀疏圖時空間浪費較大。鄰接矩陣在稀疏圖時空間浪費較大。q 實現(xiàn)實現(xiàn)v為圖中為圖中每個頂點建立一個單鏈表（邊表）每個頂點建立一個單鏈表（邊表），第，第i i個單鏈表中的結個單鏈表中的結點表示依附于頂點點表示依附于頂點ViVi的邊（有向圖中指以的邊（有向圖中指以ViVi為尾的?。槲驳幕。?。v每個鏈表附設一個

46、表頭結點（頂點結點）每個鏈表附設一個表頭結點（頂點結點）。表結點表結點adjvexadjvexnextarcnextarcinfoinfo與與ViVi鄰接的鄰接的點在表頭數(shù)點在表頭數(shù)組中的位置組中的位置頭結點頭結點datadatafirstarcfirstarcPage 592021-12-15#define MAX_VERTEX_NUM 20;#define MAX_VERTEX_NUM 20;typedef struct ArcNode typedef struct ArcNode int int adjvex; adjvex; / / 該弧所指向的頂點的位置該弧所指向的頂點的位置stru

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

48、該頂點的弧 AdjListMAX_VERTEX_NUMAdjListMAX_VERTEX_NUM; ; /頂點表頂點表typedef struct typedef struct AdjList AdjList verticesvertices; ; / / 頂點數(shù)組頂點數(shù)組int vexnum, arcnum;int vexnum, arcnum; / / 圖的當前頂點數(shù)和弧數(shù)圖的當前頂點數(shù)和弧數(shù)int kind;int kind; / / 圖的種類標志圖的種類標志 ALGraphALGraph; ;Page 602021-12-1510323101 V1 V2 V3 V40123vertex

49、 firstedgeV1V3V4V2邊表中的結點表示什么？邊表中的結點表示什么？每個結點對應圖中的一條邊，每個結點對應圖中的一條邊，鄰接表的空間復雜度為鄰接表的空間復雜度為O(n+2e)。2021-12-1510323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2如何求頂點如何求頂點 i 的度？的度？頂點頂點i的邊表中結點的個數(shù)。的邊表中結點的個數(shù)。無向圖的鄰接表無向圖的鄰接表2021-12-15如何判斷頂點如何判斷頂點 i 和頂點和頂點 j之間是否存在邊之間是否存在邊?測試頂點測試頂點 i 的邊表中是否存的邊表中是否存在終點為在終點為 j 的結點。的結

50、點。10323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2Page 63有向圖的鄰接表有向圖的鄰接表V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求頂點如何求頂點 i 的出度？的出度？頂點頂點 i 的出邊表中結點的個數(shù)。的出邊表中結點的個數(shù)。2021-12-15V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求頂點如何求頂點 i 的入度？的入度？各頂點的出邊表中以頂點各頂點的出邊表中以頂點 i 為為終點的結點個數(shù)。終點的結點個數(shù)。Page 652021-12-15

51、V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求頂點如何求頂點 i 的所有鄰接點？的所有鄰接點？遍歷頂點遍歷頂點 i 的邊表，該邊表中的的邊表，該邊表中的所有終點都是頂點所有終點都是頂點 i 的鄰接點。的鄰接點。Page 662021-12-15網(wǎng)圖的鄰接表網(wǎng)圖的鄰接表V1V2V3V427852 1 V1 V2 V3 V40123vertex firstedge5 28 37 02021-12-15v優(yōu)缺點優(yōu)缺點優(yōu)點優(yōu)點：空間較??；無向圖容易求各頂點的度；有向：空間較??；無向圖容易求各頂點的度；有向圖容易求頂點的出度；圖容易求頂點的出度；缺點缺點：

52、求有向圖頂點的入度則不容易，要遍歷整個：求有向圖頂點的入度則不容易，要遍歷整個表。表。為了求頂點的入度，有時可設逆鄰接表（指向某頂為了求頂點的入度，有時可設逆鄰接表（指向某頂點的鄰接點鏈接成單鏈表）。點的鄰接點鏈接成單鏈表）。bdac0123acdbdata firstarc3 0 02adjvex next逆鄰接表逆鄰接表2021-12-153 3 圖的十字鏈表表示法圖的十字鏈表表示法q 引入原因引入原因v對于同一個對于同一個有向圖需要同時用鄰接表和逆鄰接表有向圖需要同時用鄰接表和逆鄰接表時，不方便。時，不方便。q 實現(xiàn)實現(xiàn)v將在有向圖的將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個

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

54、的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結點表示點表示，由于在鄰接表和逆鄰接表中的頂點，由于在鄰接表和逆鄰接表中的頂點數(shù)據(jù)數(shù)據(jù)是相同的，則在是相同的，則在十字鏈表中十字鏈表中只需要出現(xiàn)一次只需要出現(xiàn)一次，但需，但需保留分別指向第一條保留分別指向第一條 出弧出弧 和和第一條第一條 入弧入弧 的指針的指針。G1G1bdac逆鄰接表逆鄰接表0123acdbdatafirstarc3 0 02adjvex next2021-12-15弧結點弧結點tailvextailvex headvexheadvexhlinkhlinktlinktlinkinfoin

55、fo頂點結點頂點結點datadatafirstinfirstinfirstoutfirstout弧尾弧尾位置位置弧頭弧頭位置位置弧頭相同的下弧頭相同的下一條弧指針一條弧指針弧相關信息弧相關信息的指針的指針弧尾相同的下弧尾相同的下一條弧指針一條弧指針指向該頂點指向該頂點第一條入弧第一條入弧指向該頂點指向該頂點第一條出弧第一條出弧2021-12-15 0 2 0 1 2 3 2 0 3 2 3 1 3 0bdacab cd0123求結點的入度求結點的入度和出度的方法？和出度的方法？弧頭弧頭弧尾弧尾出邊出邊入邊入邊同尾同尾同頭同頭Page 722021-12-154 4 圖的鄰接多重表表示法圖的鄰接

56、多重表表示法 q 引入原因引入原因v無向圖的鄰接表中無向圖的鄰接表中每一條邊有兩個結點，每一條邊有兩個結點，給對圖的邊進行訪問的給對圖的邊進行訪問的操作帶來不便。有些時候需要同時找到表示同一條邊的兩個結點操作帶來不便。有些時候需要同時找到表示同一條邊的兩個結點（如刪除一條邊）。（如刪除一條邊）。aecbd0123acdbdatafirstarc 3 1 0 1adjvex next4e 3 2 4 0 42 12Page 73q 實現(xiàn)實現(xiàn)v每條邊用一個結點表示。每條邊用一個結點表示。邊結點邊結點markmarkivexivexilinkilinkjvexjvexjlinkjlinkinfoin

57、fo頂點結點頂點結點markmarkfirstedgefirstedge訪問訪問標記標記邊依附的邊依附的一個頂點一個頂點邊依附的另邊依附的另一個頂點一個頂點依附這個頂依附這個頂點的下一條點的下一條邊指針邊指針依附這個頂依附這個頂點的下一條點的下一條邊指針邊指針訪問訪問標記標記指向第一條指向第一條 依附該頂點的依附該頂點的邊邊2021-12-15aecbd0123acdb4e 0 1 0 3 2 3 2 1 2 4 4 1q圖的概念與基本術語q圖的類型定義與存儲q圖的遍歷q圖的連通性與最小生成樹Page 752021-12-152021-12-15q 圖的遍歷圖的遍歷v從圖中某一頂點出發(fā)，訪問圖

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

59、，就置為1 1或或truetrue。Page 771 1 深度優(yōu)先搜索深度優(yōu)先搜索q 方法方法v從圖的某一頂點從圖的某一頂點V0V0出發(fā)，訪問此頂點；出發(fā)，訪問此頂點；v然后依次從然后依次從V0V0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和至圖中所有和V0V0相通的頂點都被訪問到；相通的頂點都被訪問到；v若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止。點作起點，重復上述過程，直至圖中所有頂點都被訪問為止。訪問任意一個與訪問任意一

60、個與V0V0鄰接的頂點鄰接的頂點W1W1，再從，再從W1W1出發(fā)；出發(fā)；訪問與訪問與W1W1鄰接且未被訪問過的任意頂點鄰接且未被訪問過的任意頂點W2W2，再從，再從W2W2出發(fā)；出發(fā)；重復以上過程，直到一個所有鄰接點都被訪問過的頂點為止；重復以上過程，直到一個所有鄰接點都被訪問過的頂點為止；退回到尚有鄰接點未被訪問過的頂點，再從該頂點出發(fā)；退回到尚有鄰接點未被訪問過的頂點，再從該頂點出發(fā)；直到所有的被訪問過的頂點的鄰接點都已被訪問過為止。直到所有的被訪問過的頂點的鄰接點都已被訪問過為止。Page 782021-12-15深一層遞歸深一層遞歸遞歸返回遞歸返回深度優(yōu)先遍歷序列深度優(yōu)先遍歷序列?入棧序列入棧序列?出棧序列出棧序列?V1V3V2V4V5V6V7V8 V1遍歷序列：遍歷序列：V1V2 V