數(shù)據(jù)結構(C++版)

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

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ù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社能否從某個地方出發(fā)，穿過所有的橋僅

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

5、從哪里出發(fā)，都能找到歐拉回路。都能找到歐拉回路。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社圖的定義圖的定義6.1 圖的邏輯結構圖的邏輯結構圖是由圖是由頂點頂點的的有窮非空有窮非空集合和頂點之間集合和頂點之間邊邊的集合組的集合組成，通常表示為：成，通常表示為： G=(V，E)其中：其中：G表示一個圖，表示一個圖，V是圖是圖G中頂點的集合，中頂點的集合，E是是圖圖G中頂點之間邊的集合。中頂點之間邊的集合。 在線性表中，元素個數(shù)可以為零，稱為空表；在線性表中，元素個數(shù)可以為零，稱為空表；在樹中，結點個數(shù)可以為零，稱為空樹；在樹中，結點個數(shù)可以為零，稱為空樹；在圖中，頂點個數(shù)不能為零，

6、但可以沒有邊。在圖中，頂點個數(shù)不能為零，但可以沒有邊。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.1 圖的邏輯結構圖的邏輯結構如果圖的任意兩個頂點之間的邊都如果圖的任意兩個頂點之間的邊都是是無向邊，則稱該圖為無向邊，則稱該圖為無向圖無向圖。若頂點若頂點vi和和vj之間的邊沒有方向，則之間的邊沒有方向，則稱這條邊為稱這條邊為無向邊無向邊，表示為，表示為(vi, ,vj)。若從頂點若從頂點vi到到vj的邊有方向，則稱這的邊有方向，則稱這條邊為條邊為有向邊有向邊，表示為，表示為。 如果圖的任意兩個頂點之間的邊都如果圖的任意兩個頂點之間的邊都是是有向邊，則稱該圖為有向邊，則稱該圖為有

7、向圖有向圖。V1V2V3V4V5V1V2V3V4數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 簡單圖：簡單圖：在圖中，若不存在頂點到其自身的邊，且同在圖中，若不存在頂點到其自身的邊，且同一條邊不重復出現(xiàn)一條邊不重復出現(xiàn)。V3V4V5V1V2V3V4V5V1V2非簡單圖非簡單圖 非簡單圖非簡單圖 簡單圖簡單圖V1V2V3V4V5v 數(shù)據(jù)結構中討論的都是簡單圖。數(shù)據(jù)結構中討論的都是簡單圖。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 鄰接、依附鄰接、依附無向圖

8、無向圖中，對于任意兩個頂點中，對于任意兩個頂點vi和頂點和頂點vj，若存在邊若存在邊(vi，vj)，則稱頂點，則稱頂點vi和頂點和頂點vj互為鄰接點，同時稱邊互為鄰接點，同時稱邊(vi，vj)依附于頂點依附于頂點vi和頂點和頂點vj。V1V2V3V4V5V1的鄰接點：的鄰接點： V2 、V4V2的鄰接點：的鄰接點： V1 、V3 、V5數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 鄰接、依附鄰接、依附有向圖有向圖中，對于任意兩個頂點中，對于任意兩個頂點vi和頂點和頂點vj，若存在弧若存在弧，則稱頂點則稱頂點vi鄰接到頂點鄰接

9、到頂點vj，頂點頂點vj鄰接自頂鄰接自頂點點vi，同時稱弧同時稱弧依附于頂點依附于頂點vi和頂點和頂點vj 。 V1V2V3V4V1的鄰接點：的鄰接點： V2 、V3V3的鄰接點：的鄰接點： V4數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社在線性結構中，數(shù)據(jù)元素之間僅具有線性關系；在線性結構中，數(shù)據(jù)元素之間僅具有線性關系；在樹結構中，結點之間具有層次關系；在樹結構中，結點之間具有層次關系；在圖結構中，任意兩個頂點之間都可能有關系。在圖結構中，任意兩個頂點之間都可能有關系。 FECBAD線性結構線性結構ABCDEF樹結構樹結構V1V2V3V4V5圖結構圖結構不同結構中邏輯關系的對比

10、不同結構中邏輯關系的對比數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社在線性結構中，元素之間的關系為在線性結構中，元素之間的關系為前驅前驅和和后繼后繼；在樹結構中，結點之間的關系為在樹結構中，結點之間的關系為雙親雙親和和孩子孩子；在圖結構中，頂點之間的關系為在圖結構中，頂點之間的關系為鄰接鄰接。 FECBAD線性結構線性結構ABCDEF樹結構樹結構V1V2V3V4V5圖結構圖結構不同結構中邏輯關系的對比不同結構中邏輯關系的對比數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社無向完全圖無向完全圖：在無向圖中，如果任意兩個頂點之間：在無向圖中，如果任意兩個頂點之間都存在邊，都

