北京信息科技大學數(shù)據(jù)機構(gòu)第7章圖ppt課件

1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社第七章第七章 圖圖本章的主要內(nèi)容是本章的主要內(nèi)容是:圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)圖的遍歷圖的遍歷圖的連通性與最小生成樹圖的連通性與最小生成樹拓撲排序拓撲排序關(guān)鍵路徑關(guān)鍵路徑 最短路徑最短路徑數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社歐拉歐拉17071707年出生在瑞士的巴塞爾城，年出生在瑞士的巴塞爾城，1919歲開始發(fā)歲開始發(fā)表論文，直到表論文，直到7676歲。幾乎每一個數(shù)學領(lǐng)域都可以歲。幾乎每一個數(shù)學領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體看到歐拉的名字，從初等幾何的歐拉線，

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

3、道學、航海學、建筑學等占建筑學等占3%3%。 1733 1733年，年僅年，年僅2626歲的歐拉擔任歲的歐拉擔任了彼得堡科學院數(shù)學教授。了彼得堡科學院數(shù)學教授。17411741年到柏林擔任科年到柏林擔任科學院物理數(shù)學所所長，直到學院物理數(shù)學所所長，直到17661766年，重回彼得堡，年，重回彼得堡，沒有多久，完全失明。歐拉在數(shù)學上的建樹很多，沒有多久，完全失明。歐拉在數(shù)學上的建樹很多，對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。研究。圖論圖論歐拉歐拉數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社能否從某個地方出發(fā)，穿過所有的橋僅一次能否

4、從某個地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點？后再回到出發(fā)點？哥尼斯堡七橋問題哥尼斯堡七橋問題 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社CADB七橋問題的圖模型七橋問題的圖模型哥尼斯堡七橋問題哥尼斯堡七橋問題 歐拉回路的判定規(guī)則：歐拉回路的判定規(guī)則：1.如果通奇數(shù)橋的地方多于如果通奇數(shù)橋的地方多于兩個，則不存在歐拉回路；兩個，則不存在歐拉回路；2.如果只有兩個地方通奇數(shù)如果只有兩個地方通奇數(shù)橋，可以從這兩個地方之一橋，可以從這兩個地方之一出發(fā)，找到歐拉回路；出發(fā)，找到歐拉回路；3.如果沒有一個地方是通奇如果沒有一個地方是通奇數(shù)橋的，則無論從哪里出發(fā)，數(shù)橋的，則無論從哪里出

5、發(fā)，都能找到歐拉回路。都能找到歐拉回路。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社圖的定義圖的定義7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖是一種數(shù)據(jù)結(jié)構(gòu)。由頂點的有窮非空集合和頂點圖是一種數(shù)據(jù)結(jié)構(gòu)。由頂點的有窮非空集合和頂點之間關(guān)系的集合組成，通常表示為：之間關(guān)系的集合組成，通常表示為： G=(V，E)其中：其中：G表示一個圖，表示一個圖，V是具有相同特性的數(shù)據(jù)元是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集；素的集合，稱為頂點集；E是圖是圖G中頂點之間關(guān)系中頂點之間關(guān)系的集合，成為邊集或弧集。的集合，成為邊集或弧集。 E| v,wV 且且 P(v,w)或或(v,w)| v,wV 且且

6、P(v,w) 表示從表示從 v 到到 w 的一條弧，稱的一條弧，稱 v 為弧頭，為弧頭，w 為弧尾。為弧尾。(v,w)表示表示v與與w之間的一條邊。之間的一條邊。 謂詞謂詞 P(v,w) 定義了弧定義了弧 或邊或邊(v, w)的意義或信息。的意義或信息。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)如果圖的任意兩個頂點之間的邊都如果圖的任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖。是無向邊，則稱該圖為無向圖。若頂點若頂點vivi和和vjvj之間的邊沒有方向，之間的邊沒有方向，則稱這條邊為無向邊，表示為則稱這條邊為無向邊，表示為(vi,vj)(vi

7、,vj)。若從頂點若從頂點vivi到到vjvj的邊有方向，則稱的邊有方向，則稱這條邊為有向邊，表示為這條邊為有向邊，表示為。 如果圖的任意兩個頂點之間的邊都如果圖的任意兩個頂點之間的邊都是有向邊，則稱該圖為有向圖。是有向邊，則稱該圖為有向圖。V1V2V3V4V5V1V2V3V4數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 簡單圖：在圖中，若不存在頂點到其自身的邊，且同簡單圖：在圖中，若不存在頂點到其自身的邊，且同一條邊不重復出現(xiàn)。一條邊不重復出現(xiàn)。V3V4V5V1V2V3V4V5V1V2非簡單圖非簡單圖 非簡單圖非簡單圖 簡

8、單圖簡單圖V1V2V3V4V5v 數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖。數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 鄰接、依靠鄰接、依靠無向圖中，對于任意兩個頂點無向圖中，對于任意兩個頂點vi和頂點和頂點vj，若存在邊，若存在邊(vi，vj)，則稱頂點，則稱頂點vi和頂點和頂點vj互為鄰接點，同時稱互為鄰接點，同時稱邊邊(vi，vj)依附于頂點依附于頂點vi和頂點和頂點vj。V1V2V3V4V5V1的鄰接點：的鄰接點： V2 、V4V2的鄰接點：的鄰接點： V1 、V3 、V5數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版

