數(shù)據(jù)結(jié)構(gòu) 第6章-圖(g)

第六章圖本章的主要內(nèi)容是:圖的邏輯結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)圖的連通性最小生成樹最短路徑AOV網(wǎng)與拓?fù)渑判駻OE網(wǎng)與關(guān)鍵路徑歐拉1707年出生在瑞士的巴塞爾城，19歲開始發(fā)表論文，直到76歲。幾乎每一個(gè)數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級(jí)數(shù)論的歐拉常數(shù)，變分學(xué)的歐拉方程，復(fù)變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計(jì)他那不倦的一生，共寫下了886本書籍和論文，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學(xué)占28%，天文學(xué)占11%，彈道學(xué)、航海學(xué)、建筑學(xué)等占3%。1733年，年僅26歲的歐拉擔(dān)任了彼得堡科學(xué)院數(shù)學(xué)教授。1741年到柏林擔(dān)任科學(xué)院物理數(shù)學(xué)所所長，直到1766年，重回彼得堡，沒有多久，完全失明。歐拉在數(shù)學(xué)上的建樹很多，對(duì)著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。圖論——?dú)W拉18世紀(jì)時(shí)，歐洲有一個(gè)風(fēng)景秀麗的小城哥尼斯堡，那里的普萊格爾河上有七座橋。將河中的兩個(gè)島和河岸連結(jié)，城中的居民經(jīng)常沿河過橋散步，于是他們提出了一個(gè)問題：一個(gè)人怎樣才能一次走遍七座橋，每座橋只走過一次，最后回到出發(fā)點(diǎn)？大家都試圖找出問題的答案，但是誰也解決不了這個(gè)問題…………

這就是哥尼斯堡七橋問題，一個(gè)著名的圖論問題。

哥尼斯堡七橋問題哥尼斯堡七橋問題

1727年在歐拉20歲的時(shí)候，被俄國請(qǐng)去在圣彼得堡（原列寧格勒）的科學(xué)院做研究。他的德國朋友告訴了他這個(gè)曾經(jīng)令許多人困惑的問題。

歐拉并沒有馬上跑到哥尼斯堡去走走或看看。而是他先把這個(gè)難題化成了這樣的問題來處理：把兩岸和小島縮成一點(diǎn)，橋化為邊，于是“七橋問題”就等價(jià)于下圖中所畫圖形的一筆畫問題了，這個(gè)圖如果能夠一筆畫完的話，對(duì)應(yīng)的“七橋問題”也就解決了。哥尼斯堡七橋問題

經(jīng)過研究，歐拉發(fā)現(xiàn)了一筆畫的規(guī)律。他認(rèn)為，能一筆畫的圖形必須是連通圖。連通圖就是指一個(gè)圖形各部分總是有邊相連的，這道題中的圖就是連通圖。

但是，不是所有的連通圖都可以一筆畫完的。能否一筆畫完是由圖的奇、偶點(diǎn)的數(shù)目來決定的。那么什么叫奇、偶點(diǎn)呢？與奇數(shù)（單數(shù)）條邊相連的點(diǎn)叫做奇點(diǎn)；與偶數(shù)（雙數(shù)）條邊相連的點(diǎn)叫做偶點(diǎn)。如右圖中的①、④為奇點(diǎn)，②、③為偶點(diǎn)。哥尼斯堡七橋問題

1．凡是由偶點(diǎn)組成的連通圖，一定可以一筆畫成。畫時(shí)可以把任一偶點(diǎn)為起點(diǎn)，最后一定能以這個(gè)點(diǎn)為終點(diǎn)畫完此圖。例如下圖都是偶點(diǎn)，畫的線路可以是：①→③→⑤→⑦→②→④→⑥→⑦→①哥尼斯堡七橋問題

2．凡是只有兩個(gè)奇點(diǎn)的連通圖（其余都為偶點(diǎn)），一定可以一筆畫成。畫時(shí)必須把一個(gè)奇點(diǎn)為起點(diǎn)，另一個(gè)奇點(diǎn)為終點(diǎn)。例如下圖的線路是：①→②→③→①→④哥尼斯堡七橋問題

3．其他情況的圖都不能一筆畫出。

?請(qǐng)同學(xué)們告訴我，哥尼斯堡七橋問題的答案找到了沒有？

?

留一道作業(yè)：下面的五環(huán)標(biāo)志可否一筆畫成？如何畫？圖的定義6.1圖的邏輯結(jié)構(gòu)圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G=(V，E)其中：G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中頂點(diǎn)之間邊的集合。在線性表中，元素個(gè)數(shù)可以為零，稱為空表；在樹中，結(jié)點(diǎn)個(gè)數(shù)可以為零，稱為空樹；在圖中，頂點(diǎn)個(gè)數(shù)不能為零，但可以沒有邊。6.1圖的邏輯結(jié)構(gòu)如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是無向邊，則稱該圖為無向圖。若頂點(diǎn)vi和vj之間的邊沒有方向，則稱這條邊為無向邊，表示為(vi,vj)。若從頂點(diǎn)vi到vj的邊有方向，則稱這條邊為有向邊，表示為<vi,vj>。

如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是有向邊，則稱該圖為有向圖。V1V2V3V4V5V1V2V3V46.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

簡單圖：在圖中，若不存在頂點(diǎn)到其自身的邊，且同一條邊不重復(fù)出現(xiàn)。V3V4V5V1V2V3V4V5V1V2非簡單圖非簡單圖簡單圖V1V2V3V4V5

數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