11、存在邊，則稱該圖為無向完全圖。則稱該圖為無向完全圖。有向完全圖有向完全圖：在有向圖中，如果任意兩個頂點之間：在有向圖中，如果任意兩個頂點之間都存在方向相反的兩條弧，都存在方向相反的兩條弧，則稱該圖為有向完全圖則稱該圖為有向完全圖。 圖的基本術語圖的基本術語 V1V2V3V1V2V3V46.1 圖的邏輯結構圖的邏輯結構數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社含有含有n個頂點的無向完全圖有個頂點的無向完全圖有多少多少條邊？條邊？含有含有n個頂點的有向完全圖有個頂點的有向完全圖有多少多少條??？條?。?6.1 圖的邏輯結構圖的邏輯結構含有含有n個頂點的無向完全圖有個頂點的無向完全圖有

12、n(n-1)/2條邊。條邊。 含有含有n個頂點的有向完全圖有個頂點的有向完全圖有n(n-1)條邊。條邊。 V1V2V3V1V2V3V4數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社稀疏圖：稀疏圖：稱邊數(shù)很少的圖為稀疏圖；稱邊數(shù)很少的圖為稀疏圖；稠密圖：稠密圖：稱邊數(shù)很多的圖為稠密圖。稱邊數(shù)很多的圖為稠密圖。頂點的度：頂點的度：在無向圖中，頂點在無向圖中，頂點v的的度度是指依附于該頂是指依附于該頂點的邊數(shù)，通常記為點的邊數(shù)，通常記為TD (v)。6.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 頂點的入度：頂點的入度：在有向圖中，頂點在有向圖中，頂點v的的入度入度是指以該頂是

13、指以該頂點為弧頭的弧的數(shù)目，點為弧頭的弧的數(shù)目，記為記為ID (v)；頂點頂點的的出度：出度：在有向圖中，頂點在有向圖中，頂點v的的出度出度是指以該頂是指以該頂點為弧尾的弧的數(shù)目，記為點為弧尾的弧的數(shù)目，記為OD (v)。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社V1V2V3V4V56.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 在具有在具有n個頂點、個頂點、e條邊的無向圖條邊的無向圖G中，各頂點中，各頂點的度之和與邊數(shù)之和的關系？的度之和與邊數(shù)之和的關系？ = = =niievTD12)(數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社V1V2V3V46.

14、1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 在具有在具有n個頂點、個頂點、e條邊的有向圖條邊的有向圖G中，各頂點中，各頂點的入度之和與各頂點的出度之和的關系？與邊的入度之和與各頂點的出度之和的關系？與邊數(shù)之和的關系？數(shù)之和的關系？evODvIDiiii= = = = = =11)()(nn數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社權：權：是指對邊賦予的有意義的數(shù)值量。是指對邊賦予的有意義的數(shù)值量。網(wǎng)：網(wǎng)：邊上帶權的圖，也稱網(wǎng)圖。邊上帶權的圖，也稱網(wǎng)圖。6.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 V1V2V3V42785數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大

15、學出版社清華大學出版社路徑：路徑：在無向圖在無向圖G=(V, E)中，從頂點中，從頂點vp到頂點到頂點vq之間的之間的路徑路徑是一個頂點序列是一個頂點序列(vp=vi0,vi1,vi2, , vim=vq)，其中，其中，(vij-1,vij)E（1jm）。）。若若G是有向圖，則路徑也是有是有向圖，則路徑也是有方向的，頂點序列滿足方向的，頂點序列滿足E。6.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 V1V2V3V4V5v一般情況下，圖中的路徑不惟一。一般情況下，圖中的路徑不惟一。V1 到到V4的路徑：的路徑： V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4數(shù)據(jù)結構（數(shù)

16、據(jù)結構（C版）版）清華大學出版社清華大學出版社路徑長度：路徑長度：6.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 非帶權圖非帶權圖路徑路徑上邊的上邊的個數(shù)個數(shù)帶權圖帶權圖路徑上路徑上各邊的各邊的權之和權之和V1V2V3V4V5V1 V4：長度為：長度為1V1 V2 V3 V4 ：長度為：長度為3V1 V2 V5V3 V4 ：長度為：長度為4數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社路徑長度：路徑長度：6.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 非帶權圖非帶權圖路徑路徑上邊的上邊的個數(shù)個數(shù)帶權圖帶權圖路徑上路徑上各邊的各邊的權之和權之和V1 V4：長度為：

17、長度為8V1 V2 V3 V4 ：長度為：長度為7V1 V2 V5V3 V4 ：長度為：長度為15V1V2V3V4V5256328數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社回路（環(huán)）回路（環(huán)）：第一個頂點和最后一個頂點相同的路徑。：第一個頂點和最后一個頂點相同的路徑。簡單路徑：簡單路徑：序列中頂點不重復出現(xiàn)的路徑。序列中頂點不重復出現(xiàn)的路徑。簡單回路（簡單環(huán)）：簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點除了第一個頂點和最后一個頂點外，其余頂點不重復出現(xiàn)的回路。外，其余頂點不重復出現(xiàn)的回路。6.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 V1V2V3V4V5V1V

18、2V3V4數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社子圖：子圖：若圖若圖G=（V，E），），G=（V，E），），如果如果V V 且且E E ，則稱圖則稱圖G是是G的子圖。的子圖。6.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 V1V2V3V4V5V1V2V3V4V5V1V3V4數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社連通圖：連通圖：在無向圖中，如果從一個頂點在無向圖中，如果從一個頂點vi到另一個頂?shù)搅硪粋€頂點點vj(ij)有路徑，則稱頂點有路徑，則稱頂點vi和和vj是連通的。如果圖中是連通的。如果圖中任意兩個頂點都是連通的，則稱該圖是連通任意兩個頂點