9、）清華大學出版社清華大學出版社7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 鄰接、依靠鄰接、依靠有向圖中，對于任意兩個頂點有向圖中，對于任意兩個頂點vi和頂點和頂點vj，若存在弧，若存在弧，則稱頂點，則稱頂點vi鄰接到頂點鄰接到頂點vj，頂點，頂點vj鄰接自鄰接自頂點頂點vi，同時稱弧，同時稱弧依附于頂點依附于頂點vi和頂點和頂點vj 。 V1V2V3V4V1的鄰接點：的鄰接點： V2 、V3V3的鄰接點：的鄰接點： V4數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線性關(guān)系；在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線性關(guān)系；在樹結(jié)構(gòu)中，結(jié)點之間

10、具有層次關(guān)系；在樹結(jié)構(gòu)中，結(jié)點之間具有層次關(guān)系；在圖結(jié)構(gòu)中，任意兩個頂點之間都可能有關(guān)系。在圖結(jié)構(gòu)中，任意兩個頂點之間都可能有關(guān)系。 FECBAD線性結(jié)構(gòu)線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)樹結(jié)構(gòu)V1V2V3V4V5圖結(jié)構(gòu)圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對比不同結(jié)構(gòu)中邏輯關(guān)系的對比數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社在線性結(jié)構(gòu)中，元素之間的關(guān)系為前驅(qū)和后繼；在線性結(jié)構(gòu)中，元素之間的關(guān)系為前驅(qū)和后繼；在樹結(jié)構(gòu)中，結(jié)點之間的關(guān)系為雙親和孩子；在樹結(jié)構(gòu)中，結(jié)點之間的關(guān)系為雙親和孩子；在圖結(jié)構(gòu)中，頂點之間的關(guān)系為鄰接。在圖結(jié)構(gòu)中，頂點之間的關(guān)系為鄰接。 FECBAD線性結(jié)構(gòu)線性結(jié)構(gòu)ABCDEF樹

11、結(jié)構(gòu)樹結(jié)構(gòu)V1V2V3V4V5圖結(jié)構(gòu)圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對比不同結(jié)構(gòu)中邏輯關(guān)系的對比數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社無向完全圖：在無向圖中，如果任意兩個頂點之間無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。都存在邊，則稱該圖為無向完全圖。有向完全圖：在有向圖中，如果任意兩個頂點之間有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向相反的兩條弧，則稱該圖為有向完全圖都存在方向相反的兩條弧，則稱該圖為有向完全圖。 圖的基本術(shù)語圖的基本術(shù)語 V1V2V3V1V2V3V47.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華

12、大學出版社清華大學出版社含有含有n n個頂點的無向完全圖有多少條邊？個頂點的無向完全圖有多少條邊？含有含有n n個頂點的有向完全圖有多少條??？個頂點的有向完全圖有多少條??？ 7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)含有含有n個頂點的無向完全圖有個頂點的無向完全圖有n(n-1)/2條邊。條邊。 含有含有n個頂點的有向完全圖有個頂點的有向完全圖有n(n-1)條邊。條邊。 V1V2V3V1V2V3V4數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社稀疏圖：稱邊數(shù)很少的圖為稀疏圖稀疏圖：稱邊數(shù)很少的圖為稀疏圖enlogn）；）；稠密圖：稱邊數(shù)很多的圖為稠密圖稠密圖：稱邊數(shù)很多的圖為稠密圖enlogn

13、） 。頂點的度：在無向圖中，頂點頂點的度：在無向圖中，頂點v的度是指依附于該頂?shù)亩仁侵敢栏接谠擁旤c的邊數(shù)，通常記為點的邊數(shù)，通常記為TD (v)。7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 頂點的入度：在有向圖中，頂點頂點的入度：在有向圖中，頂點v的入度是指以該頂?shù)娜攵仁侵敢栽擁旤c為弧頭的弧的數(shù)目，記為點為弧頭的弧的數(shù)目，記為ID (v)；頂點的出度：在有向圖中，頂點頂點的出度：在有向圖中，頂點v的出度是指以該頂?shù)某龆仁侵敢栽擁旤c為弧尾的弧的數(shù)目，記為點為弧尾的弧的數(shù)目，記為OD (v)。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社V1V2V3V4V57.1 圖的邏

14、輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 在具有在具有n個頂點、個頂點、e條邊的無向圖條邊的無向圖G中，各頂點中，各頂點的度之和與邊數(shù)之和的關(guān)系？的度之和與邊數(shù)之和的關(guān)系？ = = =niievTD12)(數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社V1V2V3V47.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 在具有在具有n個頂點、個頂點、e條邊的有向圖條邊的有向圖G中，各頂點中，各頂點的入度之和與各頂點的出度之和的關(guān)系？與邊的入度之和與各頂點的出度之和的關(guān)系？與邊數(shù)之和的關(guān)系？數(shù)之和的關(guān)系？evODvIDiiii= = = = = =11)()(nn數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)