鄰接、依附無向圖中，對(duì)于任意兩個(gè)頂點(diǎn)vi和頂點(diǎn)vj，若存在邊(vi，vj)，則稱頂點(diǎn)vi和頂點(diǎn)vj互為鄰接點(diǎn)，同時(shí)稱邊(vi，vj)依附于頂點(diǎn)vi和頂點(diǎn)vj。V1V2V3V4V5V1的鄰接點(diǎn)：V2、V4V2的鄰接點(diǎn)：V1、V3、V56.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

鄰接、依附有向圖中，對(duì)于任意兩個(gè)頂點(diǎn)vi和頂點(diǎn)vj，若存在弧<vi，vj>，則稱頂點(diǎn)vi鄰接到頂點(diǎn)vj，頂點(diǎn)vj鄰接自頂點(diǎn)vi，同時(shí)稱弧<vi，vj>依附于頂點(diǎn)vi和頂點(diǎn)vj

。

V1V2V3V4V1的鄰接點(diǎn)：V2、V3V3的鄰接點(diǎn)：V4在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線性關(guān)系；在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間具有層次關(guān)系；在圖結(jié)構(gòu)中，任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系。FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V1V2V3V4V5圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對(duì)比在線性結(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)系的對(duì)比無向完全圖：在無向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無向完全圖。有向完全圖：在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向相反的兩條弧，則稱該圖為有向完全圖。

圖的基本術(shù)語

V1V2V3V1V2V3V46.1圖的邏輯結(jié)構(gòu)含有n個(gè)頂點(diǎn)的無向完全圖有多少條邊？含有n個(gè)頂點(diǎn)的有向完全圖有多少條??？

6.1圖的邏輯結(jié)構(gòu)含有n個(gè)頂點(diǎn)的無向完全圖有n×(n-1)/2條邊。含有n個(gè)頂點(diǎn)的有向完全圖有n×(n-1)條邊。V1V2V3V1V2V3V4稀疏圖：稱邊數(shù)很少的圖為稀疏圖；稠密圖：稱邊數(shù)很多的圖為稠密圖。頂點(diǎn)的度：在無向圖中，頂點(diǎn)v的度是指依附于該頂點(diǎn)的邊數(shù)，通常記為TD(v)。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

頂點(diǎn)的入度：在有向圖中，頂點(diǎn)v的入度是指以該頂點(diǎn)為弧頭的弧的數(shù)目，記為ID(v)；頂點(diǎn)的出度：在有向圖中，頂點(diǎn)v的出度是指以該頂點(diǎn)為弧尾的弧的數(shù)目，記為OD(v)。V1V2V3V4V56.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

