數(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 學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo)v領(lǐng)會(huì)領(lǐng)會(huì)圖的類型定義圖的類型定義。v熟悉熟悉圖的各種存儲(chǔ)結(jié)構(gòu)圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及其構(gòu)造算法，了解各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及其及其選用原則選用原則。v熟練掌握圖的兩種熟練掌握圖的兩種遍歷遍歷算法。算法。v理解各種圖的理解各種圖的應(yīng)用問題的算法應(yīng)用問題的算法。q 重點(diǎn)和難點(diǎn)重點(diǎn)和難點(diǎn)v重點(diǎn)：圖的各種應(yīng)用問題的算法都比較經(jīng)典，注意

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

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

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

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

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

7、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ù)不能為零，但可以沒有邊。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 82021-12-18q線性表線性表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è)直

8、接后繼。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)用于語圖是比線性表和樹復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于語言學(xué)、邏輯學(xué)、物理、化學(xué)等領(lǐng)域。言學(xué)、邏輯學(xué)、物理、化學(xué)等領(lǐng)域。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 92021-12-18如果圖的任意兩個(gè)頂點(diǎn)之間的邊都如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是是無向邊，則稱該圖為無向邊，則稱該圖為無向圖無向圖。若頂點(diǎn)若頂點(diǎn)vi和和vj之間的邊沒有方向，則之間的邊沒有方向，則稱這條邊為稱這條邊為無向邊無向邊，表示為，表