15、結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社權(quán)：是指對邊賦予的有意義的數(shù)值量。權(quán)：是指對邊賦予的有意義的數(shù)值量。網(wǎng)：邊上帶權(quán)的圖，也稱網(wǎng)圖。網(wǎng)：邊上帶權(quán)的圖，也稱網(wǎng)圖。7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 V1V2V3V42785數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社途徑：在無向圖途徑：在無向圖G=(V, E)中，從頂點中，從頂點vp到頂點到頂點vq之間之間的路徑是一個頂點序列的路徑是一個頂點序列(vp=vi0,vi1,vi2, , vim=vq)，其中，其中，(vij-1,vij)E1jm）。若）。若G是有向圖，則路是有向圖，則路徑也是有方向的，頂點序

16、列滿足徑也是有方向的，頂點序列滿足E。7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 V1V2V3V4V5v一般情況下，圖中的路徑不惟一。一般情況下，圖中的路徑不惟一。V1 到到V4的路徑：的路徑： V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社路徑長度：路徑長度：7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 非帶權(quán)圖非帶權(quán)圖路徑上邊的個數(shù)路徑上邊的個數(shù)帶權(quán)圖帶權(quán)圖路徑上各邊的權(quán)之和路徑上各邊的權(quán)之和V1V2V3V4V5V1 V4：長度為：長度為1V1 V2 V3 V4 ：長度為：長度為3V1 V2

17、 V5V3 V4 ：長度：長度為為4數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社路徑長度：路徑長度：7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(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 ：長度為：長度為15V1V2V3V4V5256328數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社回路環(huán)）：第一個頂點和最后一個頂點相同的路徑。回路環(huán)）：第一個頂點和最后一個頂點相同的路徑。簡單路徑：序列中頂點不重復出現(xiàn)的路徑

18、。簡單路徑：序列中頂點不重復出現(xiàn)的路徑。簡單回路簡單環(huán)）：除了第一個頂點和最后一個頂點簡單回路簡單環(huán)）：除了第一個頂點和最后一個頂點外，其余頂點不重復出現(xiàn)的回路。外，其余頂點不重復出現(xiàn)的回路。7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 V1V2V3V4V5V1V2V3V4數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社子圖：若圖子圖：若圖G=（V，E），），G=（V，E），如果），如果VV 且且E E ，則稱圖，則稱圖G是是G的子圖。的子圖。7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 V1V2V3V4V5V1V2V3V4V5V1V3V4數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（

19、C版）版）清華大學出版社清華大學出版社連通圖：在無向圖中，如果從一個頂點連通圖：在無向圖中，如果從一個頂點vi到另一個頂?shù)搅硪粋€頂點點vj(ij)有路徑，則稱頂點有路徑，則稱頂點vi和和vj是連通的。如果圖是連通的。如果圖中任意兩個頂點都是連通的，則稱該圖是連通圖。中任意兩個頂點都是連通的，則稱該圖是連通圖。連通分量：非連通圖的極大連通子圖稱為連通分量。連通分量：非連通圖的極大連通子圖稱為連通分量。 7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 如何求得一個非連通圖的連通分量如何求得一個非連通圖的連通分量? ?1.含有極大頂點數(shù)；含有極大頂點數(shù)；2. 依附于這些頂點的所有邊。依附于

20、這些頂點的所有邊。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社連通分量連通分量1 7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量連通分量2圖的基本術(shù)語圖的基本術(shù)語 v連通分量是對無向圖的一種劃分。連通分量是對無向圖的一種劃分。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社強連通圖：在有向圖中，對圖中任意一對頂點強連通圖：在有向圖中，對圖中任意一對頂點vi和和vj (ij)，若從頂點，若從頂點vi到頂點到頂點vj和從頂點和從頂點vj到頂點到頂點vi均有路均有路徑，則稱該有向圖是強連通圖。徑，則稱該有向圖是強連通圖。強連通

21、分量：非強連通圖的極大強連通子圖。強連通分量：非強連通圖的極大強連通子圖。 7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 如何求得一個非連通圖的連通分量如何求得一個非連通圖的連通分量? ?數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 V1V2V3V4強連通分量強連通分量1 強連通分量強連通分量2V1V3V4V2數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社生成樹：生成樹：n個頂點的連通圖個頂點的連通圖G的生成樹是包含的生成樹是包含G中全中全部頂點的一個極小連通子圖。（部頂點的一個極小連通子圖。（n個頂

22、點的數(shù)至少有個頂點的數(shù)至少有n-1條邊）條邊） 生成森林：在非連通圖中，由每個連通分量都可以得生成森林：在非連通圖中，由每個連通分量都可以得到一棵生成樹，這些連通分量的生成樹就組成了一個到一棵生成樹，這些連通分量的生成樹就組成了一個非連通圖的生成森林。非連通圖的生成森林。 如何理解極小連通子圖如何理解極小連通子圖?7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)圖的基本術(shù)語圖的基本術(shù)語 多了多了構(gòu)成回路構(gòu)成回路少了少了不連通不連通含有含有n-1條邊條邊數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成樹