在具有n個(gè)頂點(diǎn)、e條邊的無向圖G中，各頂點(diǎn)的度之和與邊數(shù)之和的關(guān)系？?==niievTD12)(V1V2V3V46.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

在具有n個(gè)頂點(diǎn)、e條邊的有向圖G中，各頂點(diǎn)的入度之和與各頂點(diǎn)的出度之和的關(guān)系？與邊數(shù)之和的關(guān)系？evODvIDiiii==??==11)()(nn權(quán)：是指對(duì)邊賦予的有意義的數(shù)值量。網(wǎng)：邊上帶權(quán)的圖，也稱網(wǎng)圖。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

V1V2V3V42785路徑：在無向圖G=(V,E)中，從頂點(diǎn)vp到頂點(diǎn)vq之間的路徑是一個(gè)頂點(diǎn)序列(vp=vi0,vi1,vi2,…,vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向圖，則路徑也是有方向的，頂點(diǎn)序列滿足<vij-1,vij>∈E。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

V1V2V3V4V5一般情況下，圖中的路徑不惟一。V1到V4的路徑：V1V4

V1V2V3V4V1V2V5V3V4路徑長度：6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

非帶權(quán)圖——路徑上邊的個(gè)數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V1V2V3V4V5V1V4：長度為1V1V2V3V4：長度為3V1V2V5V3V4：長度為4路徑長度：6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

非帶權(quán)圖——路徑上邊的個(gè)數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V1V4：長度為8V1V2V3V4：長度為7V1V2V5V3V4：長度為15V1V2V3V4V5256328回路（環(huán)）：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。簡單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡單回路（簡單環(huán)）：除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

V1V2V3V4V5V1V2V3V4子圖：若圖G=（V，E），G'=（V'，E'），如果V'

V

且E'

E，則稱圖G'是G的子圖。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

V1V2V3V4V5V1V2V3V4V5V1V3V4連通圖：在無向圖中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(i≠j)有路徑，則稱頂點(diǎn)vi和vj是連通的。如果圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱該圖是連通圖。連通分量：非連通圖的極大連通子圖稱為連通分量。

6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

如何求得一個(gè)非連通圖的連通分量?1.含有極大頂點(diǎn)數(shù)；2.依附于這些頂點(diǎn)的所有邊。連通分量1

6.1圖的邏輯結(jié)構(gòu)V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量2圖的基本術(shù)語

連通分量是對(duì)無向圖的一種劃分。強(qiáng)連通圖：在有向圖中，對(duì)圖中任意一對(duì)頂點(diǎn)vi和vj

(i≠j)，若從頂點(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ù)語

如何求得一個(gè)非連通圖的連通分量?6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

V1V2V3V4強(qiáng)連通分量1

強(qiáng)連通分量2V1V3V4V2生成樹：n個(gè)頂點(diǎn)的連通圖G的生成樹是包含G中全部頂點(diǎn)的一個(gè)極小連通子圖。

生成森林：在非連通圖中，由每個(gè)連通分量都可以得到一棵生成樹，這些連通分量的生成樹就組成了一個(gè)非連通圖的生成森林。

如何理解極小連通子圖?6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

多——構(gòu)成回路少——不連通含有n-1條邊V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成樹生成森林6.1圖的邏輯結(jié)構(gòu)圖的抽象數(shù)據(jù)類型定義

ADTGraphData

頂點(diǎn)的有窮非空集合和邊的集合OperationInitGraph

前置條件：圖不存在輸入：無功能：圖的初始化輸出：無后置條件：構(gòu)造一個(gè)空的圖6.1圖的邏輯結(jié)構(gòu)

DFSTraverse

前置條件：圖已存在輸入：遍歷的起始頂點(diǎn)v

功能：從頂點(diǎn)v出發(fā)深度優(yōu)先遍歷圖輸出：圖中頂點(diǎn)的一個(gè)線性排列后置條件：圖保持不變

BFSTraverse

前置條件：圖已存在輸入：遍歷的起始頂點(diǎn)v

功能：從頂點(diǎn)v出發(fā)廣度優(yōu)先遍歷圖輸出：圖中頂點(diǎn)的一個(gè)線性排列后置條件：圖保持不變6.1圖的邏輯結(jié)構(gòu)DestroyGraph

前置條件：圖已存在輸入：無功能：銷毀圖輸出：無后置條件：釋放圖所占用的存儲(chǔ)空間GetVex

前置條件：圖已存在輸入：頂點(diǎn)v

功能：在圖中查找頂點(diǎn)v的數(shù)據(jù)信息輸出：頂點(diǎn)v的數(shù)據(jù)信息后置條件：圖保持不變endADT6.1圖的邏輯結(jié)構(gòu)圖的遍歷操作圖的遍歷是在從圖中某一頂點(diǎn)出發(fā)，對(duì)圖中所有頂點(diǎn)訪問一次且僅訪問一次。

6.1圖的邏輯結(jié)構(gòu)抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡化為輸出結(jié)點(diǎn)的數(shù)據(jù)。圖的遍歷操作要解決的關(guān)鍵問題①在圖中，如何選取遍歷的起始頂點(diǎn)？6.1圖的邏輯結(jié)構(gòu)在線性表中，數(shù)據(jù)元素在表中的編號(hào)就是元素在序列中的位置，因而其編號(hào)是唯一的；在樹中，將結(jié)點(diǎn)按層序編號(hào)，由于樹具有層次性，因而其層序編號(hào)也是唯一的；在圖中，任何兩個(gè)頂點(diǎn)之間都可能存在邊，頂點(diǎn)是沒有確定的先后次序的，所以，頂點(diǎn)的編號(hào)不唯一。為了定義操作的方便，將圖中的頂點(diǎn)按任意順序排列起來，比如，按頂點(diǎn)的存儲(chǔ)順序。解決方案：從編號(hào)小的頂點(diǎn)開始。②從某個(gè)起點(diǎn)始可能到達(dá)不了所有其它頂點(diǎn)，怎么辦？6.1圖的邏輯結(jié)構(gòu)圖的遍歷操作要解決的關(guān)鍵問題解決方案：多次調(diào)用從某頂點(diǎn)出發(fā)遍歷圖的算法。下面僅討論從某頂點(diǎn)出發(fā)遍歷圖的算法。③因圖中可能存在回路，某些頂點(diǎn)可能會(huì)被重復(fù)訪問，那么如何避免遍歷不會(huì)因回路而陷入死循環(huán)。④在圖中，一個(gè)頂點(diǎn)可以和其它多個(gè)頂點(diǎn)相連，當(dāng)這樣的頂點(diǎn)訪問過后，如何選取下一個(gè)要訪問的頂點(diǎn)？

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

基本思想：⑴訪問頂點(diǎn)v；⑵從v的未被訪問的鄰接點(diǎn)中選取一個(gè)頂點(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)先遍歷序列?入棧序列?出棧序列?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的各個(gè)未被訪問的鄰接點(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遍歷序列：V1V2V3V4V4V5V5V6V6V7V7廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?6.1圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V86.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)是否可以采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)圖?圖的特點(diǎn)：頂點(diǎn)之間的關(guān)系是m:n，即任何兩個(gè)頂點(diǎn)之間都可能存在關(guān)系（邊），無法通過存儲(chǔ)位置表示這種任意的邏輯關(guān)系，所以，圖無法采用順序存儲(chǔ)結(jié)構(gòu)。如何存儲(chǔ)圖?考慮圖的定義，圖是由頂點(diǎn)和邊組成的，分別考慮如何存儲(chǔ)頂點(diǎn)、如何存儲(chǔ)邊。鄰接矩陣（數(shù)組表示法）基本思想：用一個(gè)一維數(shù)組存儲(chǔ)圖中頂點(diǎn)的信息，用一個(gè)二維數(shù)組（稱為鄰接矩陣）存儲(chǔ)圖中各頂點(diǎn)之間的鄰接關(guān)系。6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)假設(shè)圖G＝(V，E)有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n×n的方陣，定義為：arc[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它無向圖的鄰接矩陣的特點(diǎn)？無向圖的鄰接矩陣6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4主對(duì)角線為0且一定是對(duì)稱矩陣。如何求頂點(diǎn)i的度？無向圖的鄰接矩陣6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4鄰接矩陣的第i行（或第i列）非零元素的個(gè)數(shù)。如何判斷頂點(diǎn)i和j之間是否存在邊？無向圖的鄰接矩陣6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4測試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。如何求頂點(diǎn)i的所有鄰接點(diǎn)？無向圖的鄰接矩陣6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4將數(shù)組中第i

行元素掃描一遍，若arc[i][j]為1，則頂點(diǎn)j

為頂點(diǎn)i的鄰接點(diǎn)。6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4有向圖的鄰接矩陣一定不對(duì)稱嗎？不一定，例如有向完全圖。6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求頂點(diǎn)i的出度？鄰接矩陣的第i行元素之和。6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求頂點(diǎn)i的入度？鄰接矩陣的第i列元素之和。6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何判斷從頂點(diǎn)i到頂點(diǎn)j是否存在邊？測試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。網(wǎng)圖的鄰接矩陣6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)網(wǎng)圖的鄰接矩陣可定義為：

