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

1、Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 12021-12-1810086510Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 22021-12-18q 學習目標學習目標v領(lǐng)會領(lǐng)會圖的類型定義圖的類型定義。v熟悉熟悉圖的各種存儲結(jié)構(gòu)圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲結(jié)構(gòu)的特點及其構(gòu)造算法，了解各種存儲結(jié)構(gòu)的特點及其及其選用原則選用原則。v熟練掌握圖的兩種熟練掌握圖的兩種遍歷遍歷算法。算法。v理解各種圖的理解各種圖的應用問題的算法應用問題的算法。q 重點和難點重點和難點v重點：圖的各種應用問題的算法都比較經(jīng)典，注意

2、重點：圖的各種應用問題的算法都比較經(jīng)典，注意理解各種圖的理解各種圖的算法及其應用場合算法及其應用場合。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 32021-12-18q 知識點知識點v圖的類型定義圖的類型定義v圖的存儲表示圖的存儲表示v圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷v無向網(wǎng)的最小生成樹無向網(wǎng)的最小生成樹v拓撲排序拓撲排序v關(guān)鍵路徑關(guān)鍵路徑v最短路徑最短路徑Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 42021-12-18歐拉歐拉17071707年出生在瑞士的巴塞爾城，年出

3、生在瑞士的巴塞爾城，1919歲開始發(fā)歲開始發(fā)表論文，直到表論文，直到7676歲。幾乎每一個數(shù)學領(lǐng)域都可以歲。幾乎每一個數(shù)學領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級數(shù)論的歐拉常數(shù)，變分學的歐程的歐拉方程，級數(shù)論的歐拉常數(shù)，變分學的歐拉方程，復變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計他那拉方程，復變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計他那不倦的一生，共寫下了不倦的一生，共寫下了8868

4、86本書籍和論文，其中本書籍和論文，其中分析、代數(shù)、數(shù)論占分析、代數(shù)、數(shù)論占40%40%，幾何占，幾何占18%18%，物理和，物理和力學占力學占28%28%，天文學占，天文學占11%11%，彈道學、航海學、，彈道學、航海學、建筑學等占建筑學等占3%3%。 17331733年，年僅年，年僅2626歲的歐拉擔任歲的歐拉擔任了彼得堡科學院數(shù)學教授。了彼得堡科學院數(shù)學教授。17411741年到柏林擔任科年到柏林擔任科學院物理數(shù)學所所長，直到學院物理數(shù)學所所長，直到17661766年，重回彼得堡，年，重回彼得堡，沒有多久，完全失明。歐拉在數(shù)學上的建樹很多，沒有多久，完全失明。歐拉在數(shù)學上的建樹很多，對著

5、名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。研究。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 52021-12-18能否從某個地方出發(fā)，穿過所有的橋僅一次能否從某個地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點？后再回到出發(fā)點？Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 62021-12-18CADB七橋問題的圖模型七橋問題的圖模型歐拉回路的判定規(guī)則：歐拉回路的判定規(guī)則：1.如果通奇數(shù)橋的地方多于如果通奇數(shù)橋的地方多于兩個，則不存在歐拉回路；兩個，則不存在歐拉回路；2.如果只有兩個

6、地方通奇數(shù)如果只有兩個地方通奇數(shù)橋，可以從這兩個地方之一橋，可以從這兩個地方之一出發(fā)，找到歐拉回路；出發(fā)，找到歐拉回路；3.如果沒有一個地方是通奇如果沒有一個地方是通奇數(shù)橋的，則無論從哪里出發(fā)，數(shù)橋的，則無論從哪里出發(fā)，都能找到歐拉回路。都能找到歐拉回路。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 72021-12-18圖的定義圖的定義圖是由圖是由頂點頂點的的有窮非空有窮非空集合和頂點之間集合和頂點之間邊邊的集合組的集合組成，通常表示為：成，通常表示為： G=(V，E)其中：其中：G表示一個圖，表示一個圖，V是圖是圖G中頂點的集合，中頂點的集合，E是是圖圖