9、示為(vi, ,vj)。若從頂點(diǎn)若從頂點(diǎn)vi到到vj的邊有方向，則稱這的邊有方向，則稱這條邊為條邊為有向邊有向邊，表示為，表示為。 如果圖的任意兩個(gè)頂點(diǎn)之間的邊都如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是是有向邊，則稱該圖為有向邊，則稱該圖為有向圖有向圖。V1V2V3V4V5V1V2V3V4圖的基本術(shù)語圖的基本術(shù)語 Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 102021-12-18簡單圖：簡單圖：在圖中，若不存在頂點(diǎn)到其自身的邊，且同在圖中，若不存在頂點(diǎn)到其自身的邊，且同一條邊不重復(fù)出現(xiàn)一條邊不重復(fù)出現(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ù)語 鄰接、依附鄰接、依附無向圖無向圖中，對于任意兩個(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 、V4V2的鄰接點(diǎn)：的鄰接點(diǎn)： V1 、V3

11、、V5Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 122021-12-18圖的基本術(shù)語圖的基本術(shù)語 鄰接、依附鄰接、依附有向圖有向圖中，對于任意兩個(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)： V2 、V3V3的鄰接點(diǎn)：的鄰接點(diǎn)： V4Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 132021-12-18無向完全

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

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

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

15、 = =niievTD12)(Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 172021-12-18V1V2V3V4圖的基本術(shù)語圖的基本術(shù)語 在具有在具有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)()(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)中，從頂點(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。圖的基本術(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)圖路徑路徑上邊的上邊的個(gè)數(shù)個(gè)數(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)圖路徑路徑上邊的上邊的個(gè)數(shù)個(gè)數(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)）：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。簡單路徑：簡單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡單

19、回路（簡單環(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)的回路。圖的基本術(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連通圖：連通圖：在無向圖中，如果從一個(gè)頂點(diǎn)在無向圖中，如果從一個(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)都是連通的，則稱該圖是連通圖。圖。連通分量：連通分量：非連通圖的極大連通子圖稱為連通分量。非連通圖的極大連通子圖稱為連通分量。 圖的基本術(shù)語圖的基本術(shù)語 如何求得一個(gè)非連通圖的連通分量如何求得一個(gè)非連通圖的連通分量? ?1.含有極大含有極大頂點(diǎn)頂點(diǎn)數(shù)；數(shù)；2. 依附于這些頂點(diǎn)的所有依附于這些頂點(diǎn)的所有邊邊。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強(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)連通圖。，則稱該

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

23、部頂點(diǎn)的一個(gè)極小連通的一個(gè)極小連通子圖。子圖。 生成森林：生成森林：在非連通圖中，由每個(gè)連通分量都可以得在非連通圖中，由每個(gè)連通分量都可以得到一棵生成樹，這些連通分到一棵生成樹，這些連通分量的生成樹就組成了一個(gè)量的生成樹就組成了一個(gè)非連通圖的非連通圖的生成森林生成森林。 如何理解極小連通子圖如何理解極小連通子圖?圖的基本術(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ù)元素的集合，稱為頂 點(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)定義了弧定義了弧的意義的意義 或信息或信息 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 是圖的頂點(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);初始條件：圖初始條件：圖

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

28、ex(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)，則返回“空空”。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

29、是是 v v 的最后一個(gè)鄰接點(diǎn)，則返回的最后一個(gè)鄰接點(diǎn)，則返回“空空”。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 中某個(gè)頂點(diǎn)。中某個(gè)頂點(diǎn)。操作結(jié)果：操作結(jié)果：對對 v v 賦值賦值 valuevalue。InsertVex(&G, v);InsertVex(&G, v);初始條件：圖初始條件：圖 G G 存在，存在，v v 和圖中頂點(diǎn)有相同特征。和圖

30、中頂點(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)的弧及其相關(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 中兩個(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 中中刪除弧刪除弧，若若 G G 是是無向的，則還無向的，則還 刪除對稱弧刪除對稱弧。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 362021-12

32、-18DFSTraverse(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() 失敗，則操作失敗。失敗，則操作失敗。FSTraverse(G, Visit();FSTraverse(G, Visit();初始條件：圖初始條件：圖 G G 存在，存在，

33、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 GraphData StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 372021-12-18是否可以采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)圖是否可以采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)圖?圖的特點(diǎn)：頂點(diǎn)之間的關(guān)系是圖的特點(diǎn)：頂點(diǎn)之間的關(guān)系是m: :n，即，即

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

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

36、表示#define INFINITY #define INFINITY INT_MAX; INT_MAX; / / 最大值最大值#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 VRT

37、ype adj; adj; / VRType/ VRType是頂點(diǎn)關(guān)系類型。對無權(quán)圖，用是頂點(diǎ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; ; / / 頂點(diǎn)信息頂點(diǎn)信息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; ;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如何求頂點(diǎn)如何求頂點(diǎn) 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如何求頂點(diǎn)如何求頂點(diǎn) 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如何判斷從頂點(diǎn)如何判斷從頂點(diǎn) i 到頂點(diǎn)到頂點(diǎn) j 是否存在邊？是否存在邊？測試鄰接矩陣中相應(yīng)位置的元素測試鄰接矩陣中相應(yīng)位置的元素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如何求頂點(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ù)。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 472021-12-18如何判斷頂點(diǎn)如何判斷頂點(diǎn) 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測試鄰接矩陣中相應(yīng)位置的元素測試鄰接矩陣中相應(yīng)位置的元素arcij是否為是否為1。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 482021-12-18如何求頂點(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=

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

46、頂點(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)間有無邊（?。┖陀?jì)算頂點(diǎn)的度（出度、 入度）。入度）。缺點(diǎn)缺點(diǎn)：邊數(shù)較少時(shí)，空間浪費(fèi)較大。：邊數(shù)較少時(shí)，空間浪費(fèi)較大。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鄰接矩陣在稀疏圖時(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é)點(diǎn)表示依個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)附于頂點(diǎn)ViVi的邊（有向圖中指以的邊（有向圖

48、中指以ViVi為尾的?。?。為尾的弧）。v每個(gè)鏈表附設(shè)一個(gè)表頭結(jié)點(diǎn)每個(gè)鏈表附設(shè)一個(gè)表頭結(jié)點(diǎn)。表結(jié)點(diǎn)表結(jié)點(diǎn)adjvexadjvexnextarcnextarcinfoinfo與與ViVi鄰接的鄰接的點(diǎn)在表頭數(shù)點(diǎn)在表頭數(shù)組中的位置組中的位置頭結(jié)點(diǎn)頭結(jié)點(diǎn)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; / / 該弧所指向的頂點(diǎn)的位置該弧所指向的頂點(diǎn)的位置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;/ / 頂點(diǎn)信息頂點(diǎn)信息ArcNode ArcNode * *fi

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

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

52、 i 的度？的度？頂點(diǎn)頂點(diǎn)i的邊表中結(jié)點(diǎn)的個(gè)數(shù)。的邊表中結(jié)點(diǎn)的個(gè)數(shù)。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 552021-12-18如何判斷頂點(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 firstedgeV1V3V4V2無向圖的鄰接表無向圖的鄰接表Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 562021-12-18有向圖的鄰接表有向圖的鄰接表V1

53、V2V3V41220 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ù)。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 572021-12-18有向圖的鄰接表有向圖的鄰接表V1V2V3V41220 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ù)。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖

54、論部分Page 582021-12-18有向圖的鄰接表有向圖的鄰接表V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求頂點(diǎn)如何求頂點(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)。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)缺點(diǎn)優(yōu)缺點(diǎn)優(yōu)點(diǎn)優(yōu)點(diǎn)：空間較??；無向圖容易求各頂點(diǎn)的度；有向圖容：空間較?。粺o向圖容易求各頂點(diǎn)的度；有向圖容易求頂點(diǎn)的出度；易求頂點(diǎn)的出度；缺點(diǎn)缺點(diǎn)：求有向圖頂點(diǎn)的入度則不容易，要遍歷整個(gè)表。：求有向圖頂點(diǎn)的入度則不容易，要遍歷整個(gè)表。為了求頂點(diǎn)的入度，有時(shí)可設(shè)逆鄰接表（指向某頂點(diǎn)的為了求頂點(diǎn)的入度，有時(shí)可設(shè)逆鄰接表（指向某頂點(diǎn)的鄰接點(diǎn)鏈接成單鏈表）。鄰接點(diǎn)鏈接成單鏈表）。bdac0123acdbdatafirstarc3 0 02adjvex next逆鄰接表逆鄰接表Data StructureData Struct

56、ure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 612021-12-18q 引入原因引入原因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)，由于在鄰接表和逆鄰接表中的頂點(diǎn)數(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對于同一個(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)，由于在鄰接表和逆鄰接表中的頂點(diǎn)數(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é)點(diǎn)弧結(jié)點(diǎn)tailvextailvex headvexheadvexhlinkhlinktlinktlinkinfoinfo頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)datadatafirstinfirstinfirstoutfirstout弧尾弧尾位置位置弧頭弧頭位置位置弧尾相同的下弧尾相同的下一條弧指針

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

60、的操作帶來不便。有些時(shí)候需要同時(shí)找到表示同一條邊的兩個(gè)結(jié)點(diǎn)操作帶來不便。有些時(shí)候需要同時(shí)找到表示同一條邊的兩個(gè)結(jié)點(diǎn)（如刪除一條邊）。（如刪除一條邊）。aecbd0123acdbdatafirstarc 3 1 0 1adjvex next4e 3 2 4 0 42 12Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)圖論部分Page 662021-12-18q 實(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)邊依附的邊依附的另一個(gè)頂另一個(gè)頂點(diǎn)點(diǎn)