arc[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他V1V2V3V42785025∞∞0∞

∞

∞

∞087∞∞0arc=鄰接矩陣存儲(chǔ)無向圖的類constintMaxSize=10;template<classT>classMgraph{public:MGraph(Ta[],intn,inte);~MGraph()

voidDFSTraverse(intv);voidBFSTraverse(intv);private:Tvertex[MaxSize];intarc[MaxSize][MaxSize];intvertexNum,arcNum;};6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)鄰接矩陣中圖的基本操作——構(gòu)造函數(shù)確定圖的頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)；2.輸入頂點(diǎn)信息存儲(chǔ)在一維數(shù)組vertex中；3.初始化鄰接矩陣；4.依次輸入每條邊存儲(chǔ)在鄰接矩陣arc中；4.1輸入邊依附的兩個(gè)頂點(diǎn)的序號(hào)i,j；4.2將鄰接矩陣的第i行第j列的元素值置為1；4.3將鄰接矩陣的第j行第i列的元素值置為1；6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)template<classT>MGraph::MGraph(Ta[],intn,inte){vertexNum=n;arcNum=e;for(i=0;i<vertexNum;i++)vertex[i]=a[i];for(i=0;i<vertexNum;i++)//初始化鄰接矩陣

for(j=0;j<vertexNum;j++)arc[i][j]=0;for(k=0;k<arcNum;k++)//依次輸入每一條邊{cin>>i>>j;//邊依附的兩個(gè)頂點(diǎn)的序號(hào)arc[i][j]=1;arc[j][i]=1;//置有邊標(biāo)志

}}6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)鄰接矩陣中圖的基本操作——構(gòu)造函數(shù)鄰接矩陣中圖的基本操作——深度優(yōu)先遍歷template<classT>voidMGraph::DFSTraverse(intv)

{cout<<vertex[v];visited[v]=1;for(j=0;j<vertexNum;j++)if(arc[v][j]==1&&visited[j]==0)

DFSTraverse(j);}6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)鄰接矩陣中圖的基本操作——廣度優(yōu)先遍歷template<classT>voidMGraph::BFSTraverse(intv)

{front=rear=-1;//假設(shè)采用順序隊(duì)列且不會(huì)發(fā)生溢出cout<<vertex[v];visited[v]=1;Q[++rear]=v;while(front!=rear){v=Q[++front];

for(j=0;j<vertexNum;j++)if(arc[v][j]==1&&visited[j]==0){cout<<vertex[j];visited[j]=1;Q[++rear]=j;}}}6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)鄰接表鄰接表存儲(chǔ)的基本思想：對(duì)于圖的每個(gè)頂點(diǎn)vi，將所有鄰接于vi的頂點(diǎn)鏈成一個(gè)單鏈表，稱為頂點(diǎn)vi的邊表（對(duì)于有向圖則稱為出邊表），所有邊表的頭指針和存儲(chǔ)頂點(diǎn)信息的一維數(shù)組構(gòu)成了頂點(diǎn)表。

6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的空間復(fù)雜度？如果為稀疏圖則會(huì)出現(xiàn)什么現(xiàn)象？假設(shè)圖G有n個(gè)頂點(diǎn)e條邊，則存儲(chǔ)該圖需要O(n2)。鄰接表有兩種結(jié)點(diǎn)結(jié)構(gòu)：頂點(diǎn)表結(jié)點(diǎn)和邊表結(jié)點(diǎn)。vertexfirstedge

adjvex

next

頂點(diǎn)表邊表vertex：數(shù)據(jù)域，存放頂點(diǎn)信息。

firstedge：指針域，指向邊表中第一個(gè)結(jié)點(diǎn)。

adjvex：鄰接點(diǎn)域，邊的終點(diǎn)在頂點(diǎn)表中的下標(biāo)。next：指針域，指向邊表中的下一個(gè)結(jié)點(diǎn)。

6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)structArcNode{intadjvex;ArcNode*next;};template<classT>structVertexNode{

Tvertex;

ArcNode*firstedge;};定義鄰接表的結(jié)點(diǎn)

6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)vertexfirstedge

adjvex

next103∧23∧1∧01∧V1V2

V3V40123vertexfirstedge6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)V1V3V4V2無向圖的鄰接表邊表中的結(jié)點(diǎn)表示什么？每個(gè)結(jié)點(diǎn)對(duì)應(yīng)圖中的一條邊，鄰接表的空間復(fù)雜度為O(n+e)。103∧23∧1∧01∧V1V2