7、G中頂點之間邊的集合。中頂點之間邊的集合。 在線性表中，元素個數(shù)可以為零，稱為空表；在線性表中，元素個數(shù)可以為零，稱為空表；在樹中，結(jié)點個數(shù)可以為零，稱為空樹；在樹中，結(jié)點個數(shù)可以為零，稱為空樹；在圖中，頂點個數(shù)不能為零，但可以沒有邊。在圖中，頂點個數(shù)不能為零，但可以沒有邊。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 82021-12-18q線性表線性表v每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。q樹形結(jié)構(gòu)樹形結(jié)構(gòu)v每個數(shù)據(jù)元素只有一個直接前驅(qū)，但可能有多個直接后繼。每個數(shù)據(jù)元素只有一個直接前驅(qū)，但可能有多個直

8、接后繼。q圖形結(jié)構(gòu)圖形結(jié)構(gòu)v每個數(shù)據(jù)元素可能有多個直接前驅(qū)和多個直接后繼。每個數(shù)據(jù)元素可能有多個直接前驅(qū)和多個直接后繼。 圖是比線性表和樹復雜的數(shù)據(jù)結(jié)構(gòu)，廣泛應用于語圖是比線性表和樹復雜的數(shù)據(jù)結(jié)構(gòu)，廣泛應用于語言學、邏輯學、物理、化學等領(lǐng)域。言學、邏輯學、物理、化學等領(lǐng)域。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 92021-12-18如果圖的任意兩個頂點之間的邊都如果圖的任意兩個頂點之間的邊都是是無向邊，則稱該圖為無向邊，則稱該圖為無向圖無向圖。若頂點若頂點vi和和vj之間的邊沒有方向，則之間的邊沒有方向，則稱這條邊為稱這條邊為無向邊無向邊，表示為，表

9、示為(vi, ,vj)。若從頂點若從頂點vi到到vj的邊有方向，則稱這的邊有方向，則稱這條邊為條邊為有向邊有向邊，表示為，表示為。 如果圖的任意兩個頂點之間的邊都如果圖的任意兩個頂點之間的邊都是是有向邊，則稱該圖為有向邊，則稱該圖為有向圖有向圖。V1V2V3V4V5V1V2V3V4圖的基本術(shù)語圖的基本術(shù)語 Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 102021-12-18簡單圖：簡單圖：在圖中，若不存在頂點到其自身的邊，且同在圖中，若不存在頂點到其自身的邊，且同一條邊不重復出現(xiàn)一條邊不重復出現(xiàn)。V3V4V5V1V2V3V4V5V1V2非簡單圖非簡單圖 非

10、簡單圖非簡單圖 簡單圖簡單圖V1V2V3V4V5v 數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖。數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 112021-12-18圖的基本術(shù)語圖的基本術(shù)語 鄰接、依附鄰接、依附無向圖無向圖中，對于任意兩個頂點中，對于任意兩個頂點vi和頂點和頂點vj，若存在邊，若存在邊(vi，vj)，則稱頂點，則稱頂點vi和頂點和頂點vj互為鄰接點，同時稱邊互為鄰接點，同時稱邊(vi，vj)依附于頂點依附于頂點vi和頂點和頂點vj。V1V2V3V4V5V1的鄰接點：的鄰接點： V2 、V4V2的鄰接點：的鄰接點： V1 、V3

11、、V5Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 122021-12-18圖的基本術(shù)語圖的基本術(shù)語 鄰接、依附鄰接、依附有向圖有向圖中，對于任意兩個頂點中，對于任意兩個頂點vi和頂點和頂點vj，若存在弧，若存在弧，則稱頂點，則稱頂點vi鄰接到頂點鄰接到頂點vj，頂點，頂點vj鄰接自頂鄰接自頂點點vi，同時稱弧同時稱弧依附于頂點依附于頂點vi和頂點和頂點vj 。 V1V2V3V4V1的鄰接點：的鄰接點： V2 、V3V3的鄰接點：的鄰接點： V4Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 132021-12-18無向完全