19、都是連通的，則稱該圖是連通圖。圖。連通分量：連通分量：非連通圖的極大連通子圖稱為連通分量。非連通圖的極大連通子圖稱為連通分量。 6.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 如何求得一個非連通圖的連通分量如何求得一個非連通圖的連通分量? ?1.含有極大含有極大頂點頂點數(shù)；數(shù)；2. 依附于這些頂點的所有依附于這些頂點的所有邊邊。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社連通分量連通分量1 6.1 圖的邏輯結構圖的邏輯結構V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量連通分量2圖的基本術語圖的基本術語 v連通分量是對無向圖的一種劃分。連通分量是對無向圖

20、的一種劃分。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社強連通圖：強連通圖：在有向圖中，對圖中任意一對頂點在有向圖中，對圖中任意一對頂點vi和和vj (ij)，若從頂點若從頂點vi到頂點到頂點vj和從頂點和從頂點vj到頂點到頂點vi均有路徑均有路徑，則稱該有向圖是強連通圖。，則稱該有向圖是強連通圖。強連通分量：強連通分量：非強連通圖非強連通圖的極大強連通子圖。的極大強連通子圖。 6.1 圖的邏輯結構圖的邏輯結構圖的基本術語圖的基本術語 如何求得一個非連通圖的連通分量如何求得一個非連通圖的連通分量? ?數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.1 圖的邏輯結構圖

21、的邏輯結構圖的基本術語圖的基本術語 V1V2V3V4強連通分量強連通分量1 強連通分量強連通分量2V1V3V4V2數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社生成樹：生成樹：n個頂點的連通圖個頂點的連通圖G的生成樹是包含的生成樹是包含G中中全全部頂點部頂點的一個極小連通的一個極小連通子圖。子圖。 生成森林：生成森林：在非連通圖中，由每個連通分量都可以得在非連通圖中，由每個連通分量都可以得到一棵生成樹，這些連通分到一棵生成樹，這些連通分量的生成樹就組成了一個量的生成樹就組成了一個非連通圖的非連通圖的生成森林生成森林。 如何理解極小連通子圖如何理解極小連通子圖?6.1 圖的邏輯結構圖

22、的邏輯結構圖的基本術語圖的基本術語 多多構成回路構成回路少少不連通不連通含有含有n-1條邊條邊數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成樹生成樹生成森林生成森林6.1 圖的邏輯結構圖的邏輯結構數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社圖的抽象數(shù)據(jù)類型定義圖的抽象數(shù)據(jù)類型定義 ADT GraphData 頂點的有窮非空集合和邊的集合頂點的有窮非空集合和邊的集合Operation InitGraph 前置條件：圖不存在前置條件：圖不存在 輸入：無輸入：無 功能：圖的初

23、始化功能：圖的初始化 輸出：無輸出：無 后置條件：構造一個空的圖后置條件：構造一個空的圖6.1 圖的邏輯結構圖的邏輯結構數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社 DFSTraverse 前置條件：圖已存在前置條件：圖已存在 輸入：遍歷的起始頂點輸入：遍歷的起始頂點v 功能：從頂點功能：從頂點v出發(fā)深度優(yōu)先遍歷圖出發(fā)深度優(yōu)先遍歷圖 輸出：圖中頂點的一個線性排列輸出：圖中頂點的一個線性排列 后置條件：圖保持不變后置條件：圖保持不變 BFSTraverse 前置條件：圖已存在前置條件：圖已存在 輸入：遍歷的起始頂點輸入：遍歷的起始頂點v 功能：從頂點功能：從頂點v出發(fā)廣度優(yōu)先遍歷圖