V3V40123vertexfirstedge6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)V1V3V4V2無向圖的鄰接表如何求頂點(diǎn)i的度？頂點(diǎn)i的邊表中結(jié)點(diǎn)的個(gè)數(shù)。如何判斷頂點(diǎn)i和頂點(diǎn)j之間是否存在邊?測試頂點(diǎn)i的邊表中是否存在終點(diǎn)為j的結(jié)點(diǎn)。6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2無向圖的鄰接表6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)有向圖的鄰接表V1V2V3V412∧2∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點(diǎn)i的出度？頂點(diǎn)i的出邊表中結(jié)點(diǎn)的個(gè)數(shù)。6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)有向圖的鄰接表V1V2V3V412∧2∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點(diǎn)i的入度？各頂點(diǎn)的出邊表中以頂點(diǎn)i為終點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)。6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)有向圖的鄰接表V1V2V3V412∧3∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點(diǎn)i的所有鄰接點(diǎn)？遍歷頂點(diǎn)i的邊表，該邊表中的所有終點(diǎn)都是頂點(diǎn)i的鄰接點(diǎn)。6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)網(wǎng)圖的鄰接表V1V2V3V4278521V1V2

V3V40123vertexfirstedge∧52∧83∧70∧鄰接表存儲(chǔ)有向圖的類constintMaxSize=10;//圖的最大頂點(diǎn)數(shù)template<classT>classALGraph{public:ALGraph(Ta[],intn,inte);~ALGraph;voidDFSTraverse(intv);

voidBFSTraverse(intv);private:VertexNodeadjlist[MaxSize];

intvertexNum,arcNum;};6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)鄰接表中圖的基本操作——構(gòu)造函數(shù)

1.確定圖的頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)；2.輸入頂點(diǎn)信息，初始化該頂點(diǎn)的邊表；3.依次輸入邊的信息并存儲(chǔ)在邊表中；3.1輸入邊所依附的兩個(gè)頂點(diǎn)的序號(hào)i和j；3.2生成鄰接點(diǎn)序號(hào)為j的邊表結(jié)點(diǎn)s；

3.3將結(jié)點(diǎn)s插入到第i個(gè)邊表的頭部；6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)template<classT>ALGraph::ALGraph(Ta[],intn,inte){vertexNum=n;arcNum=e;

for(i=0;i<vertexNum;i++)

//輸入頂點(diǎn)信息，初始化邊表{

adjlist[i].vertex=a[i];adjlist[i].firstedge=NULL;}

6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)鄰接表中圖的基本操作——構(gòu)造函數(shù)

sfor(k=0;k<arcNum;k++)//輸入邊的信息存儲(chǔ)在邊表中{

cin>>i>>j;

s=newArcNode;s->adjvex=j; s->next=adjlist[i].firstedge;adjlist[i].firstedge=s;}}6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)12V1V2

V3V40123∧∧∧∧①②鄰接表中圖的基本操作——深度優(yōu)先遍歷template<classT>voidALGraph::DFSTraverse(intv){

cout<<adjlist[v].vertex;visited[v]=1;p=adjlist[v].firstedge;while(p!=NULL)

{j=p->adjvex;if(visited[j]==0)DFSTraverse(j);

p=p->next;}}6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)鄰接表中圖的基本操作——廣度優(yōu)先遍歷template<classT>voidALGraph::BFSTraverse(intv)

{front=rear=-1;cout<<adjlist[v].vertex;visited[v]=1;Q[++rear]=v;while(front!=rear){v=Q[++front];p=adjlist[v].firstedge;while(p!=NULL)

{j=p->adjvex;if(visited[j]==0){cout<<adjlist[j].vertex;visited[j]=1;Q[++rear]=j;}p=p->next;}}}6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)十字鏈表鄰接表6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)逆鄰接表將鄰接表與逆鄰接表合二為一?為什么要合并？V1V2V3V412∧3∧0v1v2v3v4∧01231∧3∧0∧2∧v1v2v3v4012303∧十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)vertexfirstinfirstout頂點(diǎn)表結(jié)點(diǎn)tailvexheadvexheadlinktaillink邊表結(jié)點(diǎn)tailvex：弧的起點(diǎn)在頂點(diǎn)表中的下標(biāo)；headvex：弧的終點(diǎn)在頂點(diǎn)表中的下標(biāo)；headlink：入邊表指針域；taillink：出邊表指針域。6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)vertex：數(shù)據(jù)域，存放頂點(diǎn)信息；firstin：入邊表頭指針；firstout：出邊表頭指針；3031∧3210V1V2V3V423

∧0102∧6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)十字鏈表存儲(chǔ)有向圖∧∧V1V2V3V4∧∧∧v3v4v4v1v1v2v1v3v4v2圖的存儲(chǔ)結(jié)構(gòu)的比較——鄰接矩陣和鄰接表O（n2）O（n+e）O（n2）O（n+e）空間性能時(shí)間性能適用范圍唯一性鄰接矩陣鄰接表稠密圖稀疏圖唯一不唯一6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)6.3圖的連通性要想判定一個(gè)無向圖是否為連通圖，或有幾個(gè)連通分量，通過對(duì)無向圖遍歷即可得到結(jié)果。非連通圖：需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過程中得到的頂點(diǎn)訪問序列恰為其各個(gè)連通分量中的頂點(diǎn)集。

連通圖：僅需從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索（或廣度優(yōu)先搜索），便可訪問到圖中所有頂點(diǎn)。

無向圖的連通性count=0;2.for(圖中每個(gè)頂點(diǎn)v)2.1if(v尚未被訪問過)

2.1.1count++;2.1.2從v出發(fā)遍歷該圖；3.if(count==1)

cout<<"圖是連通的";