12、圖無向完全圖：在無向圖中，如果任意兩個頂點之間：在無向圖中，如果任意兩個頂點之間都存在邊，都存在邊，則稱該圖為無向完全圖。則稱該圖為無向完全圖。有向完全圖有向完全圖：在有向圖中，如果任意兩個頂點之間：在有向圖中，如果任意兩個頂點之間都存在方向相反的兩條弧，都存在方向相反的兩條弧，則稱該圖為有向完全圖則稱該圖為有向完全圖。 圖的基本術(shù)語圖的基本術(shù)語 V1V2V3V1V2V3V4Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 142021-12-18含有含有n個頂點的無向完全圖有個頂點的無向完全圖有多少多少條邊？條邊？含有含有n個頂點的有向完全圖有個頂點的有向完全

13、圖有多少多少條?。織l??？ 含有含有n個頂點的無向完全圖有個頂點的無向完全圖有n(n-1)/2條邊。條邊。 含有含有n個頂點的有向完全圖有個頂點的有向完全圖有n(n-1)條邊。條邊。 V1V2V3V1V2V3V4Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 152021-12-18稀疏圖：稀疏圖：稱邊數(shù)很少的圖為稀疏圖；稱邊數(shù)很少的圖為稀疏圖；稠密圖：稠密圖：稱邊數(shù)很多的圖為稠密圖。稱邊數(shù)很多的圖為稠密圖。頂點的度：頂點的度：在無向圖中，頂點在無向圖中，頂點v的的度度是指依附于該頂是指依附于該頂點的邊數(shù)，通常記為點的邊數(shù)，通常記為TD (v)。圖的基本術(shù)語圖的

14、基本術(shù)語 頂點的入度：頂點的入度：在有向圖中，頂點在有向圖中，頂點v的的入度入度是指以該頂是指以該頂點為弧頭的弧的數(shù)目，點為弧頭的弧的數(shù)目，記為記為ID (v)；頂點頂點的的出度：出度：在有向圖中，頂點在有向圖中，頂點v的的出度出度是指以該頂是指以該頂點為弧尾的弧的數(shù)目，記為點為弧尾的弧的數(shù)目，記為OD (v)。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 162021-12-18V1V2V3V4V5圖的基本術(shù)語圖的基本術(shù)語 在具有在具有n個頂點、個頂點、e條邊的無向圖條邊的無向圖G中，各頂點中，各頂點的度之和與邊數(shù)之和的關(guān)系？的度之和與邊數(shù)之和的關(guān)系？ =