24、出發(fā)廣度優(yōu)先遍歷圖 輸出：圖中頂點的一個線性排列輸出：圖中頂點的一個線性排列 后置條件：圖保持不變后置條件：圖保持不變6.1 圖的邏輯結構圖的邏輯結構數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社DestroyGraph 前置條件：圖已存在前置條件：圖已存在 輸入：無輸入：無 功能：銷毀圖功能：銷毀圖 輸出：無輸出：無 后置條件：釋放圖所占用的存儲空間后置條件：釋放圖所占用的存儲空間GetVex 前置條件：圖已存在前置條件：圖已存在 輸入：頂點輸入：頂點v 功能：在圖中查找頂點功能：在圖中查找頂點v的數(shù)據(jù)信息的數(shù)據(jù)信息 輸出：頂點輸出：頂點v的數(shù)據(jù)信息的數(shù)據(jù)信息 后置條件：圖保持不

25、變后置條件：圖保持不變endADT6.1 圖的邏輯結構圖的邏輯結構數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社圖的遍歷操作圖的遍歷操作圖的遍歷圖的遍歷是在從圖中是在從圖中某某一頂點出發(fā)，對圖中所一頂點出發(fā)，對圖中所有頂點有頂點訪問一次且僅訪問一次且僅訪問訪問一次。一次。 6.1 圖的邏輯結構圖的邏輯結構抽象操作，抽象操作，可以是對結點進行的各種可以是對結點進行的各種處理，這里處理，這里簡化為輸出結點的數(shù)據(jù)。簡化為輸出結點的數(shù)據(jù)。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社圖的遍歷操作要解決的關鍵問題圖的遍歷操作要解決的關鍵問題 在圖中，如何選取遍歷的起始頂點？在圖中

26、，如何選取遍歷的起始頂點？6.1 圖的邏輯結構圖的邏輯結構n在在線性表線性表中，數(shù)據(jù)元素在表中的編號就是元素在序列中，數(shù)據(jù)元素在表中的編號就是元素在序列中的位置，因而其編號是唯一的；中的位置，因而其編號是唯一的；n在在樹樹中，將結點按層序編號，由于樹具有層次性，因中，將結點按層序編號，由于樹具有層次性，因而其層序編號也是唯一的；而其層序編號也是唯一的；n在在圖圖中，任何兩個頂點之間都可能存在邊，頂點是沒中，任何兩個頂點之間都可能存在邊，頂點是沒有確定的先后次序的，所以，頂點的編號不唯一。有確定的先后次序的，所以，頂點的編號不唯一。為了定義操作的方便，將圖中的頂點按任意順序排列起為了定義操作的方

27、便，將圖中的頂點按任意順序排列起來，比如，按頂點的存儲順序。來，比如，按頂點的存儲順序。解決方案：從編號小的頂點開始解決方案：從編號小的頂點開始 。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社 從某個起點始可能到達不了所有其它頂點從某個起點始可能到達不了所有其它頂點，怎么辦？怎么辦？6.1 圖的邏輯結構圖的邏輯結構圖的遍歷操作要解決的關鍵問題圖的遍歷操作要解決的關鍵問題解決方案：多次調用從某頂點出發(fā)遍歷圖的算法。解決方案：多次調用從某頂點出發(fā)遍歷圖的算法。v下面僅討論從某頂點出發(fā)遍歷圖的算法。下面僅討論從某頂點出發(fā)遍歷圖的算法。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學

28、出版社 因圖中可能存在回路，某些頂點可能會被重復訪問，因圖中可能存在回路，某些頂點可能會被重復訪問，那么如何避免遍歷不會因回路而陷入死循環(huán)。那么如何避免遍歷不會因回路而陷入死循環(huán)。 在圖中，一個頂點可以和其它多個頂點相連，當這樣在圖中，一個頂點可以和其它多個頂點相連，當這樣的頂點的頂點訪問過后，如何選取下一個要訪問的頂點？訪問過后，如何選取下一個要訪問的頂點？ 6.1 圖的邏輯結構圖的邏輯結構圖的遍歷操作要解決的關鍵問題圖的遍歷操作要解決的關鍵問題解決方案：附設訪問標志數(shù)組解決方案：附設訪問標志數(shù)組visitedn 。解決方案：解決方案：深度深度優(yōu)先遍歷和優(yōu)先遍歷和廣度廣度優(yōu)先遍歷。優(yōu)先遍歷。