elsecout<<"圖中有"<<count<<"個(gè)連通分量";求無向圖的連通分量6.3圖的連通性有向圖的連通性⑴從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷，并按其所有鄰接點(diǎn)都訪問（即出棧）的順序?qū)㈨旤c(diǎn)排列起來。⑵從最后完成訪問的頂點(diǎn)出發(fā)，沿著以該頂點(diǎn)為頭的弧作逆向的深度優(yōu)先遍歷。若不能訪問到所有頂點(diǎn)，則從余下的頂點(diǎn)中最后訪問的那個(gè)頂點(diǎn)出發(fā)，繼續(xù)作逆向的深度優(yōu)先遍歷，直至有向圖中所有頂點(diǎn)都被訪問到為止。⑶每一次逆向深度優(yōu)先遍歷所訪問到的頂點(diǎn)集便是該有向圖的一個(gè)強(qiáng)連通分量的頂點(diǎn)集。6.3圖的連通性（a）深度優(yōu)先生成樹（b）廣度優(yōu)先生成樹生成樹6.3圖的連通性V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V8由深度優(yōu)先遍歷得到的為深度優(yōu)先生成樹，由廣度優(yōu)先遍歷得到的為廣度優(yōu)先生成樹。

一個(gè)連通圖的生成樹可能不唯一，由不同的遍歷次序、從不同頂點(diǎn)出發(fā)進(jìn)行遍歷都會(huì)得到不同的生成樹。

對(duì)于非連通圖，通過圖的遍歷，將得到的是生成森林。

結(jié)論：6.3圖的連通性生成樹生成樹的代價(jià)：設(shè)G=（V，E）是一個(gè)無向連通網(wǎng)，生成樹上各邊的權(quán)值之和稱為該生成樹的代價(jià)。

最小生成樹：在圖G所有生成樹中，代價(jià)最小的生成樹稱為最小生成樹。應(yīng)用舉例——最小生成樹最小生成樹最小生成樹的概念可以應(yīng)用到許多實(shí)際問題中。例：在n個(gè)城市之間建造通信網(wǎng)絡(luò)，至少要架設(shè)n-1條通信線路，而每兩個(gè)城市之間架設(shè)通信線路的造價(jià)是不一樣的，那么如何設(shè)計(jì)才能使得總造價(jià)最小？MST性質(zhì)假設(shè)G=(V,E)是一個(gè)無向連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹。應(yīng)用舉例——最小生成樹頂點(diǎn)集UV－Uu'vv'u頂點(diǎn)集T1T2基本思想：設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的連通網(wǎng)，T=(U,TE)是G的最小生成樹，T的初始狀態(tài)為U={u0}（u0∈V），TE={}，重復(fù)執(zhí)行下述操作：在所有u∈U，v∈V-U的邊中找一條代價(jià)最小的邊(u,v)并入集合TE，同時(shí)v并入U(xiǎn)，直至U=V。關(guān)鍵:是如何找到連接U和V-U的最短邊。

普里姆（Prim）算法

應(yīng)用舉例——最小生成樹利用MST性質(zhì)，可以用下述方法構(gòu)造候選最短邊集：對(duì)應(yīng)V-U中的每個(gè)頂點(diǎn)，保留從該頂點(diǎn)到U中的各頂點(diǎn)的最短邊。U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}251234192646381725應(yīng)用舉例——最小生成樹ABEDCFPrim算法

Prim算法

應(yīng)用舉例——最小生成樹251234192646381725ABEDCFU={A,F}V-U={B,C,D,E}cost={(A,B)34,(F,C)25,(F,D)25,(F,E)26}Prim算法

應(yīng)用舉例——最小生成樹251234192646381725ABEDCFU={A,F,C}V-U={B,D,E}cost={(A,B)34,(C,D)17,(F,E)26}

Prim算法

應(yīng)用舉例——最小生成樹251234192646381725ABEDCFU={A,F,C,D}V-U={B,E}cost={(A,B)34,(F,E)26}

Prim算法

應(yīng)用舉例——最小生成樹251234192646381725ABEDCFU={A,F,C,D,E}V-U={B}cost={(E,B)12}

Prim算法

應(yīng)用舉例——最小生成樹251234192646381725ABEDCFU={A,F,C,D,E,B}V-U={}數(shù)組lowcost[n]：用來保存集合V-U中各頂點(diǎn)與集合U中頂點(diǎn)最短邊的權(quán)值，lowcost[v]=0表示頂點(diǎn)v已加入最小生成樹中；數(shù)組adjvex[n]：用來保存依附于該邊（集合V-U中各頂點(diǎn)與集合U中頂點(diǎn)的最短邊）在集合U中的頂點(diǎn)。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)表示頂點(diǎn)vi和頂點(diǎn)vk之間的權(quán)值為w，其中：vi∈V-U且vk∈Ulowcost[i]=wadjvex[i]=k應(yīng)用舉例——最小生成樹如何用數(shù)組lowcost和adjvex表示候選最短邊集？

i

數(shù)組B(i=1)C(i=2)D(i=3)E(i=4)F(i=5)UV-U輸出adjvexlowcostA34A46A∞A∞A19{A}{B,C,D,E,F}(AF)19adjvexlowcostA34F25F25F26

{A,F}{B,C,D,E}(FC)25adjvexlowcostA34

C17F26

{A,F,C}{B,D,E}(CD)17adjvexlowcostA34

F26

{A,F,C,D}{B,E}(FE)26adjvexlowcostE12

{A,F,C,D,E}{B}(EB)12adjvexlowcost