23、生成樹生成森林生成森林7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社圖的抽象數(shù)據(jù)類型定義圖的抽象數(shù)據(jù)類型定義 7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)ADT GraphADT Graph數(shù)據(jù)對象數(shù)據(jù)對象V V；V V是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R: R=ER: R=E（弧集或邊集）（弧集或邊集）基本操作基本操作P P：構(gòu)造、銷毀、頂點操作、弧操作、遍歷等：構(gòu)造、銷毀、頂點操作、弧操作、遍歷等CreatGraph(&G, V, E) / CreatGraph(&G, V, E) / 按定義按定

24、義(V, E) (V, E) 構(gòu)造圖構(gòu)造圖DestroyGraph(&G) / DestroyGraph(&G) / 銷毀圖銷毀圖LocateVex(G, u) / LocateVex(G, u) / 若若G G中存在頂點中存在頂點u u，則返回該頂點在，則返回該頂點在圖中圖中“位置位置” ” ；否則返回其它信息。；否則返回其它信息。GetVex(G, v) / GetVex(G, v) / 前往前往 v v 的值。的值。PutVex(&G, v, value) / PutVex(&G, v, value) / 對對 v v 賦值賦值valuevalue。Fir

25、stAdjVex(G, v) / FirstAdjVex(G, v) / 前往前往 v v 的的“第一個鄰接點第一個鄰接點” ” 。若。若該頂點在該頂點在 G G 中沒有鄰接點，則返回中沒有鄰接點，則返回“空空”。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社圖的抽象數(shù)據(jù)類型定義圖的抽象數(shù)據(jù)類型定義 7.1 圖的邏輯結(jié)構(gòu)圖的邏輯結(jié)構(gòu)NextAdjVex(G, v, w); / 前往前往 v 的的(相對于相對于 w 的的) “下一個鄰接下一個鄰接 /點點 ”。 假設假設 w 是是 v 的最后一個鄰接點，則返回的最后一個鄰接點，則返回“空空”。InsertVex(&G, v);

26、 /在圖在圖 G中增添新頂點中增添新頂點v。DeleteVex(&G, v); / 刪除刪除G中頂點中頂點v及其相關(guān)的弧。及其相關(guān)的弧。InsertArc(&G, v, w);/在在G中增添弧中增添弧，若，若G是無向的，是無向的， /則還增添對稱弧則還增添對稱弧。DeleteArc(&G, v, w); /在在G中刪除弧中刪除弧，若，若G是無向的，是無向的， /則還刪除對稱弧則還刪除對稱弧。DFSTraverse(G, v, Visit(); /從頂點從頂點v起深度優(yōu)先遍歷圖起深度優(yōu)先遍歷圖G，并，并 /對每個頂點調(diào)用函數(shù)對每個頂點調(diào)用函數(shù)Visit一次且僅一次。一次且

27、僅一次。BFSTraverse(G, v, Visit(); /從頂點從頂點v起廣度優(yōu)先遍歷圖起廣度優(yōu)先遍歷圖G，并，并 /對每個頂點調(diào)用函數(shù)對每個頂點調(diào)用函數(shù)Visit一次且僅一次。一次且僅一次。 ADT Graph數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)是否可以采用順序存儲結(jié)構(gòu)存儲圖是否可以采用順序存儲結(jié)構(gòu)存儲圖?圖的特點：頂點之間的關(guān)系是圖的特點：頂點之間的關(guān)系是m:nm:n，即任何兩，即任何兩個頂點之間都可能存在關(guān)系邊或?。瑹o法個頂點之間都可能存在關(guān)系邊或弧），無法通過存儲位置表示這種任意的邏輯關(guān)系，所以，通過存儲位置表示

28、這種任意的邏輯關(guān)系，所以，圖無法采用順序存儲結(jié)構(gòu)。圖無法采用順序存儲結(jié)構(gòu)。如何存儲圖如何存儲圖?考慮圖的定義，圖是由頂點和邊組成的，分別考慮圖的定義，圖是由頂點和邊組成的，分別考慮如何存儲頂點、如何存儲邊?？紤]如何存儲頂點、如何存儲邊。線性表、二叉樹都可以兩種不同的存儲結(jié)構(gòu)線性表、二叉樹都可以兩種不同的存儲結(jié)構(gòu)-順序和鏈式存儲結(jié)構(gòu)來存儲。順序和鏈式存儲結(jié)構(gòu)來存儲。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)如何設計圖的頂點結(jié)構(gòu)和邊結(jié)構(gòu)呢？如何設計圖的頂點結(jié)構(gòu)和邊結(jié)構(gòu)呢？ 如果按照度數(shù)最大的結(jié)點設計結(jié)點存儲結(jié)構(gòu)，浪如果按照度數(shù)最大的結(jié)點設