15、 = =niievTD12)(Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 172021-12-18V1V2V3V4圖的基本術(shù)語圖的基本術(shù)語 在具有在具有n個頂點、個頂點、e條邊的有向圖條邊的有向圖G中，各頂點中，各頂點的入度之和與各頂點的出度之和的關(guān)系？與邊的入度之和與各頂點的出度之和的關(guān)系？與邊數(shù)之和的關(guān)系？數(shù)之和的關(guān)系？evODvIDiiii= = = = = =11)()(nnData StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 182021-12-18權(quán)：權(quán)：是指對邊賦予的有意義的數(shù)值量。是指對邊賦予的有意義的數(shù)值量。網(wǎng)

16、：網(wǎng)：邊上帶權(quán)的圖，也稱網(wǎng)圖。邊上帶權(quán)的圖，也稱網(wǎng)圖。圖的基本術(shù)語圖的基本術(shù)語 V1V2V3V42785Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 192021-12-18路徑：路徑：在無向圖在無向圖G=(V, E)中，從頂點中，從頂點vp到頂點到頂點vq之間的之間的路徑路徑是一個頂點序列是一個頂點序列(vp=vi0,vi1,vi2, , vim=vq)，其中，其中，(vij-1,vij)E（1jm）。若）。若G是有向圖，則路徑也是有是有向圖，則路徑也是有方向的，頂點序列滿足方向的，頂點序列滿足E。圖的基本術(shù)語圖的基本術(shù)語 V1V2V3V4V5v一般情況下

17、，圖中的路徑不惟一。一般情況下，圖中的路徑不惟一。V1 到到V4的路徑：的路徑： V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 202021-12-18路徑長度：路徑長度：圖的基本術(shù)語圖的基本術(shù)語 非帶權(quán)圖非帶權(quán)圖路徑路徑上邊的上邊的個數(shù)個數(shù)帶權(quán)圖帶權(quán)圖路徑上路徑上各邊的各邊的權(quán)之和權(quán)之和V1V2V3V4V5V1 V4：長度為：長度為1V1 V2 V3 V4 ：長度為：長度為3V1 V2 V5V3 V4 ：長度為：長度為4Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Pa

18、ge 212021-12-18路徑長度：路徑長度：圖的基本術(shù)語圖的基本術(shù)語 非帶權(quán)圖非帶權(quán)圖路徑路徑上邊的上邊的個數(shù)個數(shù)帶權(quán)圖帶權(quán)圖路徑上路徑上各邊的各邊的權(quán)之和權(quán)之和V1 V4：長度為：長度為8V1 V2 V3 V4 ：長度為：長度為7V1 V2 V5V3 V4 ：長度為：長度為15V1V2V3V4V5256328Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 222021-12-18回路（環(huán)）回路（環(huán)）：第一個頂點和最后一個頂點相同的路徑。：第一個頂點和最后一個頂點相同的路徑。簡單路徑：簡單路徑：序列中頂點不重復出現(xiàn)的路徑。序列中頂點不重復出現(xiàn)的路徑。簡單

19、回路（簡單環(huán)）：簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點外，其余除了第一個頂點和最后一個頂點外，其余頂點不重復出現(xiàn)的回路。頂點不重復出現(xiàn)的回路。圖的基本術(shù)語圖的基本術(shù)語 V1V2V3V4V5V1V2V3V4Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 232021-12-18子圖：子圖：若圖若圖G=（V，E），），G=（V，E），如果），如果V V 且且E E ，則稱圖，則稱圖G是是G的子圖。的子圖。圖的基本術(shù)語圖的基本術(shù)語 V1V2V3V4V5V1V2V3V4V5V1V3V4Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分P

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

21、ureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 252021-12-18連通分量連通分量1 V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量連通分量2圖的基本術(shù)語圖的基本術(shù)語 v連通分量是對無向圖的一種劃分。連通分量是對無向圖的一種劃分。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 262021-12-18強連通圖：強連通圖：在有向圖中，對圖中任意一對頂點在有向圖中，對圖中任意一對頂點vi和和vj (ij)，若從頂點，若從頂點vi到頂點到頂點vj和從頂點和從頂點vj到頂點到頂點vi均有路徑均有路徑，則稱該有向圖是強連通圖。，則稱該

22、有向圖是強連通圖。強連通分量：強連通分量：非強連通圖非強連通圖的極大強連通子圖。的極大強連通子圖。 圖的基本術(shù)語圖的基本術(shù)語 如何求得一個非連通圖的連通分量如何求得一個非連通圖的連通分量? ?Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 272021-12-18圖的基本術(shù)語圖的基本術(shù)語 V1V2V3V4強連通分量強連通分量1 強連通分量強連通分量2V1V3V4V2Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 282021-12-18生成樹：生成樹：n個頂點的連通圖個頂點的連通圖G的生成樹是包含的生成樹是包含G中中全全部頂點

23、部頂點的一個極小連通的一個極小連通子圖。子圖。 生成森林：生成森林：在非連通圖中，由每個連通分量都可以得在非連通圖中，由每個連通分量都可以得到一棵生成樹，這些連通分到一棵生成樹，這些連通分量的生成樹就組成了一個量的生成樹就組成了一個非連通圖的非連通圖的生成森林生成森林。 如何理解極小連通子圖如何理解極小連通子圖?圖的基本術(shù)語圖的基本術(shù)語 多多構(gòu)成回路構(gòu)成回路少少不連通不連通含有含有n-1條邊條邊Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 292021-12-18V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5

24、生成樹生成樹生成森林生成森林Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 302021-12-18q圖的抽象數(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)定義了弧定義了弧的意義的意義 或信息或信息 Data StructureD

25、ata Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 312021-12-18G1=(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) Data StructureData Structure數(shù)據(jù)結(jié)

26、構(gòu)圖論部分Page 322021-12-18CreateGraph(&G, V, VR);CreateGraph(&G, V, VR);初始條件：初始條件：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);初始條件：圖初始條件：圖