{A,F,C,D,E,B}{}

應(yīng)用舉例——最小生成樹1.初始化兩個(gè)輔助數(shù)組lowcost和adjvex；2.輸出頂點(diǎn)u0，將頂點(diǎn)u0加入集合U中；3.重復(fù)執(zhí)行下列操作n-1次

3.1在lowcost中選取最短邊，取adjvex中對(duì)應(yīng)的頂點(diǎn)序號(hào)k；

3.2輸出頂點(diǎn)k和對(duì)應(yīng)的權(quán)值；

3.3將頂點(diǎn)k加入集合U中；

3.4調(diào)整數(shù)組lowcost和adjvex；應(yīng)用舉例——最小生成樹Prim算法——偽代碼

克魯斯卡爾（Kruskal）算法

基本思想：設(shè)無向連通網(wǎng)為G＝(V,E)，令G的最小生成樹為T＝(U,TE)，其初態(tài)為U＝V，TE＝{}，然后，按照邊的權(quán)值由小到大的順序，考察G的邊集E中的各條邊。若被考察的邊的兩個(gè)頂點(diǎn)屬于T的兩個(gè)不同的連通分量，則將此邊作為最小生成樹的邊加入到T中，同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察邊的兩個(gè)頂點(diǎn)屬于同一個(gè)連通分量，則舍去此邊，以免造成回路，如此下去，當(dāng)T中的連通分量個(gè)數(shù)為1時(shí)，此連通分量便為G的一棵最小生成樹。

應(yīng)用舉例——最小生成樹251234192646382025ABEDCF應(yīng)用舉例——最小生成樹ABEDCF連通分量＝{A},{B},{C},{D},{E},{F}251234192646382025ABEDCF應(yīng)用舉例——最小生成樹ABEDCF連通分量＝{A},{B},{C},{D},{E},{F}12連通分量＝{A},{B,E},{C},{D},{F}251234192646382025ABEDCF應(yīng)用舉例——最小生成樹ABEDCF連通分量＝{A},{B,E},{C},{D},{F}12連通分量＝{A,F},{B,E},{C},{D}19251234192646382025ABEDCF應(yīng)用舉例——最小生成樹ABEDCF連通分量＝{A,F},{B,E},{C},{D}12連通分量＝{A,F},{B,E},{C,D}1920251234192646382025ABEDCF應(yīng)用舉例——最小生成樹ABEDCF連通分量＝{A,F},{B,E},{C,D}12連通分量＝{A,F,C,D},{B,E}192025251234192646382025ABEDCF應(yīng)用舉例——最小生成樹ABEDCF連通分量＝{A,F,C,D},{B,E}12連通分量＝{A,F,C,D,B,E}192025261.初始化：U=V；TE={}；2.循環(huán)直到T中的連通分量個(gè)數(shù)為12.1在E中尋找最短邊(u，v);2.2如果頂點(diǎn)u、v位于T的兩個(gè)不同連通分量，則

2.2.1將邊(u，v)并入TE；

2.2.2將這兩個(gè)連通分量合為一個(gè)；

2.3在E中標(biāo)記邊(u，v)，使得(u，v)不參加后續(xù)最短邊的選取；應(yīng)用舉例——最小生成樹Kruskal算法——偽代碼在非網(wǎng)圖中，最短路徑是指兩頂點(diǎn)之間經(jīng)歷的邊數(shù)最少的路徑。

應(yīng)用舉例——最短路徑最短路徑

BAEDCAE：1ADE：2ADCE：3ABCE：3應(yīng)用舉例——最短路徑最短路徑

在網(wǎng)圖中，最短路徑是指兩頂點(diǎn)之間經(jīng)歷的邊上權(quán)值之和最短的路徑。

BAEDC105030101002060AE：100ADE：90ADCE：60ABCE：70問題描述：給定帶權(quán)有向圖G＝(V,E)和源點(diǎn)v∈V，求從v到G中其余各頂點(diǎn)的最短路徑。

單源點(diǎn)最短路徑問題

應(yīng)用舉例——最短路徑應(yīng)用實(shí)例——計(jì)算機(jī)網(wǎng)絡(luò)傳輸?shù)膯栴}：怎樣找到一種最經(jīng)濟(jì)的方式，從一臺(tái)計(jì)算機(jī)向網(wǎng)上所有其它計(jì)算機(jī)發(fā)送一條消息。迪杰斯特拉（Dijkstra）提出了一個(gè)按路徑長度遞增的次序產(chǎn)生最短路徑的算法——Dijkstra算法?；舅枷耄涸O(shè)置一個(gè)集合S存放已經(jīng)找到最短路徑的頂點(diǎn)，S的初始狀態(tài)只包含源點(diǎn)v，對(duì)vi∈V-S，假設(shè)從源點(diǎn)v到vi的有向邊為最短路徑。以后每求得一條最短路徑v,…,vk，就將vk加入集合S中，并將路徑v,…,vk,vi與原來的假設(shè)相比較，取路徑長度較小者為最短路徑。重復(fù)上述過程，直到集合V中全部頂點(diǎn)加入到集合S中。Dijkstra算法應(yīng)用舉例——最短路徑

集合

V-S集合