29、計結(jié)點存儲結(jié)構(gòu)，浪費；若按照各自的度數(shù)設計又會造成操作的不便。費；若按照各自的度數(shù)設計又會造成操作的不便。 下面我們介紹的四種存儲表示法將分別對圖中的下面我們介紹的四種存儲表示法將分別對圖中的頂點結(jié)構(gòu)和弧邊結(jié)構(gòu)分別進行設計。頂點結(jié)構(gòu)和弧邊結(jié)構(gòu)分別進行設計。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社一、鄰接矩陣數(shù)組表示法）一、鄰接矩陣數(shù)組表示法）基本思想：用一個一維數(shù)組存儲圖中頂點的信息，基本思想：用一個一維數(shù)組存儲圖中頂點的信息，用一個二維數(shù)組稱為鄰接矩陣存儲圖中各頂點用一個二維數(shù)組稱為鄰接矩陣存儲圖中各頂點之間的鄰接關(guān)系。之間的鄰接關(guān)系。7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)

30、及實現(xiàn)假設圖假設圖G(V，E)有有n個頂點，則鄰接矩陣是一個頂點，則鄰接矩陣是一個個nn的方陣，定義為：的方陣，定義為：arcij1 假設假設(vi, vj)E或或E）0 其它其它數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社無向圖的鄰接矩陣的特點？無向圖的鄰接矩陣的特點？無向圖的鄰接矩陣無向圖的鄰接矩陣7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xià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主對角線為主對角線為 0 且一定是對稱矩陣。且一定是對稱矩陣。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)

31、結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社如何求頂點如何求頂點i的度？的度？無向圖的鄰接矩陣無向圖的鄰接矩陣7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xià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鄰接矩陣的第鄰接矩陣的第i行或第行或第i列非零元素的個數(shù)。列非零元素的個數(shù)。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社如何判斷頂點如何判斷頂點 i 和和 j 之間是否存在邊？之間是否存在邊？無向圖的鄰接矩陣無向圖的鄰接矩陣7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)V

32、1V3V4V2V1 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。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社如何求頂點如何求頂點 i 的所有鄰接點？的所有鄰接點？無向圖的鄰接矩陣無向圖的鄰接矩陣7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xià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ù)組中

33、第將數(shù)組中第 i 行元素掃描一遍，若行元素掃描一遍，若arcij為為1，則，則頂點頂點 j 為頂點為頂點 i 的鄰接點。的鄰接點。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接矩陣有向圖的鄰接矩陣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有向圖的鄰接矩陣一定不對稱嗎？有向圖的鄰接矩陣一定不對稱嗎？不一定，例如有向完全圖。不一定，例如有向完全圖。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.2

34、圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接矩陣有向圖的鄰接矩陣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 行元素之和。行元素之和。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接矩陣有向圖的鄰接矩陣V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3

35、 V4V1V2V3V4如何求頂點如何求頂點 i 的入度？的入度？鄰接矩陣的第鄰接矩陣的第 i 列元素之和。列元素之和。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接矩陣有向圖的鄰接矩陣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 到頂點到頂點 j 是否存在弧？是否存在弧？測試鄰接矩陣中相應位置的元素測試鄰接矩陣中相應位置的元素arcij是否為是否為1。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版

36、）清華大學出版社清華大學出版社網(wǎng)圖的鄰接矩陣網(wǎng)圖的鄰接矩陣7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)網(wǎng)圖的鄰接矩陣可定義為：網(wǎng)圖的鄰接矩陣可定義為： arcij wij 假設假設(vi, vj)E或或E）0 若若i=j 其他其他V1V2V3V42785 0 2 5 0 0 8 7 0 arc=數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社typedef struct ArcCell / 弧的定義弧的定義 VRType adj; / VRType是頂點關(guān)系類型。是頂點關(guān)系類型。 / 對無權(quán)圖，用對無權(quán)圖，用1或或0表示相鄰否；表示相鄰否； / 對帶權(quán)圖，則為權(quán)值類型。對帶權(quán)圖，則為

37、權(quán)值類型。 Info *info；/該弧相關(guān)信息的指針該弧相關(guān)信息的指針 AdjMatrixN N;/這里假設這里假設N為最大頂點個數(shù)為最大頂點個數(shù)7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社 Status CreateGraph( MGraph &G ) / 算法算法7.1 / 采用數(shù)組采用數(shù)組(鄰接矩陣鄰接矩陣)表示法，構(gòu)造圖表示法，構(gòu)造圖G。 scanf(&G.kind); / 自定義輸入函數(shù)，讀入一個隨機值自定義輸入函數(shù)，讀入一個隨機值 switch (G.kind) case DG: return Create

38、DG(G); / 構(gòu)造有向圖構(gòu)造有向圖G case DN: return CreateDN(G); / 構(gòu)造有向網(wǎng)構(gòu)造有向網(wǎng)G case UDG: return CreateUDG(G); / 構(gòu)造無向圖構(gòu)造無向圖G case UDN: return CreateUDN(G); / 構(gòu)造無向網(wǎng)構(gòu)造無向網(wǎng)G，算法，算法7.2 default : return ERROR; / CreateGraph7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社鄰接矩陣中圖的基本操作鄰接矩陣中圖的基本操作構(gòu)造函數(shù)構(gòu)造函數(shù) 確定圖的頂點個數(shù)和邊的個數(shù)；確定圖的