27、G G 存在，存在，u u 和和 G G 中頂點有相同特征。中頂點有相同特征。操作結(jié)果：若操作結(jié)果：若 G G 中存在和中存在和 u u 相同的頂點，則相同的頂點，則返回該頂點返回該頂點 在圖中位置在圖中位置；否則返回其它信息。；否則返回其它信息。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 332021-12-18GetVex(G, v);GetVex(G, v);初始條件：圖初始條件：圖 G G 存在，存在，v v 是是 G G 中某個頂點。中某個頂點。操作結(jié)果：返回操作結(jié)果：返回 v v 的值的值。FirstAdjVex(G, v);FirstAdjV

28、ex(G, v);初始條件：圖初始條件：圖 G G 存在，存在，v v 是是 G G 中某個頂點。中某個頂點。操作結(jié)果：操作結(jié)果：返回返回 v v 的第一個鄰接點。的第一個鄰接點。若該頂點在若該頂點在 G G 中沒中沒 有鄰接點，則返回有鄰接點，則返回“空空”。NextAdjVex(G, v, w);NextAdjVex(G, v, w);初始條件：圖初始條件：圖 G G 存在，存在，v v 是是 G G 中某個頂點，中某個頂點，w w 是是 v v 的的 鄰接頂點。鄰接頂點。操作結(jié)果：操作結(jié)果：返回返回 v v 的（相對于的（相對于 w w 的）下一個鄰接點。的）下一個鄰接點。若若 w w

29、是是 v v 的最后一個鄰接點，則返回的最后一個鄰接點，則返回“空空”。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 342021-12-18PutVex(&G, v, value);PutVex(&G, v, value);初始條件：圖初始條件：圖 G G 存在，存在，v v 是是 G G 中某個頂點。中某個頂點。操作結(jié)果：操作結(jié)果：對對 v v 賦值賦值 valuevalue。InsertVex(&G, v);InsertVex(&G, v);初始條件：圖初始條件：圖 G G 存在，存在，v v 和圖中頂點有相同特征。和圖

30、中頂點有相同特征。操作結(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)的弧。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 352021-12-18InsertArc(&G, v, w);InsertArc(&G, v, w);初始條件：圖初始條件：圖 G G 存在，存在，

31、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 是是無向的，則還無向的，則還 刪除對稱弧刪除對稱弧。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 362021-12

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

33、Visit Visit 是頂點的應用函數(shù)。是頂點的應用函數(shù)。操作結(jié)果：對圖操作結(jié)果：對圖 G G 進行進行廣度優(yōu)先廣度優(yōu)先遍歷。遍歷過程中對每遍歷。遍歷過程中對每 個頂點調(diào)用函數(shù)個頂點調(diào)用函數(shù)Visit Visit 一次且僅一次。一旦一次且僅一次。一旦 visit() visit() 失敗，則操作失敗。失敗，則操作失敗。 ADT Graph ADT GraphData StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 372021-12-18是否可以采用順序存儲結(jié)構(gòu)存儲圖是否可以采用順序存儲結(jié)構(gòu)存儲圖?圖的特點：頂點之間的關(guān)系是圖的特點：頂點之間的關(guān)系是m: :n，即，即

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