29、數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社約翰約翰霍普克洛夫特霍普克洛夫特19391939年生于西年生于西雅圖。雅圖。19611961年進入斯坦福大學研究年進入斯坦福大學研究生院深造，生院深造，19621962年獲碩士學位，年獲碩士學位，19641964年獲博士學位。畢業(yè)后先后在年獲博士學位。畢業(yè)后先后在普林斯頓大學、斯坦福大學等著名普林斯頓大學、斯坦福大學等著名學府工作，也曾任職于一些科學研學府工作，也曾任職于一些科學研究機構如究機構如 NSFNSF（美國科學基金會）美國科學基金會）和和 NRCNRC（美國國家研究院）。美國國家研究院）。羅伯特羅伯特陶爾揚陶爾揚1948194

30、8年年4 4月月3030日生日生于加利福尼亞州于加利福尼亞州 。19691969年本科畢年本科畢業(yè)，進入斯坦福大學研究生院，業(yè)，進入斯坦福大學研究生院，19721972年獲得博士學位。年獲得博士學位。1986年圖靈獎獲得者年圖靈獎獲得者6.1 圖的邏輯結構圖的邏輯結構數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社1. 深度優(yōu)先遍歷深度優(yōu)先遍歷 基本思想基本思想 ： 訪問頂點訪問頂點v； 從從v的未被訪問的鄰接點中選取一個頂點的未被訪問的鄰接點中選取一個頂點w，從從w出發(fā)進行深度優(yōu)先遍歷；出發(fā)進行深度優(yōu)先遍歷； 重復上述兩步，直至圖中所有和重復上述兩步，直至圖中所有和v有路徑相通有路

31、徑相通的頂點都被訪問到。的頂點都被訪問到。 6.1 圖的邏輯結構圖的邏輯結構數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社深一層遞歸深一層遞歸遞歸返回遞歸返回深度優(yōu)先遍歷序列深度優(yōu)先遍歷序列?入棧序列入棧序列?出棧序列出棧序列?6.1 圖的邏輯結構圖的邏輯結構V1V3V2V4V5V6V7V8 V1遍歷序列：遍歷序列：V1V2 V2V4 V4V5 V5數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社深一層遞歸深一層遞歸遞歸返回遞歸返回深度優(yōu)先遍歷序列深度優(yōu)先遍歷序列?入棧序列入棧序列?出棧序列出棧序列?6.1 圖的邏輯結構圖的邏輯結構V1V3V2V4V5V6V7V8 V1遍

32、歷序列：遍歷序列：V1V2 V2V4 V4V5V8 V8數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社深一層遞歸深一層遞歸遞歸返回遞歸返回深度優(yōu)先遍歷序列深度優(yōu)先遍歷序列?入棧序列入棧序列?出棧序列出棧序列?6.1 圖的邏輯結構圖的邏輯結構V1V3V2V4V5V6V7V8 V1遍歷序列：遍歷序列：V1V2 V2V4 V4V5V8數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社深一層遞歸深一層遞歸遞歸返回遞歸返回深度優(yōu)先遍歷序列深度優(yōu)先遍歷序列?入棧序列入棧序列?出棧序列出棧序列?6.1 圖的邏輯結構圖的邏輯結構V1V3V2V4V5V6V7V8 V1遍歷序列：遍歷序列：V1

33、 V7V2V4V5V8V3 V3V6 V6V7數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社2. 廣度優(yōu)先遍歷廣度優(yōu)先遍歷 基本思想基本思想： 訪問頂點訪問頂點v； 依次依次訪問訪問v的各個未被訪問的鄰接點的各個未被訪問的鄰接點v1, v2, , vk； 分別從分別從v1，v2，vk出發(fā)依次訪問它們未被訪問出發(fā)依次訪問它們未被訪問的鄰接點，并使的鄰接點，并使“先先被訪問頂點的鄰接點被訪問頂點的鄰接點”先先于于“后被訪問頂點的鄰接點后被訪問頂點的鄰接點”被訪問。直至圖中所有與被訪問。直至圖中所有與頂點頂點v有路徑相通的頂點都被訪問到。有路徑相通的頂點都被訪問到。6.1 圖的邏輯結構圖

34、的邏輯結構數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社廣度優(yōu)先遍歷序列廣度優(yōu)先遍歷序列?入隊序列入隊序列?出隊序列出隊序列? 6.1 圖的邏輯結構圖的邏輯結構V1V3V2V4V5V6V7V8遍歷序列：遍歷序列：V1V1數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社廣度優(yōu)先遍歷序列廣度優(yōu)先遍歷序列?入隊序列入隊序列?出隊序列出隊序列? 6.1 圖的邏輯結構圖的邏輯結構V1V3V2V4V5V6V7V8遍歷序列：遍歷序列：V1V2V2V3V3數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社廣度優(yōu)先遍歷序列廣度優(yōu)先遍歷序列?入隊序列入隊序列?出隊序列出隊序列? 6.