39、頂點個數(shù)和邊的個數(shù)；2. 輸入頂點信息，構(gòu)造頂點向量輸入頂點信息，構(gòu)造頂點向量vertexvexnum；3. 初始化鄰接矩陣；初始化鄰接矩陣；4. 依次輸入每條邊存儲在鄰接矩陣依次輸入每條邊存儲在鄰接矩陣arc中；中； 4.1 確定邊依附的兩個頂點的序號確定邊依附的兩個頂點的序號i, j； 4.2 將鄰接矩陣的第將鄰接矩陣的第i行第行第j列置為邊的權(quán)值列置為邊的權(quán)值w； 4.3 將鄰接矩陣的第將鄰接矩陣的第j行第行第i列置為邊的權(quán)值列置為邊的權(quán)值w ；7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社Status CreateUDN(MGra

40、ph &G) / 算法算法7.2 / 采用數(shù)組鄰接矩陣表示法，構(gòu)造無向網(wǎng)采用數(shù)組鄰接矩陣表示法，構(gòu)造無向網(wǎng)G。 int i,j,k,w; VertexType v1,v2; printf(G.vexnum : ); scanf(%d,&G.vexnum);/輸入頂點個數(shù)輸入頂點個數(shù) printf(“G.arcnum :”); scanf(“%d”,&G.arcnum);/輸入弧的個數(shù)輸入弧的個數(shù) for (i=0; iG.vexnum; +i ) printf(G.vertex%d : ,i); scanf(%c,&G.vertexi); / 構(gòu)造頂點向量構(gòu)造頂

41、點向量 for (i=0; iG.vexnum; +i ) / 初始化鄰接矩陣初始化鄰接矩陣 for (j=0; jG.vexnum; +j ) G.arcsij.adj = INFINITY; /adj,info G.arcsij= NULL; 7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社 for (k=0; kG.arcnum; +k ) / 構(gòu)造鄰接矩陣構(gòu)造鄰接矩陣 printf(v1 (char) : ); scanf(%c, &v1);getchar(); printf(v2 (char) : ); scanf(%c,

42、 &v2);getchar(); printf(w (int) : ); scanf(%d, &w); getchar(); / 輸入一條邊依附的頂點及權(quán)值輸入一條邊依附的頂點及權(quán)值 i = LocateVex(G, v1); j = LocateVex(G, v2); / 確定確定v1和和v2在在G中位置中位置 G.arcsij.adj = w; / 弧弧的權(quán)值的權(quán)值 / if (IncInfo) scanf(G.arcsij); / 輸入弧含有相關(guān)輸入弧含有相關(guān)信息信息 G.arcsji.adj = G.arcsij.adj; / 置置的對稱的對稱弧弧 return OK;

43、 / CreateUDN7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社二、鄰接表二、鄰接表鄰接表存儲的基本思想：對于圖的每個頂點鄰接表存儲的基本思想：對于圖的每個頂點vi，將所，將所有鄰接于有鄰接于vi的頂點鏈成一個單鏈表，稱為頂點的頂點鏈成一個單鏈表，稱為頂點vi的邊的邊表對于有向圖則稱為出邊表），所有邊表的頭指表對于有向圖則稱為出邊表），所有邊表的頭指針和存儲頂點信息的一維數(shù)組構(gòu)成了頂點表。針和存儲頂點信息的一維數(shù)組構(gòu)成了頂點表。 7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)圖的鄰接矩陣存儲結(jié)構(gòu)的空間復雜度？圖的鄰接矩陣存儲結(jié)構(gòu)的空間

44、復雜度？如果為稀疏圖則會出現(xiàn)什么現(xiàn)象？如果為稀疏圖則會出現(xiàn)什么現(xiàn)象？ 假設圖假設圖G有有n個頂點個頂點e條邊，則存儲該圖需要條邊，則存儲該圖需要O(n2) 。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社鄰接表有兩種結(jié)點結(jié)構(gòu)：頂點表結(jié)點和邊表結(jié)點。鄰接表有兩種結(jié)點結(jié)構(gòu)：頂點表結(jié)點和邊表結(jié)點。datafirstarc adjvex nextarc頭頭(頂點頂點)結(jié)點結(jié)點 表表(邊邊)結(jié)點結(jié)點 vertex：數(shù)據(jù)域，存放頂點信息。：數(shù)據(jù)域，存放頂點信息。 firstedge：指針域，指向邊表中第一個結(jié)點。：指針域，指向邊表中第一個結(jié)點。 adjvex：鄰接點域，邊的終點在頂點表中的下標

45、。：鄰接點域，邊的終點在頂點表中的下標。next：指針域，指向邊表中的下一個結(jié)點。：指針域，指向邊表中的下一個結(jié)點。 7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社Typedef struct ArcNode int adjvex; ArcNode *nextarc; ArcNode;Typedef struct VNode Vertextype data; ArcNode *firstarc;VNode，AdjListN；/N為圖的最大頂點數(shù)為圖的最大頂點數(shù)定義鄰接表的結(jié)點定義鄰接表的結(jié)點 7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)d