35、數(shù)組中，并將它的，并將它的鄰接矩陣存鄰接矩陣存儲在一個二維數(shù)組中儲在一個二維數(shù)組中即構(gòu)成圖的數(shù)組表示。即構(gòu)成圖的數(shù)組表示。v假設(shè)圖中頂點數(shù)為假設(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的值應為該的值應為該弧上的權(quán)值，否則為弧上的權(quán)值，否則為。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 392021-12-18v圖的數(shù)組圖的數(shù)組( (鄰接矩陣鄰接矩陣) )存儲表示存儲

36、表示#define INFINITY #define 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 VRT

37、ype adj; adj; / VRType/ VRType是頂點關(guān)系類型。對無權(quán)圖，用是頂點關(guān)系類型。對無權(quán)圖，用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 V

38、ertexType vexsMAX_VERTEX_NUMvexsMAX_VERTEX_NUM; ; / / 頂點信息頂點信息AdjMatrix AdjMatrix arcsarcs; ; / / 鄰接矩陣鄰接矩陣int int vexnum, arcnumvexnum, arcnum; ; / / 圖的當前頂點數(shù)和弧圖的當前頂點數(shù)和弧( (邊邊) )數(shù)數(shù)GraphKind GraphKind kindkind; ; / / 圖的種類標志圖的種類標志 MGraphMGraph; ;Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 402021-12-18G1G1B

39、DAC0 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=DGData StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 412021-12-18有向圖的鄰接矩陣有向圖的鄰接矩陣V1V2V3V4V1 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 的出度？的出度？鄰接矩陣的第

40、鄰接矩陣的第 i 行元素之和。行元素之和。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 422021-12-18有向圖的鄰接矩陣有向圖的鄰接矩陣V1V2V3V4V1 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 列元素之和。列元素之和。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 432021-12-18有向圖的鄰接矩陣有向圖的鄰接矩陣V1V2V3V4V1 V

41、2 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。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 442021-12-18AECBDG2G20 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

42、11 10 00 0G2.vexs=A,B,C,D,EG2.vexnum=5G2.arcnum=6G2.kind=UDGData StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 452021-12-180 05 57 70 03 35 50 00 04 48 8G G3 3. .a ar rc cs s = =7 70 00 02 21 10 04 42 20 06 63 38 81 16 60 0A AD DE EB BC C7 75 53 31 18 86 64 42 2G3G3G3.vexs=A,B,C,D,EG3.vexnum=5G3.arcnum=8G3.ki

43、nd=UDNData StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 462021-12-18如何求頂點如何求頂點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ù)。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 472021-12-18如何判斷頂點如何判斷頂點 i 和和 j 之間是否存在邊？之間是否

44、存在邊？無向圖的鄰接矩陣無向圖的鄰接矩陣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測試鄰接矩陣中相應位置的元素測試鄰接矩陣中相應位置的元素arcij是否為是否為1。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 482021-12-18如何求頂點如何求頂點 i 的所有鄰接點？的所有鄰接點？無向圖的鄰接矩陣無向圖的鄰接矩陣V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=

45、V1 V2 V3 V4V1V2V3V4將數(shù)組中第將數(shù)組中第 i 行元素掃描一遍，若行元素掃描一遍，若arcij為為1，則，則頂點頂點 j 為頂點為頂點 i 的鄰接點。的鄰接點。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 492021-12-18v特點特點：無向圖無向圖的鄰接的鄰接矩陣對稱矩陣對稱，可，可壓縮存儲壓縮存儲；有；有n n個頂點的無向圖需個頂點的無向圖需存儲空間為存儲空間為n(n+1)/2n(n+1)/2。有向圖有向圖鄰接鄰接矩陣不一定對稱矩陣不一定對稱；有；有n n個頂點的有向圖需存儲空間個頂點的有向圖需存儲空間為為n n。無向圖無向圖中頂點中

46、頂點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的度（出度、：容易判定頂點間有無邊（?。┖陀嬎沩旤c的度（出度、 入度）。入度）。缺點缺點：邊數(shù)較少時，空間浪費較大。：邊數(shù)較少時，空間浪費較大。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 502021-12-

47、18網(wǎng)圖的鄰接矩陣網(wǎng)圖的鄰接矩陣網(wǎng)圖的鄰接矩陣可定義為：網(wǎng)圖的鄰接矩陣可定義為： arcij wij 若若(vi, vj)E（或（或E）0 若若i=j 其他其他V1V2V3V42785 0 2 5 0 0 8 7 0 arc=Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 512021-12-18q 引入原因引入原因v鄰接矩陣在稀疏圖時空間浪費較大。鄰接矩陣在稀疏圖時空間浪費較大。q 實現(xiàn)實現(xiàn)v為圖中為圖中每個頂點建立一個單鏈表每個頂點建立一個單鏈表，第，第i i個單鏈表中的結(jié)點表示依個單鏈表中的結(jié)點表示依附于頂點附于頂點ViVi的邊（有向圖中指以的邊（有向圖