35、1 圖的邏輯結構圖的邏輯結構V1V3V2V4V5V6V7V8遍歷序列：遍歷序列：V1V2V3V3V4V4V5V5數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社廣度優(yōu)先遍歷序列廣度優(yōu)先遍歷序列?入隊序列入隊序列?出隊序列出隊序列? 6.1 圖的邏輯結構圖的邏輯結構V1V3V2V4V5V6V7V8遍歷序列：遍歷序列：V1V2V3V4V4V5V5V6V6V7V7數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社廣度優(yōu)先遍歷序列廣度優(yōu)先遍歷序列?入隊序列入隊序列?出隊序列出隊序列? 6.1 圖的邏輯結構圖的邏輯結構V1V3V2V4V5V6V7V8遍歷序列：遍歷序列：V1V2V3V4

36、V5V5V6V6V7V7V8V8數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)是否可以采用順序存儲結構存儲圖是否可以采用順序存儲結構存儲圖?圖的特點：頂點之間的關系是圖的特點：頂點之間的關系是m: :n，即，即任何兩任何兩個頂點之間都可能存在關系（邊），無法通過個頂點之間都可能存在關系（邊），無法通過存儲位置表示這種任意的邏輯關系，所以，圖存儲位置表示這種任意的邏輯關系，所以，圖無法采用順序存儲結構。無法采用順序存儲結構。如何存儲圖如何存儲圖?考慮圖的定義，圖是由頂點和邊組成的，分別考慮圖的定義，圖是由頂點和邊組成的，分別考慮如何存儲頂點

37、、如何存儲邊?？紤]如何存儲頂點、如何存儲邊。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社鄰接矩陣（數(shù)組表示法）鄰接矩陣（數(shù)組表示法）基本思想：用一個一維數(shù)組存儲圖中基本思想：用一個一維數(shù)組存儲圖中頂點頂點的信息，的信息，用一個二維數(shù)組（用一個二維數(shù)組（稱為鄰接矩陣稱為鄰接矩陣）存儲圖中各頂點）存儲圖中各頂點之間的之間的鄰接鄰接關系。關系。6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)假設圖假設圖G(V，E)有有n個頂點，則鄰接矩陣是一個個頂點，則鄰接矩陣是一個nn的方陣，定義為：的方陣，定義為：arcij1 若若(vi, vj)E（或（或E）0 其它其它數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版

38、）清華大學出版社清華大學出版社無向圖的鄰接矩陣的特點？無向圖的鄰接矩陣的特點？無向圖的鄰接矩陣無向圖的鄰接矩陣6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(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ù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社如何求頂點如何求頂點i的度？的度？無向圖的鄰接矩陣無向圖的鄰接矩陣6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)V1V3V4V2V1 V2 V3 V4vertex=0