46、ata firstarc adjvex nextarc表邊結(jié)點表邊結(jié)點頭頂點結(jié)點頭頂點結(jié)點數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 圖的種類標志圖的種類標志 ALGraph;圖的結(jié)構(gòu)定義圖的結(jié)構(gòu)定義7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社10323101 V1 V2 V3 V40123Data firstarc7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)V1V3V4V2無向圖的鄰接表無向圖

47、的鄰接表表邊結(jié)點表示什么？表邊結(jié)點表示什么？每個表邊結(jié)點對應圖中的一條邊，每個表邊結(jié)點對應圖中的一條邊，鄰接表的空間復雜度為鄰接表的空間復雜度為O(n+e)。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社10323101 V1 V2 V3 V40123Data firstarc7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)V1V3V4V2無向圖的鄰接表無向圖的鄰接表如何求頂點如何求頂點 i 的度？的度？頂點頂點i的邊鏈表中結(jié)點的個數(shù)。的邊鏈表中結(jié)點的個數(shù)。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社如何判斷頂點如何判斷頂點 i 和頂點和頂點 j之間是否存在邊之間是否存在

48、邊?測試頂點測試頂點 i 的邊鏈表中是否的邊鏈表中是否存在終點為存在終點為 j 的結(jié)點。的結(jié)點。7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)10323101 V1 V2 V3 V40123Data firstarcV1V3V4V2無向圖的鄰接表無向圖的鄰接表數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接表有向圖的鄰接表V1V2V3V41230 V1 V2 V3 V40123data firstarc如何求頂點如何求頂點 i 的出度？的出度？頂點頂點 i 的出邊鏈表中結(jié)點的個數(shù)的出邊鏈表中結(jié)點的個數(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）

49、清華大學出版社清華大學出版社7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接表有向圖的鄰接表V1V2V3V41230 V1 V2 V3 V40123data firstarc如何求頂點如何求頂點 i 的入度？的入度？各頂點的出邊鏈表中以頂點各頂點的出邊鏈表中以頂點 i 為終點的結(jié)點個數(shù)。為終點的結(jié)點個數(shù)。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的逆向鄰接表有向圖的逆向鄰接表V1V2V3V4如何求頂點如何求頂點 i 的入度？的入度？頂點頂點i的入邊鏈表中的結(jié)點個數(shù)的入邊鏈表中的結(jié)點個數(shù)3002 V1 V2 V3 V401

50、23data firstarc數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接表有向圖的鄰接表V1V2V3V41230 V1 V2 V3 V40123Data firstarc如何求頂點如何求頂點 i 的所有鄰接點？的所有鄰接點？遍歷頂點遍歷頂點 i 的邊鏈表，該邊鏈表中的邊鏈表，該邊鏈表中的所有終點都是頂點的所有終點都是頂點 i 的鄰接點。的鄰接點。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)網(wǎng)圖的鄰接表網(wǎng)圖的鄰接表V1V2V3V427852 1 V1 V2 V3 V4

51、0123Data firstarc5 28 37 0數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社鄰接表中圖的基本操作鄰接表中圖的基本操作構(gòu)造函數(shù)構(gòu)造函數(shù) 1. 確定圖的頂點個數(shù)和邊的個數(shù)；確定圖的頂點個數(shù)和邊的個數(shù)；2. 輸入頂點信息，初始化該頂點的邊表；輸入頂點信息，初始化該頂點的邊表；3. 依次輸入邊的信息并存儲在邊表中；依次輸入邊的信息并存儲在邊表中； 3.1 輸入邊所依附的兩個頂點的序號輸入邊所依附的兩個頂點的序號i和和j； 3.2 生成鄰接點序號為生成鄰接點序號為j的邊表結(jié)點的邊表結(jié)點s； 3.3 將結(jié)點將結(jié)點s插入到第插入到第i個邊表的頭部；個邊表的頭部；7.2 圖的

52、存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社優(yōu)點：在邊稀疏的情況下，用鄰接表比鄰接矩陣優(yōu)點：在邊稀疏的情況下，用鄰接表比鄰接矩陣節(jié)省存儲空間，當和邊相關(guān)的信息較多時更是如節(jié)省存儲空間，當和邊相關(guān)的信息較多時更是如此。此。缺陷：在鄰接表上容易找到任一頂點的第一個鄰缺陷：在鄰接表上容易找到任一頂點的第一個鄰接點和下一個鄰接點，但要判定任意兩個頂點之接點和下一個鄰接點，但要判定任意兩個頂點之間是否有邊或弧相連則需搜索兩個鏈表，不及鄰間是否有邊或弧相連則需搜索兩個鏈表，不及鄰接矩陣方便。接矩陣方便。N N個頂點，個頂點，e e條邊的無向圖，鄰接表需要條邊的