48、中指以ViVi為尾的?。?。為尾的?。?。v每個鏈表附設(shè)一個表頭結(jié)點每個鏈表附設(shè)一個表頭結(jié)點。表結(jié)點表結(jié)點adjvexadjvexnextarcnextarcinfoinfo與與ViVi鄰接的鄰接的點在表頭數(shù)點在表頭數(shù)組中的位置組中的位置頭結(jié)點頭結(jié)點datadatafirstarcfirstarcData StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 522021-12-18#define MAX_VERTEX_NUM 20;#define MAX_VERTEX_NUM 20;typedef struct ArcNode typedef struct ArcNode in

49、t int adjvex; adjvex; / / 該弧所指向的頂點的位置該弧所指向的頂點的位置struct ArcNode struct ArcNode * *nextarc;nextarc; / / 指向下一條弧的指針指向下一條弧的指針I(yè)nfoType InfoType * *info;info; / / 該弧相關(guān)信息的指針該弧相關(guān)信息的指針 ArcNode; ArcNode; typedef struct VNode typedef struct VNode VertexType VertexType data;data;/ / 頂點信息頂點信息ArcNode ArcNode * *fi

50、rstarc;firstarc; / / 指向第一條依附該頂點的弧指向第一條依附該頂點的弧 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; ;Data StructureD

51、ata Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 532021-12-1810323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2無向圖的鄰接表無向圖的鄰接表邊表中的結(jié)點表示什么？邊表中的結(jié)點表示什么？每個結(jié)點對應圖中的一條邊，每個結(jié)點對應圖中的一條邊，鄰接表的空間復雜度為鄰接表的空間復雜度為O(n+e)。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 542021-12-1810323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2無向圖的鄰接表無向圖的鄰接表如何求頂點如何求頂點

52、 i 的度？的度？頂點頂點i的邊表中結(jié)點的個數(shù)。的邊表中結(jié)點的個數(shù)。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 552021-12-18如何判斷頂點如何判斷頂點 i 和頂點和頂點 j之間是否存在邊之間是否存在邊?測試頂點測試頂點 i 的邊表中是否存的邊表中是否存在終點為在終點為 j 的結(jié)點。的結(jié)點。10323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2無向圖的鄰接表無向圖的鄰接表Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 562021-12-18有向圖的鄰接表有向圖的鄰接表V1

53、V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求頂點如何求頂點 i 的出度？的出度？頂點頂點 i 的出邊表中結(jié)點的個數(shù)。的出邊表中結(jié)點的個數(shù)。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 572021-12-18有向圖的鄰接表有向圖的鄰接表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求頂點如何求頂點 i 的入度？的入度？各頂點的出邊表中以頂點各頂點的出邊表中以頂點 i 為為終點的結(jié)點個數(shù)。終點的結(jié)點個數(shù)。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖

54、論部分Page 582021-12-18有向圖的鄰接表有向圖的鄰接表V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求頂點如何求頂點 i 的所有鄰接點？的所有鄰接點？遍歷頂點遍歷頂點 i 的邊表，該邊表中的的邊表，該邊表中的所有終點都是頂點所有終點都是頂點 i 的鄰接點。的鄰接點。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 592021-12-18網(wǎng)圖的鄰接表網(wǎng)圖的鄰接表V1V2V3V427852 1 V1 V2 V3 V40123vertex firstedge5 28 37 0Data StructureDa