39、 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ù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社如何判斷頂點如何判斷頂點 i 和和 j 之間是否存在邊？之間是否存在邊？無向圖的鄰接矩陣無向圖的鄰接矩陣6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(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測試鄰接矩陣中相應位置的元素測試鄰接矩陣

40、中相應位置的元素arcij是否為是否為1。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社如何求頂點如何求頂點 i 的所有鄰接點？的所有鄰接點？無向圖的鄰接矩陣無向圖的鄰接矩陣6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(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ù)組中第將數(shù)組中第 i 行元素掃描一遍，若行元素掃描一遍，若arcij為為1，則，則頂點頂點 j 為頂點為頂點 i 的鄰接點。的鄰接點。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.2 圖的

41、存儲結構及實現(xiàn)圖的存儲結構及實現(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ù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)有向圖的鄰接矩陣有向圖的鄰接矩陣V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V

42、2 V3 V4V1V2V3V4如何求頂點如何求頂點 i 的出度？的出度？鄰接矩陣的第鄰接矩陣的第 i 行元素之和。行元素之和。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(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ù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.2 圖的存儲結構及實

43、現(xiàn)圖的存儲結構及實現(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ù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社網(wǎng)圖的鄰接矩陣網(wǎng)圖的鄰接矩陣6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)網(wǎng)圖的鄰接矩陣可定義為：網(wǎng)圖的鄰接矩陣可定義為： arcij wij 若若(vi, vj)E（或（

44、或E）0 若若i=j 其他其他V1V2V3V42785 0 2 5 0 0 8 7 0 arc=數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社鄰接矩陣存儲鄰接矩陣存儲無向圖無向圖的類的類const int MaxSize=10; template class Mgraph public: MGraph( (T a , int n, int e ) ); MGraph( )( ) void DFSTraverse( (int v) ); void BFSTraverse( (int v) ); private: T vertexMaxSize; int arcMaxSizeMaxSi

45、ze; int vertexNum, arcNum; ;6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社鄰接矩陣中圖的基本操作鄰接矩陣中圖的基本操作構造函數(shù)構造函數(shù) 1. 確定圖的頂點個數(shù)和邊的個數(shù)；確定圖的頂點個數(shù)和邊的個數(shù)；2. 輸入頂點信息存儲在一維數(shù)組輸入頂點信息存儲在一維數(shù)組vertex中；中；3. 初始化鄰接矩陣；初始化鄰接矩陣；4. 依次輸入每條邊存儲在鄰接矩陣依次輸入每條邊存儲在鄰接矩陣arc中；中； 4.1 輸入邊依附的兩個頂點的序號輸入邊依附的兩個頂點的序號i, j； 4.2 將鄰接矩陣的第將鄰接矩陣的第i行第行第j列的

46、元素值置為列的元素值置為1； 4.3 將鄰接矩陣的第將鄰接矩陣的第j行第行第i列的元素值置為列的元素值置為1；6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社template MGraph:MGraph(T a , int n, int e) vertexNum=n; arcNum=e; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) /初始化鄰接矩陣初始化鄰接矩陣 for (j=0; jvertexNum; j+) arcij=0; for (k=0; kij

47、; /邊依附的兩個頂點的序號邊依附的兩個頂點的序號 arcij=1; arcji=1; /置有邊標志置有邊標志 6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)鄰接矩陣中圖的基本操作鄰接矩陣中圖的基本操作構造函數(shù)構造函數(shù) 數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社鄰接矩陣中圖的基本操作鄰接矩陣中圖的基本操作深度優(yōu)先遍歷深度優(yōu)先遍歷template void MGraph:DFSTraverse( (int v) ) coutvertexv; visited v=1; for ( (j=0; jvertexNum; j+) ) if ( (arcvj=1 & visitedj=0)

48、) DFSTraverse( ( j ) );6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社鄰接矩陣中圖的基本操作鄰接矩陣中圖的基本操作廣度優(yōu)先遍歷廣度優(yōu)先遍歷template void MGraph:BFSTraverse( (int v) ) front=rear=- -1; /假設采用順序隊列且不會發(fā)生溢出假設采用順序隊列且不會發(fā)生溢出 coutvertexv; visitedv=1; Q+rear=v; while ( (front!=rear) ) v=Q+front; for ( (j=0; jvertexNum; j+) )

49、 if ( (arcvj=1 & visitedj=0 ) ) coutvertexj; visitedj=1; Q+rear=j; 6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社鄰接表鄰接表鄰接表存儲的基本思想：對于圖的每個頂點鄰接表存儲的基本思想：對于圖的每個頂點vi，將所將所有鄰接于有鄰接于vi的頂點鏈成一個單鏈表，稱為頂點的頂點鏈成一個單鏈表，稱為頂點vi的的邊邊表表（對于有向圖則稱為出邊表），所有邊表的頭指（對于有向圖則稱為出邊表），所有邊表的頭指針和存儲頂點信息的一維針和存儲頂點信息的一維數(shù)組構成了數(shù)組構成了頂點表頂點表。 6

50、.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)圖的鄰接矩陣存儲結構的空間復雜度？圖的鄰接矩陣存儲結構的空間復雜度？如果為稀疏圖則會出現(xiàn)什么現(xiàn)象？如果為稀疏圖則會出現(xiàn)什么現(xiàn)象？ 假設圖假設圖G有有n個頂點個頂點e條邊，則存儲該圖需要條邊，則存儲該圖需要O(n2) 。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社鄰接表有兩種結點結構：頂點表結點和邊表結點鄰接表有兩種結點結構：頂點表結點和邊表結點。vertexfirstedge adjvex next 頂點表頂點表 邊邊 表表 vertex：數(shù)據(jù)域，存放頂點信息。數(shù)據(jù)域，存放頂點信息。 firstedge：指針域，指向邊表中第一個結點。指針

51、域，指向邊表中第一個結點。 adjvex：鄰接點域，邊的終點在頂點表中的下標。鄰接點域，邊的終點在頂點表中的下標。next：指針域，指向邊表中的下一個結點。指針域，指向邊表中的下一個結點。 6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社struct ArcNode int adjvex; ArcNode *next;template struct VertexNode T vertex; ArcNode *firstedge;定義鄰接表的結點定義鄰接表的結點 6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)vertexfirstedge ad

52、jvex next數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社10323101 V1 V2 V3 V40123vertex firstedge6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)V1V3V4V2無向圖的鄰接表無向圖的鄰接表邊表中的結點表示什么？邊表中的結點表示什么？每個結點對應圖中的一條邊，每個結點對應圖中的一條邊，鄰接表的空間復雜度為鄰接表的空間復雜度為O(n+e)。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社10323101 V1 V2 V3 V40123vertex firstedge6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)V1V3V4V2無向圖的