53、無向圖，鄰接表需要n n個頭結(jié)點個頭結(jié)點和和2e2e個表結(jié)點。個表結(jié)點。7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社三、十字鏈表三、十字鏈表-有向圖的另一種鏈式存儲有向圖的另一種鏈式存儲結(jié)構(gòu)結(jié)構(gòu) 鄰接表鄰接表7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)逆鄰接表逆鄰接表將鄰接表與逆鄰接表合二為一將鄰接表與逆鄰接表合二為一?為什么要合并？為什么要合并？V1V2V3V412 3 0v1v2v3v401231 3 0 2 v1v2v3v4012303 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社十字鏈表的結(jié)點結(jié)構(gòu)十字鏈表的結(jié)點結(jié)構(gòu)

54、 datafirstin firstout頂點結(jié)點頂點結(jié)點tailvex：弧尾頂點在圖中的位置，即在頂點表中的下標；：弧尾頂點在圖中的位置，即在頂點表中的下標；headvex：弧頭頂點在圖中的位置，即在頂點表中的下標；：弧頭頂點在圖中的位置，即在頂點表中的下標；headlink：指向弧頭相同的下一條弧的指針；：指向弧頭相同的下一條弧的指針；taillink：指向弧尾相同的下一條弧的指針；：指向弧尾相同的下一條弧的指針；Info :指向該弧的相關(guān)信息。指向該弧的相關(guān)信息。7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)data：數(shù)據(jù)域，存放頂點信息；：數(shù)據(jù)域，存放頂點信息；firstin：指向該頂點

55、的第一條入弧的指針；：指向該頂點的第一條入弧的指針；firstout：指向該頂點的第一條出弧的指針：指向該頂點的第一條出弧的指針 ；tailvex headvex headlink taillink弧結(jié)點弧結(jié)點info數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社3 03 1 3210V1V2V3V42 3 0 10 2 7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)十字鏈表存儲有向圖十字鏈表存儲有向圖 V1V2V3V4v3v4v4v1v1v2v1v3v4v2數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社typedef struct ArcBox / 弧的結(jié)構(gòu)表示弧的結(jié)構(gòu)

56、表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; ArcBox;typedef struct VexNode / 頂點的結(jié)構(gòu)表示頂點的結(jié)構(gòu)表示 VertexType data; ArcBox *firstin, *firstout; VexNode;有向圖的十字鏈表存儲表示有向圖的十字鏈表存儲表示 7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社typedef struct VexNode xlistN; /N為最大頂點數(shù)為最大頂點數(shù) / 頂點結(jié)點頂

57、點結(jié)點(表頭向量表頭向量) int vexnum, arcnum; /有向圖的當前頂點數(shù)和弧數(shù)有向圖的當前頂點數(shù)和弧數(shù) OLGraph;有向圖的結(jié)構(gòu)表示有向圖的結(jié)構(gòu)表示(十字鏈表十字鏈表)7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖十字鏈表結(jié)構(gòu)表示的優(yōu)點：有向圖十字鏈表結(jié)構(gòu)表示的優(yōu)點： 容易求得頂點的入度和出度容易求得頂點的入度和出度數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社Status CreateDG(OLGraph &G) / 算法算法7.3 / 采用十字鏈表表示法，構(gòu)造有向圖采用十字鏈表表示法，構(gòu)造有向圖GG.kind=DG)。scanf(&G.v

58、exnum,&G.arcnum,&IncInfo); /輸入頂點和弧的個數(shù)輸入頂點和弧的個數(shù)for (i=0; iG.vexnum; i+ ) scanf(&G.xlisti.data); G.xlisti.firstin=Null; G.xlisti.firstout=Null; / 初始化指針初始化指針 for (k=0; kinfo);/createDG采用十字鏈表法構(gòu)造有向圖的算法采用十字鏈表法構(gòu)造有向圖的算法7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社四、無向圖的鄰接多重表存儲表示四、無向圖的鄰接多重表

59、存儲表示頂點的結(jié)點結(jié)構(gòu)頂點的結(jié)點結(jié)構(gòu)data firstedge邊的結(jié)點結(jié)構(gòu)邊的結(jié)點結(jié)構(gòu)mark ivex ilink jvex jlink info盡管鄰接表能很好的表示無向圖，但每條邊盡管鄰接表能很好的表示無向圖，但每條邊vi，vj有兩個結(jié)點，分別在第有兩個結(jié)點，分別在第i個和第個和第j個鏈表中，給個鏈表中，給圖的操作帶來不便。圖的操作帶來不便。7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社ABCDABCD0 12 10 20 33 1 四、無向圖的鄰接多重表存儲表示四、無向圖的鄰接多重表存儲表示7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)

60、及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社四、無向圖的鄰接多重表存儲表示四、無向圖的鄰接多重表存儲表示Typedef emnu unvisited,visited VisitIf;typedef struct Ebox VisitIf mark; / 訪問標記訪問標記 int ivex, jvex; /該邊依附的兩個頂點的位置該邊依附的兩個頂點的位置 struct EBox *ilink, *jlink; InfoType *info; / 該邊信息指針該邊信息指針 EBox;邊的結(jié)構(gòu)表示邊的結(jié)構(gòu)表示7.2 圖的存儲結(jié)構(gòu)及實現(xiàn)圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學出版社清華大學出版社typedef struct / 鄰接多重表鄰接多重表 VexBox adjmulistN; int vexnum, edgenum; AMLG