55、ta Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 602021-12-18v優(yōu)缺點優(yōu)缺點優(yōu)點優(yōu)點：空間較?。粺o向圖容易求各頂點的度；有向圖容：空間較??；無向圖容易求各頂點的度；有向圖容易求頂點的出度；易求頂點的出度；缺點缺點：求有向圖頂點的入度則不容易，要遍歷整個表。：求有向圖頂點的入度則不容易，要遍歷整個表。為了求頂點的入度，有時可設(shè)逆鄰接表（指向某頂點的為了求頂點的入度，有時可設(shè)逆鄰接表（指向某頂點的鄰接點鏈接成單鏈表）。鄰接點鏈接成單鏈表）。bdac0123acdbdatafirstarc3 0 02adjvex next逆鄰接表逆鄰接表Data StructureData Struct

56、ure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 612021-12-18q 引入原因引入原因v對于同一個對于同一個有向圖需要同時用鄰接表和逆鄰接表有向圖需要同時用鄰接表和逆鄰接表時，不方便。時，不方便。q 實現(xiàn)實現(xiàn)v將在有向圖的將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結(jié)鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結(jié)點表示點表示，由于在鄰接表和逆鄰接表中的頂點，由于在鄰接表和逆鄰接表中的頂點數(shù)據(jù)數(shù)據(jù)是相同的，則在是相同的，則在十字鏈表中十字鏈表中只需要出現(xiàn)一次只需要出現(xiàn)一次，但需，但需保留分別指向第一條保留分別指向第一條 出弧出弧 和和第一條第一條 入弧入弧 的指針的指針。G1G1bdac0123a

57、cdbdatafirstarc 2 1 3 0adjvex next鄰接表鄰接表Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 622021-12-18q 引入原因引入原因v對于同一個對于同一個有向圖需要同時用鄰接表和逆鄰接表有向圖需要同時用鄰接表和逆鄰接表時，不方便。時，不方便。q 實現(xiàn)實現(xiàn)v將在有向圖的將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結(jié)鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結(jié)點表示點表示，由于在鄰接表和逆鄰接表中的頂點，由于在鄰接表和逆鄰接表中的頂點數(shù)據(jù)數(shù)據(jù)是相同的，則在是相同的，則在十字鏈表中十字鏈表中只需要出現(xiàn)一次只需要出現(xiàn)一

58、次，但需，但需保留分別指向第一條保留分別指向第一條 出弧出弧 和和第一條第一條 入弧入弧 的指針的指針。G1G1bdac逆鄰接表逆鄰接表0123acdbdatafirstarc3 0 02adjvex nextData StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 632021-12-18弧結(jié)點弧結(jié)點tailvextailvex headvexheadvexhlinkhlinktlinktlinkinfoinfo頂點結(jié)點頂點結(jié)點datadatafirstinfirstinfirstoutfirstout弧尾弧尾位置位置弧頭弧頭位置位置弧尾相同的下弧尾相同的下一條弧指針

59、一條弧指針弧相關(guān)信息弧相關(guān)信息的指針的指針指向該頂點指向該頂點第一條入弧第一條入弧指向該頂點指向該頂點第一條出弧第一條出弧Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 642021-12-18 0 2 0 1 2 3 2 0 3 2 3 1 3 0bdacab cd0123求結(jié)點的入度求結(jié)點的入度和出度的方法？和出度的方法？Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 652021-12-18q 引入原因引入原因v無向圖的鄰接表中無向圖的鄰接表中每一條邊有兩個結(jié)點，每一條邊有兩個結(jié)點，給對圖的邊進行訪問的給對圖的邊進行訪問

60、的操作帶來不便。有些時候需要同時找到表示同一條邊的兩個結(jié)點操作帶來不便。有些時候需要同時找到表示同一條邊的兩個結(jié)點（如刪除一條邊）。（如刪除一條邊）。aecbd0123acdbdatafirstarc 3 1 0 1adjvex next4e 3 2 4 0 42 12Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 662021-12-18q 實現(xiàn)實現(xiàn)v每條邊用一個結(jié)點表示。每條邊用一個結(jié)點表示。邊結(jié)點邊結(jié)點markmarkivexivexilinkilinkjvexjvexjlinkjlinkinfoinfo頂點結(jié)點頂點結(jié)點markmarkfirstedgefirstedge訪問訪問標記標記邊依附的邊依附的一個頂點一個頂點邊依附的邊依附的另一個頂另一個頂點點