53、鄰接表無向圖的鄰接表如何求頂點如何求頂點 i 的度？的度？頂點頂點i的邊表中結點的個數(shù)。的邊表中結點的個數(shù)。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社如何判斷頂點如何判斷頂點 i 和頂點和頂點 j之間是否存在邊之間是否存在邊?測試頂點測試頂點 i 的邊表中是否存的邊表中是否存在終點為在終點為 j 的結點。的結點。6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)10323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2無向圖的鄰接表無向圖的鄰接表數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)

54、有向圖的鄰接表有向圖的鄰接表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求頂點如何求頂點 i 的出度？的出度？頂點頂點 i 的出邊表中結點的個數(shù)。的出邊表中結點的個數(shù)。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)有向圖的鄰接表有向圖的鄰接表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求頂點如何求頂點 i 的入度？的入度？各頂點的出邊表中以頂點各頂點的出邊表中以頂點 i 為為終點的結點個數(shù)。終點的結點個數(shù)。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學

55、出版社清華大學出版社6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)有向圖的鄰接表有向圖的鄰接表V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求頂點如何求頂點 i 的所有鄰接點？的所有鄰接點？遍歷頂點遍歷頂點 i 的邊表，該邊表中的的邊表，該邊表中的所有終點都是頂點所有終點都是頂點 i 的鄰接點。的鄰接點。數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)網(wǎng)圖的鄰接表網(wǎng)圖的鄰接表V1V2V3V427852 1 V1 V2 V3 V40123vertex firstedge5 28 37 0數(shù)據(jù)結構（數(shù)

56、據(jù)結構（C版）版）清華大學出版社清華大學出版社鄰接表存儲鄰接表存儲有向圖有向圖的的類類const int MaxSize=10; /圖的最大頂點數(shù)圖的最大頂點數(shù)template class ALGraph public: ALGraph( (T a , int n, int e) ); ALGraph; void DFSTraverse( (int v) ); void BFSTraverse( (int v) ); private: VertexNode adjlistMaxSize; int vertexNum, arcNum; ;6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)數(shù)據(jù)結構（數(shù)據(jù)

57、結構（C版）版）清華大學出版社清華大學出版社鄰接表中圖的基本操作鄰接表中圖的基本操作構造函數(shù)構造函數(shù) 1. 確定圖的頂點個數(shù)和邊的個數(shù)；確定圖的頂點個數(shù)和邊的個數(shù)；2. 輸入頂點信息，初始化該頂點的邊表；輸入頂點信息，初始化該頂點的邊表；3. 依次輸入邊的信息并存儲在邊表中；依次輸入邊的信息并存儲在邊表中； 3.1 輸入邊所依附的兩個頂點的序號輸入邊所依附的兩個頂點的序號i和和j； 3.2 生成鄰接點序號為生成鄰接點序號為j的邊表結點的邊表結點s； 3.3 將結點將結點s插入到第插入到第i個邊表的頭部；個邊表的頭部；6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華

58、大學出版社清華大學出版社template ALGraph:ALGraph(T a , int n, int e) vertexNum=n; arcNum=e; for (i=0; ivertexNum; i+) /輸入頂點信息，初始化邊表輸入頂點信息，初始化邊表 adjlisti.vertex=ai; adjlisti.firstedge=NULL; 6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)鄰接表中圖的基本操作鄰接表中圖的基本操作構造函數(shù)構造函數(shù) 數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社s for (k=0; kij; s=new ArcNode; s-adjvex=j;

59、 s-next=adjlisti.firstedge; adjlisti.firstedge=s; 6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)12 V1 V2 V3 V40123數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社鄰接表中圖的基本操作鄰接表中圖的基本操作深度優(yōu)先遍歷深度優(yōu)先遍歷template void ALGraph:DFSTraverse( (int v) ) cout-adjvex; if ( (visitedj=0) ) DFSTraverse( (j) ); p=p-next; 6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學

60、出版社清華大學出版社鄰接表中圖的基本操作鄰接表中圖的基本操作廣度優(yōu)先遍歷廣度優(yōu)先遍歷template void ALGraph:BFSTraverse( (int v) ) front=rear=- -1; cout-adjvex; if ( (visitedj=0) ) cout-next; 6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)數(shù)據(jù)結構（數(shù)據(jù)結構（C版）版）清華大學出版社清華大學出版社十字鏈表十字鏈表 鄰接表鄰接表6.2 圖的存儲結構及實現(xiàn)圖的存儲結構及實現(xiàn)逆鄰接表逆鄰接表將鄰接表與逆鄰接表合二為一將鄰接表與逆鄰接表合二為一?為什么要合并？為什么要合并？V1V2V3V412 3 0v