SvkvviDijkstra算法的基本思想應(yīng)用舉例——最短路徑ABAEDC105030101002060S={A}A→B:(A,B)10A→C:(A,C)∞A→D:(A,D)30A→E:(A,E)100應(yīng)用舉例——最短路徑Dijkstra算法ABAEDC105030101002060S={A,B}A→B:(A,B)10A→C:(A,B,C)60A→D:(A,D)30A→E:(A,E)100應(yīng)用舉例——最短路徑BDijkstra算法ABAEDC105030101002060S={A,B,D}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,E)90應(yīng)用舉例——最短路徑BDDijkstra算法ABAEDC105030101002060S={A,B,D,C}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60應(yīng)用舉例——最短路徑BDCDijkstra算法ABAEDC105030101002060Dijkstra算法S={A,B,D,C,E}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60應(yīng)用舉例——最短路徑BDCE圖的存儲(chǔ)結(jié)構(gòu)：帶權(quán)的鄰接矩陣存儲(chǔ)結(jié)構(gòu)

數(shù)組dist[n]：每個(gè)分量dist[i]表示當(dāng)前所找到的從始點(diǎn)v到終點(diǎn)vi的最短路徑的長度。初態(tài)為：若從v到vi有弧，則dist[i]為弧上權(quán)值；否則置dist[i]為∞。數(shù)組path[n]：path[i]是一個(gè)字符串，表示當(dāng)前所找到的從始點(diǎn)v到終點(diǎn)vi的最短路徑。初態(tài)為：若從v到vi有弧，則path[i]為vvi；否則置path[i]空串。數(shù)組s[n]：存放源點(diǎn)和已經(jīng)生成的終點(diǎn)，其初態(tài)為只有一個(gè)源點(diǎn)v。

設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)

:應(yīng)用舉例——最短路徑迪杰斯特拉算法的主要步驟如下：

(1)g為用鄰接矩陣表示的帶權(quán)圖。將v0到其余頂點(diǎn)的路徑長度初始化為權(quán)值；

S←{v0}，dist［i］=g.arcs［v0］［vi］；

(2)選擇vk，使得vk為目前求得的下一條從v0出發(fā)的最短路徑的終點(diǎn)。(3)修改從v0出發(fā)到集合V-S上任一頂點(diǎn)vi的最短路徑的長度。

如果dist［k］+g.arcs［k］［i］<dist［i］

則修改dist［i］為:dist［k］+g.arcs［k］［i］(4)重復(fù)(2)、(3)n-1次，即可按最短路徑長度的遞增順序，逐個(gè)求出v0到圖中其它每個(gè)頂點(diǎn)的最短路徑。實(shí)例：求圖7.26中v0頂點(diǎn)到其它各頂點(diǎn)的最短路徑

v0v2v5v4v1v3201531050104515353020012345012345∞5010∞45∞∞∞15∞10∞20∞∞15∞∞∞20∞∞35∞∞∞∞30∞∞∞∞∞3∞∞圖7.26一個(gè)帶權(quán)有向圖及其鄰接矩陣應(yīng)用舉例——最短路徑終點(diǎn)從V0到各終點(diǎn)的dist[i]值和最短距離V110∞45∞V250/2545∞V345//45∞V4///45∞////

加入S集合的頂點(diǎn){V0}V2V3V1V4無最短路徑值10254545

V5

50∞dist［k］+g.arcs［k］［i］<dist［i］每一對(duì)頂點(diǎn)之間的最短路徑

問題描述：給定帶權(quán)有向圖G＝(V,E)，對(duì)任意頂點(diǎn)vi,vj∈V（i≠j），求頂點(diǎn)vi到頂點(diǎn)vj的最短路徑。

應(yīng)用舉例——最短路徑解決辦法1：每次以一個(gè)頂點(diǎn)為源點(diǎn)，調(diào)用Dijkstra算法n次。顯然，時(shí)間復(fù)雜度為O(n3)。解決辦法2：弗洛伊德提出的求每一對(duì)頂點(diǎn)之間的最短路徑算法——Floyd算法，其時(shí)間復(fù)雜度也是O(n3)，但形式上要簡單些?；舅枷耄簩?duì)于從vi到vj的弧，進(jìn)行n次試探：首先考慮路徑vi,v0,vj是否存在，如果存在，則比較vi,vj和vi,v0,vj的路徑長度，取較短者為從vi到vj的中間頂點(diǎn)的序號(hào)不大于0的最短路徑。在路徑上再增加一個(gè)頂點(diǎn)v1，依此類推，在經(jīng)過n次比較后，最后求得的必是從頂點(diǎn)vi到頂點(diǎn)vj的最短路徑。

Floyd算法應(yīng)用舉例——最短路徑04116023∞0有向網(wǎng)圖鄰接矩陣Floyd算法應(yīng)用舉例——最短路徑acb346112Floyd算法應(yīng)用舉例——最短路徑acb346112dist-1

=04116023∞0path-1

=

abacbabcca初始化Floyd算法應(yīng)用舉例——最短路徑acb346112dist-1

=04116023∞0path-1

=

abacbabcca第1次迭代dist0

=0411602370path0

=

abacbabccacab

Floyd算法應(yīng)用舉例——最短路徑acb346112第2次迭代dist0

=0411602370path0

=

abacbabccacabdist1

=046602370path1

=

ababc

babccacabFloyd算法應(yīng)用舉例——最短路徑acb346112第3次迭代dist2

=046502370path2

=

ababcbcabccacabdist1

=046602370path1

=

ababcbabccacab圖的存儲(chǔ)結(jié)構(gòu)：帶權(quán)的鄰接矩陣存儲(chǔ)結(jié)構(gòu)

數(shù)組dist[n][n]：存放在迭代過程中求得的最短路徑長度。迭代公式：數(shù)組path[n][n]：存放從vi到vj的最短路徑，初始為path[i][j]