數(shù)據(jù)結(jié)構(gòu)第6本章的主要內(nèi)容是

1、第六章 圖本章的主要內(nèi)容是:圖的邏輯結(jié)構(gòu)圖的存儲結(jié)構(gòu)及實(shí)現(xiàn)圖的連通性最小生成樹最短路徑AOV網(wǎng)與拓?fù)渑判駻OE網(wǎng)與關(guān)鍵路徑 歐拉1707年出生在瑞士的巴塞爾城，19歲開始發(fā)表論文，直到76歲。幾乎每一個數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級數(shù)論的歐拉常數(shù)，變分學(xué)的歐拉方程，復(fù)變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計他那不倦的一生，共寫下了886本書籍和論文，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學(xué)占28%，天文學(xué)占11%，彈道學(xué)、航海學(xué)、建筑學(xué)等占3%。 1733年，年僅26

2、歲的歐拉擔(dān)任了彼得堡科學(xué)院數(shù)學(xué)教授。1741年到柏林擔(dān)任科學(xué)院物理數(shù)學(xué)所所長，直到1766年，重回彼得堡，沒有多久，完全失明。歐拉在數(shù)學(xué)上的建樹很多，對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。圖論歐拉能否從某個地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點(diǎn)？哥尼斯堡七橋問題 CADB七橋問題的圖模型哥尼斯堡七橋問題 歐拉回路的判定規(guī)則：1.如果通奇數(shù)橋的地方多于兩個，則不存在歐拉回路；2.如果只有兩個地方通奇數(shù)橋，可以從這兩個地方之一出發(fā)，找到歐拉回路；3.如果沒有一個地方是通奇數(shù)橋的，則無論從哪里出發(fā)，都能找到歐拉回路。圖的定義6.1 圖的邏輯結(jié)構(gòu)圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合

3、組成，通常表示為： G=(V，E)其中：G表示一個圖，V是圖G中頂點(diǎn)（數(shù)據(jù)元素）的集合，E是圖G中頂點(diǎn)之間邊的集合。 在線性表中，元素個數(shù)可以為零，稱為空表；在樹中，結(jié)點(diǎn)個數(shù)可以為零，稱為空樹；在圖中，頂點(diǎn)個數(shù)不能為零，但可以沒有邊。6.1 圖的邏輯結(jié)構(gòu)如果圖的任意兩個頂點(diǎn)之間的邊都是無向邊，則稱該圖為無向圖。若頂點(diǎn)vi和vj之間的邊沒有方向，則稱這條邊為無向邊，表示為(vi,vj)。若從頂點(diǎn)vi到vj的邊有方向，則稱這條邊為有向邊，表示為。 如果圖的任意兩個頂點(diǎn)之間的邊都是有向邊，則稱該圖為有向圖。V1V2V3V4V5V1V2V3V46.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 簡單圖：在圖中，若不存在

4、頂點(diǎn)到其自身的邊，且同一條邊不重復(fù)出現(xiàn)。V3V4V5V1V2V3V4V5V1V2非簡單圖 非簡單圖 簡單圖V1V2V3V4V5 數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖6.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 鄰接、依附無向圖中，對于任意兩個頂點(diǎn)vi和頂點(diǎn)vj，若存在邊(vi，vj)，則稱頂點(diǎn)vi和頂點(diǎn)vj互為鄰接點(diǎn)，同時稱邊(vi，vj)依附于頂點(diǎn)vi和頂點(diǎn)vj。V1V2V3V4V5V1的鄰接點(diǎn)： V2 、V4V2的鄰接點(diǎn)： V1 、V3 、V56.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 鄰接、依附有向圖中，對于任意兩個頂點(diǎn)vi和頂點(diǎn)vj，若存在弧，則稱頂點(diǎn)vi（弧尾）鄰接到頂點(diǎn)vj （弧頭） ，頂點(diǎn)vj鄰接自頂點(diǎn)vi，同

5、時稱弧依附于頂點(diǎn)vi和頂點(diǎn)vj 。 V1V2V3V4V1的鄰接點(diǎn)： V2 、V3V3的鄰接點(diǎn)： V4在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線性關(guān)系；1:1在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間具有層次關(guān)系；1:n在圖結(jié)構(gòu)中，任意兩個頂點(diǎn)之間都可能有關(guān)系。m:n FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V1V2V3V4V5圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對比在線性結(jié)構(gòu)中，元素之間的關(guān)系為前驅(qū)和后繼；在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系為雙親和孩子；在圖結(jié)構(gòu)中，頂點(diǎn)之間的關(guān)系為鄰接。 FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V1V2V3V4V5圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對比無向完全圖：在無向圖中，如果任意兩個頂點(diǎn)之間都存在邊，則稱該圖為無向

6、完全圖有向完全圖：在有向圖中，如果任意兩個頂點(diǎn)之間都存在方向相反的兩條弧，則稱該圖為有向完全圖圖的基本術(shù)語 V1V2V3V1V2V3V46.1 圖的邏輯結(jié)構(gòu)含有n個頂點(diǎn)的無向完全圖有多少條邊？含有n個頂點(diǎn)的有向完全圖有多少條??？ 6.1 圖的邏輯結(jié)構(gòu)含有n個頂點(diǎn)的無向完全圖有n(n-1)/2條邊。 含有n個頂點(diǎn)的有向完全圖有n(n-1)條邊。 V1V2V3V1V2V3V4稀疏圖：稱邊數(shù)很少的圖為稀疏圖； enlogn稠密圖：稱邊數(shù)很多的圖為稠密圖。頂點(diǎn)的度：在無向圖中，頂點(diǎn)v的度是指依附于該頂點(diǎn)的邊數(shù)，通常記為TD (v)。6.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 頂點(diǎn)的入度：在有向圖中，頂點(diǎn)v的入度

7、是指以該頂點(diǎn)為弧頭的弧的數(shù)目，記為ID (v)；頂點(diǎn)的出度：在有向圖中，頂點(diǎn)v的出度是指以該頂點(diǎn)為弧尾的弧的數(shù)目，記為OD (v)。邊數(shù)點(diǎn)數(shù)w1w2w3V1V2V3V4v1,v2,v3,v4的度是多少？w1,w2,w3的入度和出度是多少V1V2V3V4V56.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 在具有n個頂點(diǎn)、e條邊的無向圖G中，各頂點(diǎn)的度之和與邊數(shù)之和的關(guān)系？=niievTD12)(V1V2V3V46.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 在具有n個頂點(diǎn)、e條邊的有向圖G中，各頂點(diǎn)的入度之和與各頂點(diǎn)的出度之和的關(guān)系？與邊數(shù)之和的關(guān)系？evODvIDiiii=11)()(nn權(quán)：是指對邊賦予的有意義的數(shù)值量

8、。網(wǎng)：邊上帶權(quán)的圖，也稱網(wǎng)圖,簡稱網(wǎng)。6.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 V1V2V3V42785路徑：在無向圖G=(V, E)中，從頂點(diǎn)vp到頂點(diǎn)vq之間的路徑是一個頂點(diǎn)序列(vp=vi0,vi1,vi2, , vim=vq)，其中，(vij-1,vij)E（1jm）。若G是有向圖，則路徑也是有方向的，頂點(diǎn)序列滿足E。6.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 V1V2V3V4V5一般情況下，圖中的路徑不惟一。V1 到V4的路徑： V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4路徑長度：6.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 非帶權(quán)圖路徑上邊的個數(shù)帶權(quán)圖路徑上各邊的權(quán)之和V1V2V3V4V5V

9、1 V4：長度為1V1 V2 V3 V4 ：長度為3V1 V2 V5V3 V4 ：長度為4路徑長度：6.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 非帶權(quán)圖路徑上邊的個數(shù)帶權(quán)圖路徑上各邊的權(quán)之和V1 V4：長度為8V1 V2 V3 V4 ：長度為7V1 V2 V5V3 V4 ：長度為15V1V2V3V4V5256328回路（環(huán)）：第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑。簡單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡單回路（簡單環(huán)）：除了第一個頂點(diǎn)和最后一個頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路。6.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 V1V2V3V4V5V1V2V3V4子圖：若圖G=（V，E），G=（V，E），如果VV 且E E

10、 ，則稱圖G是G的子圖。6.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 V1V2V3V4V5V1V2V3V4V5V1V3V4連通圖：在無向圖中，如果從一個頂點(diǎn)vi到另一個頂點(diǎn)vj(ij)有路徑，則稱頂點(diǎn)vi和vj是連通的。如果圖中任意兩個頂點(diǎn)都是連通的，則稱該圖是連通圖。連通分量：非連通圖的極大連通子圖稱為連通分量。 6.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 如何求得一個非連通圖的連通分量?1.含有極大頂點(diǎn)數(shù)；2. 依附于這些頂點(diǎn)的所有邊。連通分量1 6.1 圖的邏輯結(jié)構(gòu)V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量2圖的基本術(shù)語 連通分量是對無向圖的一種劃分強(qiáng)連通圖：在有向圖中，對圖中任意一對頂

11、點(diǎn)vi和vj (ij)，若從頂點(diǎn)vi到頂點(diǎn)vj和從頂點(diǎn)vj到頂點(diǎn)vi均有路徑，則稱該有向圖是強(qiáng)連通圖。強(qiáng)連通分量：非強(qiáng)連通圖的極大強(qiáng)連通子圖。 6.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 如何求得一個非連通圖的連通分量?6.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 V1V2V3V4強(qiáng)連通分量1 強(qiáng)連通分量2V1V3V4V2生成樹：n個頂點(diǎn)的連通圖G的生成樹是包含G中全部頂點(diǎn)的一個極小連通子圖。 生成森林：在非連通圖中，由每個連通分量都可以得到一棵生成樹，這些連通分量的生成樹就組成了一個非連通圖的生成森林。 如何理解極小連通子圖?6.1 圖的邏輯結(jié)構(gòu)圖的基本術(shù)語 多構(gòu)成回路少不連通含有n-1條邊V1V2V3V4V5V

12、6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成樹生成森林6.1 圖的邏輯結(jié)構(gòu)圖的抽象數(shù)據(jù)類型定義 ADT GraphData 頂點(diǎn)的有窮非空集合和邊的集合 Operation InitGraph 前置條件：圖不存在 輸入：無 功能：圖的初始化 輸出：無 后置條件：構(gòu)造一個空的圖6.1 圖的邏輯結(jié)構(gòu) DFSTraverse 前置條件：圖已存在 輸入：遍歷的起始頂點(diǎn)v 功能：從頂點(diǎn)v出發(fā)深度優(yōu)先遍歷圖 輸出：圖中頂點(diǎn)的一個線性排列 后置條件：圖保持不變 BFSTraverse 前置條件：圖已存在 輸入：遍歷的起始頂點(diǎn)v 功能：從頂點(diǎn)v出發(fā)廣度優(yōu)先遍歷圖 輸出：圖中頂

13、點(diǎn)的一個線性排列 后置條件：圖保持不變6.1 圖的邏輯結(jié)構(gòu)DestroyGraph 前置條件：圖已存在 輸入：無 功能：銷毀圖 輸出：無 后置條件：釋放圖所占用的存儲空間GetVex 前置條件：圖已存在 輸入：頂點(diǎn)v 功能：在圖中查找頂點(diǎn)v的數(shù)據(jù)信息 輸出：頂點(diǎn)v的數(shù)據(jù)信息 后置條件：圖保持不變ADT Graph6.1 圖的邏輯結(jié)構(gòu)圖的遍歷操作圖的遍歷是從圖中某一頂點(diǎn)出發(fā)，對圖中所有頂點(diǎn)訪問一次且僅訪問一次。 6.1 圖的邏輯結(jié)構(gòu)抽象操作，可以是對結(jié)點(diǎn)進(jìn)行的各種處理，這里簡化為輸出結(jié)點(diǎn)的數(shù)據(jù)。圖的遍歷操作要解決的關(guān)鍵問題 在圖中，如何選取遍歷的起始頂點(diǎn)？6.1 圖的邏輯結(jié)構(gòu)在線性表中，數(shù)據(jù)元素

14、在表中的編號就是元素在序列中的位置，因而其編號是唯一的；在樹中，將結(jié)點(diǎn)按層序編號，由于樹具有層次性，因而其層序編號也是唯一的；在圖中，任何兩個頂點(diǎn)之間都可能存在邊，頂點(diǎn)是沒有確定的先后次序的，所以，頂點(diǎn)的編號不唯一。為了定義操作的方便，將圖中的頂點(diǎn)按任意順序排列起來，比如，按頂點(diǎn)的存儲順序。解決方案：從編號小的頂點(diǎn)開始 。 從某個點(diǎn)起始可能到達(dá)不了所有其它頂點(diǎn)，怎么辦？6.1 圖的邏輯結(jié)構(gòu)圖的遍歷操作要解決的關(guān)鍵問題解決方案：多次調(diào)用從某頂點(diǎn)出發(fā)遍歷圖的算法。下面僅討論從某頂點(diǎn)出發(fā)遍歷圖的算法。 因圖中可能存在回路，某些頂點(diǎn)可能會被重復(fù)訪問，那么如何避免遍歷不會因回路而陷入死循環(huán)。 在圖中，一

15、個頂點(diǎn)可以和其它多個頂點(diǎn)相連，當(dāng)這樣的頂點(diǎn)訪問過后，如何選取下一個要訪問的頂點(diǎn)？ 6.1 圖的邏輯結(jié)構(gòu)圖的遍歷操作要解決的關(guān)鍵問題解決方案：附設(shè)訪問標(biāo)志數(shù)組visitedn 。解決方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。約翰霍普克洛夫特1939年生于西雅圖。1961年進(jìn)入斯坦福大學(xué)研究生院深造，1962年獲碩士學(xué)位，1964年獲博士學(xué)位。畢業(yè)后先后在普林斯頓大學(xué)、斯坦福大學(xué)等著名學(xué)府工作，也曾任職于一些科學(xué)研究機(jī)構(gòu)如 NSF（美國科學(xué)基金會）和 NRC（美國國家研究院）。羅伯特陶爾揚(yáng)1948年4月30日生于加利福尼亞州 。1969年本科畢業(yè)，進(jìn)入斯坦福大學(xué)研究生院，1972年獲得博士學(xué)位。1986年

16、圖靈獎獲得者6.1 圖的邏輯結(jié)構(gòu)1. 深度優(yōu)先遍歷 基本思想 ： 訪問頂點(diǎn)v； 從v的未被訪問的鄰接點(diǎn)中選取一個頂點(diǎn)w，從w出發(fā)進(jìn)行深度優(yōu)先遍歷； 重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。 6.1 圖的邏輯結(jié)構(gòu)深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1 圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8 V1遍歷序列：V1V2 V2V4 V4V5 V5深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1 圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8 V1遍歷序列：V1V2 V2V4 V4V5V8 V8深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序

17、列?6.1 圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8 V1遍歷序列：V1V2 V2V4 V4V5V8深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1 圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8 V1遍歷序列：V1 V7V2V4V5V8V3 V3V6 V6V72. 廣度優(yōu)先遍歷 基本思想： 訪問頂點(diǎn)v； 依次訪問v的各個未被訪問的鄰接點(diǎn)v1, v2, , vk； 分別從v1，v2，vk出發(fā)依次訪問它們未被訪問的鄰接點(diǎn)，并使“先被訪問頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問頂點(diǎn)的鄰接點(diǎn)”被訪問。直至圖中所有與頂點(diǎn)v有路徑相通的頂點(diǎn)都被訪問到。6.1 圖的邏輯結(jié)構(gòu)廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列? 6.1 圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8遍歷序列：V1V1廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列? 6.1 圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V3廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列? 6.1 圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V5廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列? 6.1 圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V7V8V5V6V7V