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

第六章圖圖的邏輯結(jié)構(gòu)圖的存儲結(jié)構(gòu)及實現(xiàn)最小生成樹最短路徑AOV網(wǎng)與拓?fù)渑判駻OE網(wǎng)與關(guān)鍵路徑數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第1頁。歐拉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%。歐拉對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。圖論——歐拉數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第2頁。能否從某個地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點？哥尼斯堡七橋問題ABCD數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第3頁。CADB七橋問題的圖模型哥尼斯堡七橋問題歐拉回路的判定規(guī)則：1.如果通奇數(shù)橋的地方多于兩個，則不存在歐拉回路；2.如果只有兩個地方通奇數(shù)橋，可以從這兩個地方之一出發(fā)，找到歐拉回路；3.如果沒有一個地方是通奇數(shù)橋的，則無論從哪里出發(fā)，都能找到歐拉回路。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第4頁。圖的定義6.1圖的邏輯結(jié)構(gòu)圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G=(V，E)其中：G表示一個圖，V是圖G中頂點的集合，E是圖G中頂點之間邊的集合。在線性表中，元素個數(shù)可以為零，稱為空表；在樹中，結(jié)點個數(shù)可以為零，稱為空樹；在圖中，頂點個數(shù)不能為零，但可以沒有邊。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第5頁。6.1圖的邏輯結(jié)構(gòu)如果圖的任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖。若頂點vi和vj之間的邊沒有方向，則稱這條邊為無向邊，表示為(vi,vj)。若從頂點vi到vj的邊有方向，則稱這條邊為有向邊，表示為<vi,vj>。

如果圖的任意兩個頂點之間的邊都是有向邊，則稱該圖為有向圖。V0V1V2V3V4V0V1V2V3數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第6頁。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

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

數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖。V0V1V2V3V4V0V1V2V3V4V0V1V2V3V4數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第7頁。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

鄰接、依附無向圖中，對于任意兩個頂點vi和頂點vj，若存在邊(vi，vj)，則稱頂點vi和頂點vj互為鄰接點，同時稱邊(vi，vj)依附于頂點vi和頂點vj。V0的鄰接點：V1、V3V1的鄰接點：V0、V2、V4V0V1V2V3V4數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第8頁。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

鄰接、依附有向圖中，對于任意兩個頂點vi和頂點vj，若存在弧<vi，vj>，則稱頂點vi鄰接到頂點vj，頂點vj鄰接自頂點vi，同時稱弧<vi，vj>依附于頂點vi和頂點vj

。

V0V1V2V3V0的鄰接點：V1、V2V2的鄰接點：V3數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第9頁。在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線性關(guān)系；在樹結(jié)構(gòu)中，結(jié)點之間具有層次關(guān)系；在圖結(jié)構(gòu)中，任意兩個頂點之間都可能有關(guān)系。FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對比V0V1V2V3V4圖結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第10頁。在線性結(jié)構(gòu)中，元素之間的關(guān)系為前驅(qū)和后繼；在樹結(jié)構(gòu)中，結(jié)點之間的關(guān)系為雙親和孩子；在圖結(jié)構(gòu)中，頂點之間的關(guān)系為鄰接。FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對比V0V1V2V3V4圖結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第11頁。無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向相反的兩條弧，則稱該圖為有向完全圖。

圖的基本術(shù)語

V0V1V2V0V1V2V36.1圖的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第12頁。含有n個頂點的無向完全圖有多少條邊？含有n個頂點的有向完全圖有多少條??？

6.1圖的邏輯結(jié)構(gòu)含有n個頂點的無向完全圖有n×(n-1)/2條邊。含有n個頂點的有向完全圖有n×(n-1)條邊。V0V1V2V3V0V1V2數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第13頁。稀疏圖：稱邊數(shù)很少的圖為稀疏圖；稠密圖：稱邊數(shù)很多的圖為稠密圖。頂點的度：在無向圖中，頂點v的度是指依附于該頂點的邊數(shù)，通常記為TD(v)。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

頂點的入度：在有向圖中，頂點v的入度是指以該頂點為弧頭的弧的數(shù)目，記為ID(v)；頂點的出度：在有向圖中，頂點v的出度是指以該頂點為弧尾的弧的數(shù)目，記為OD(v)。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第14頁。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

在具有n個頂點、e條邊的無向圖G中，各頂點的度之和與邊數(shù)之和的關(guān)系？?==niievTD12)(V0V1V2V3V4數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第15頁。V0V1V2V36.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

在具有n個頂點、e條邊的有向圖G中，各頂點的入度之和與各頂點的出度之和的關(guān)系？與邊數(shù)之和的關(guān)系？evODvIDiiii==??==11)()(nn數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第16頁。權(quán)：是指對邊賦予的有意義的數(shù)值量。網(wǎng)：邊上帶權(quán)的圖，也稱網(wǎng)圖。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

V0V1V2V32785哈夫曼樹中的權(quán)與網(wǎng)圖的權(quán)有何區(qū)別？7423數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第17頁。路徑：在無向圖G=(V,E)中，從頂點vp到頂點vq之間的路徑是一個頂點序列(vp=vi0,vi1,vi2,…,vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向圖，則路徑也是有方向的，頂點序列滿足<vij-1,vij>∈E。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

一般情況下，圖中的路徑不惟一V0到V3的路徑：V0V3

V0V1V2V3V0V1V4V2V3V0V1V2V3V4數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第18頁。路徑長度：6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

非帶權(quán)圖——路徑上邊的個數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V0V3：長度為1V0V1V2V3：長度為3V0V1V4V2V3：長度為4V0V1V2V3V4數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第19頁。路徑長度：6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

非帶權(quán)圖——路徑上邊的個數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V0V3：長度為8V0V1V2V3：長度為7V0V1V4V2V3：長度為15V0V1V2V3V4256328數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第20頁。回路（環(huán)）：第一個頂點和最后一個頂點相同的路徑。簡單路徑：序列中頂點不重復(fù)出現(xiàn)的路徑。簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

V0V1V2V3V4V0V1V2V3數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第21頁。子圖：若圖G=（V，E），G'=（V'，E'），如果V'V

且E'

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

V0V1V2V3V4V0V1V2V3V4V0V2V3數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第22頁。連通圖：在無向圖中，如果從一個頂點vi到另一個頂點vj(i≠j)有路徑，則稱頂點vi和vj是連通的。如果圖中任意兩個頂點都是連通的，則稱該圖是連通圖。連通分量：非連通圖的極大連通子圖稱為連通分量。

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

如何求得一個非連通圖的連通分量?1.含有極大頂點數(shù)；2.依附于這些頂點的所有邊。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第23頁。連通分量1

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

連通分量是對無向圖的一種劃分?jǐn)?shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第24頁。強連通圖：在有向圖中，對圖中任意一對頂點vi和vj

(i≠j)，若從頂點vi到頂點vj和從頂點vj到頂點vi均有路徑，則稱該有向圖是強連通圖。強連通分量：非強連通圖的極大強連通子圖。

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

如何求得一個非連通圖的連通分量?數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第25頁。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語

V0V1V2V3強連通分量1

強連通分量2V0V2V3V1數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第26頁。生成樹：n個頂點的連通圖G的生成樹是包含G中全部頂點的一個極小連通子圖。

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

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

多——構(gòu)成回路少——不連通含有n-1條邊數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第27頁。V0V1V3V4V2V6V5V0V1V3V4V2V6V5V0V1V2V3V4V0V1V2V3V4生成樹生成森林6.1圖的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第28頁。圖的抽象數(shù)據(jù)類型定義

ADTGraphData

頂點的有窮非空集合和邊的集合Operation

6.1圖的邏輯結(jié)構(gòu)圖是一種與具體應(yīng)用密切相關(guān)的數(shù)據(jù)結(jié)構(gòu)，它的基本操作往往隨應(yīng)用不同而有很大差別。下面給出一個圖的抽象數(shù)據(jù)類型定義的例子，簡單起見，基本操作僅包含圖的遍歷，針對具體應(yīng)用，需要重新定義其基本操作。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第29頁。InitGraph

前置條件：圖不存在輸入：無功能：圖的初始化輸出：無后置條件：構(gòu)造一個空的圖DestroyGraph

前置條件：圖已存在輸入：無功能：銷毀圖輸出：無后置條件：釋放圖所占用的存儲空間6.1圖的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第30頁。

DFSTraverse

前置條件：圖已存在輸入：遍歷的起始頂點v

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

BFSTraverse

前置條件：圖已存在輸入：遍歷的起始頂點v

功能：從頂點v出發(fā)廣度優(yōu)先遍歷圖輸出：圖中頂點的一個線性排列后置條件：圖保持不變endADT6.1圖的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第31頁。圖的遍歷操作圖的遍歷是在從圖中某一頂點出發(fā)，對圖中所有頂點訪問一次且僅訪問一次。

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

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

基本思想：⑴訪問頂點v；⑵從v的未被訪問的鄰接點中選取一個頂點w，從w出發(fā)進(jìn)行深度優(yōu)先遍歷；⑶

重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。

6.1圖的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第37頁。深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5

V5數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第38頁。深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8

V8數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第39頁。深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第40頁。深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8

V1遍歷序列：V1

V7V2V4V5V8V3

V3V6

V6V7數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第41頁。1.深度優(yōu)先遍歷

從頂點v出發(fā)圖的深度優(yōu)先遍歷算法的偽代碼：

6.1圖的邏輯結(jié)構(gòu)1.訪問頂點v;visited[v]=1;2.w=頂點v的第一個鄰接點；3.while(w存在)3.1if(w未被訪問)從頂點w出發(fā)遞歸執(zhí)行該算法;3.2w=頂點v的下一個鄰接點;數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第42頁。2.廣度優(yōu)先遍歷

基本思想：⑴訪問頂點v；⑵依次訪問v的各個未被訪問的鄰接點v1,v2,…,vk；⑶分別從v1，v2，…，vk出發(fā)依次訪問它們未被訪問的鄰接點，并使“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”被訪問。直至圖中所有與頂點v有路徑相通的頂點都被訪問到。6.1圖的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第43頁。廣度優(yōu)先遍歷序列?入隊序列?出隊序列?6.1圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8遍歷序列：V1V1數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第44頁。廣度優(yōu)先遍歷序列?入隊序列?出隊序列?6.1圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V3數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第45頁。廣度優(yōu)先遍歷序列?入隊序列?出隊序列?6.1圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V5數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第46頁。廣度優(yōu)先遍歷序列?入隊序列?出隊序列?6.1圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V7數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第47頁。廣度優(yōu)先遍歷序列?入隊序列?出隊序列?6.1圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V8數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第48頁。2.廣度優(yōu)先遍歷

6.1圖的邏輯結(jié)構(gòu)從頂點v出發(fā)圖的廣度優(yōu)先遍歷算法的偽代碼：

1.初始化隊列Q;2.訪問頂點v;visited[v]=1;頂點v入隊列Q;3.while(隊列Q非空)3.1v=隊列Q的隊頭元素出隊;3.2w=頂點v的第一個鄰接點;3.3while(w存在)3.3.1如果w未被訪問，則訪問頂點w;visited[w]=1;頂點w入隊列Q；

3.3.2w=頂點v的下一個鄰接點；數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第49頁。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)是否可以采用順序存儲結(jié)構(gòu)存儲圖?圖的特點：頂點之間的關(guān)系是m:n，即任何兩個頂點之間都可能存在關(guān)系（邊），無法通過存儲位置表示這種任意的邏輯關(guān)系，所以，圖無法采用順序存儲結(jié)構(gòu)。如何存儲圖?考慮圖的定義，圖是由頂點和邊組成的，分別考慮如何存儲頂點、如何存儲邊。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第50頁。鄰接矩陣（數(shù)組表示法）基本思想：用一個一維數(shù)組存儲圖中頂點的信息，用一個二維數(shù)組（稱為鄰接矩陣）存儲圖中各頂點之間的鄰接關(guān)系。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)假設(shè)圖G＝(V，E)有n個頂點，則鄰接矩陣是一個n×n的方陣，定義為：arc[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第51頁。無向圖的鄰接矩陣的特點？無向圖的鄰接矩陣6.2圖的存儲結(jié)構(gòu)及實現(xiàn)V0V2V3V1V0V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3主對角線為0且一定是對稱矩陣。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第52頁。如何求頂點i的度？無向圖的鄰接矩陣6.2圖的存儲結(jié)構(gòu)及實現(xiàn)鄰接矩陣的第i行（或第i列）非零元素的個數(shù)。0101101101001100arc=V0V1V2V3V0V1V2V3V0V2V3V1V0V1V2V3vertex=數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第53頁。如何判斷頂點i和j之間是否存在邊？無向圖的鄰接矩陣6.2圖的存儲結(jié)構(gòu)及實現(xiàn)測試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。0101101101001100arc=V0V1V2V3V0V1V2V3V0V2V3V1V0V1V2V3vertex=數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第54頁。如何求頂點i的所有鄰接點？無向圖的鄰接矩陣6.2圖的存儲結(jié)構(gòu)及實現(xiàn)將數(shù)組中第i

行元素掃描一遍，若arc[i][j]為1，則頂點j

為頂點i的鄰接點。V0V2V3V10101101101001100arc=V0V1V2V3V0V1V2V3V0V1V2V3vertex=數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第55頁。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接矩陣V0V1V2V3V0V1V2V3vertex=0110000000011000arc=V0V1V2V3V0V1V2V3有向圖的鄰接矩陣一定不對稱嗎？不一定，例如有向完全圖。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第56頁。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接矩陣如何求頂點i的出度？鄰接矩陣的第i行元素之和。V0V1V2V3V0V1V2V3vertex=0110000000011000arc=V0V1V2V3V0V1V2V3數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第57頁。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接矩陣如何求頂點i的入度？鄰接矩陣的第i列元素之和。V0V1V2V3V0V1V2V3vertex=0110000000011000arc=V0V1V2V3V0V1V2V3數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第58頁。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接矩陣如何判斷從頂點i到頂點j是否存在邊？測試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。V0V1V2V3V0V1V2V3vertex=0110000000011000arc=V0V1V2V3V0V1V2V3數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第59頁。網(wǎng)圖的鄰接矩陣6.2圖的存儲結(jié)構(gòu)及實現(xiàn)網(wǎng)圖的鄰接矩陣可定義為：

arc[i][j]＝

wij

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

∞

∞

∞087∞∞0arc=數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第60頁。鄰接矩陣存儲無向圖的類constintMaxSize=10;template<classDataType>classMgraph{public:MGraph(DataTypea[],intn,inte);~MGraph()

voidDFSTraverse(intv);voidBFSTraverse(intv);private:DataTypevertex[MaxSize];intarc[MaxSize][MaxSize];intvertexNum,arcNum;};6.2圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第61頁。鄰接矩陣中圖的基本操作——構(gòu)造函數(shù)確定圖的頂點個數(shù)和邊的個數(shù)；2.輸入頂點信息存儲在一維數(shù)組vertex中；3.初始化鄰接矩陣；4.依次輸入每條邊存儲在鄰接矩陣arc中；4.1輸入邊依附的兩個頂點的序號i,j；4.2將鄰接矩陣的第i行第j列的元素值置為1；4.3將鄰接矩陣的第j行第i列的元素值置為1；6.2圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第62頁。template<classDataType>MGraph<DataType>::MGraph(DataTypea[],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;//輸入邊依附的兩個頂點的編號arc[i][j]=1;arc[j][i]=1;//置有邊標(biāo)志

}}6.2圖的存儲結(jié)構(gòu)及實現(xiàn)鄰接矩陣中圖的基本操作——構(gòu)造函數(shù)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第63頁。鄰接矩陣中圖的基本操作——深度優(yōu)先遍歷template<classDataType>voidMGraph<DataType>::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圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第64頁。鄰接矩陣中圖的基本操作——廣度優(yōu)先遍歷template<classDataType>voidMGraph<DataType>::BFSTraverse(intv){front=rear=-1;//初始化順序隊列

cout<<vertex[v];visited[v]=1;Q[++rear]=v;while(front!=rear)//當(dāng)隊列非空時

{v=Q[++front];//將隊頭元素出隊并送到v中

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圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第65頁。鄰接表鄰接表存儲的基本思想：對于圖的每個頂點vi，將所有鄰接于vi的頂點鏈成一個單鏈表，稱為頂點vi的邊表（對于有向圖則稱為出邊表），所有邊表的頭指針和存儲頂點信息的一維數(shù)組構(gòu)成了頂點表。

6.2圖的存儲結(jié)構(gòu)及實現(xiàn)圖的鄰接矩陣存儲結(jié)構(gòu)的空間復(fù)雜度？如果為稀疏圖則會出現(xiàn)什么現(xiàn)象？假設(shè)圖G有n個頂點e條邊，則存儲該圖需要O(n2)。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第66頁。鄰接表有兩種結(jié)點結(jié)構(gòu)：頂點表結(jié)點和邊表結(jié)點。vertexfirstedge

adjvex

next

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

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

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

6.2圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第67頁。structArcNode{

intadjvex;ArcNode*next;};template<classDataType>structVertexNode{

DataTypevertex;

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

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

adjvex

next數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第68頁。103∧23∧1∧01∧V0V1

V2V30123vertexfirstedge6.2圖的存儲結(jié)構(gòu)及實現(xiàn)V0V2V3V1無向圖的鄰接表邊表中的結(jié)點表示什么？每個結(jié)點對應(yīng)圖中的一條邊，鄰接表的空間復(fù)雜度為O(n+e)。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第69頁。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)無向圖的鄰接表如何求頂點i的度？頂點i的邊表中結(jié)點的個數(shù)。V0V2V3V1103∧23∧1∧01∧V0V1

V2V30123vertexfirstedge數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第70頁。如何判斷頂點i和頂點j之間是否存在邊?測試頂點i的邊表中是否存在終點為j的結(jié)點。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)無向圖的鄰接表V0V2V3V1103∧23∧1∧01∧V0V1

V2V30123vertexfirstedge數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第71頁。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接表V0V1V2V312∧3∧0∧V0V1

V2V30123vertexfirstedge∧如何求頂點i的出度？頂點i的出邊表中結(jié)點的個數(shù)。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第72頁。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接表如何求頂點i的入度？各頂點的出邊表中以頂點i為終點的結(jié)點個數(shù)。V0V1V2V312∧3∧0∧V0V1

V2V30123vertexfirstedge∧數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第73頁。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)有向圖的鄰接表如何求頂點i的所有鄰接點？遍歷頂點i的邊表，該邊表中的所有終點都是頂點i的鄰接點。V0V1V2V312∧3∧0∧V0V1

V2V30123vertexfirstedge∧數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第74頁。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)網(wǎng)圖的鄰接表V0V1V2V3278521V0V1

V2V30123vertexfirstedge∧52∧83∧70∧數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第75頁。鄰接表存儲有向圖的類constintMaxSize=10;//圖的最大頂點數(shù)template<classDataType>classALGraph{public:ALGraph(DataTypea[],intn,inte);~ALGraph;voidDFSTraverse(intv);

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

intvertexNum,arcNum;};6.2圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第76頁。鄰接表中圖的基本操作——構(gòu)造函數(shù)

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

3.3將結(jié)點s插入到第i個邊表的頭部；6.2圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第77頁。template<classDataType>ALGraph<DataType>::ALGraph(DataTypea[],intn,inte){vertexNum=n;arcNum=e;for(i=0;i<vertexNum;i++){//輸入頂點信息，初始化頂點表adjlist[i].vertex=a[i];adjlist[i].firstedge=NULL;}6.2圖的存儲結(jié)構(gòu)及實現(xiàn)鄰接表中圖的基本操作——構(gòu)造函數(shù)

數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第78頁。for(k=0;k<arcNum;k++)//輸入邊的信息存儲在邊表中{

cin>>i>>j;

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

V2V30123∧∧∧∧①②鄰接表中圖的基本操作——構(gòu)造函數(shù)

數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第79頁。鄰接表中圖的基本操作——深度優(yōu)先遍歷template<classDataType>voidALGraph<DataType>::DFSTraverse(intv){cout<<adjlist[v].vertex;visited[v]=1;p=adjlist[v].firstedge;//工作指針p指向頂點v的邊表while(p!=NULL)//依次搜索頂點v的鄰接點j{j=p->adjvex;if(visited[j]==0)DFSTraverse(j);p=p->next;}}6.2圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第80頁。鄰接表中圖的基本操作——廣度優(yōu)先遍歷template<classDataType>voidALGraph<DataType>::BFSTraverse(intv){front=rear=-1;//初始化順序隊列

cout<<adjlist[v].vertex;visited[v]=1;Q[++rear]=v;

while(front!=rear)//當(dāng)隊列非空時

{v=Q[++front];p=adjlist[v].firstarc;//工作指針p指向頂點v的邊表

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圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第81頁。十字鏈表鄰接表6.2圖的存儲結(jié)構(gòu)及實現(xiàn)逆鄰接表將鄰接表與逆鄰接表合二為一?為什么要合并？V0V1V2V312∧3∧0v0v1v2v3∧01231∧3∧0∧2∧v0v1v2v3012303∧數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第82頁。十字鏈表的結(jié)點結(jié)構(gòu)vertexfirstinfirstout頂點表結(jié)點tailvexheadvexheadlinktaillink邊表結(jié)點tailvex：弧的起點在頂點表中的下標(biāo)；headvex：弧的終點在頂點表中的下標(biāo)；headlink：入邊表指針域；taillink：出邊表指針域。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)vertex：數(shù)據(jù)域，存放頂點信息；firstin：入邊表頭指針；firstout：出邊表頭指針；數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第83頁。3031∧3210V0V1V2V323

∧0102∧6.2圖的存儲結(jié)構(gòu)及實現(xiàn)十字鏈表存儲有向圖∧∧V0V1V2V3∧∧∧v2v3v3v0v0v1v0v2v3v1數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第84頁。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)鄰接多重表存儲無向圖

ivex

ilink

jvex

jlinkvertexfirstedgea)頂點表結(jié)點(b)邊表結(jié)點vertex：數(shù)據(jù)域，存儲有關(guān)頂點的數(shù)據(jù)信息；firstedge：邊表頭指針，指向依附于該頂點的邊表；ivex、jvex：與某條邊依附的兩個頂點在頂點表中的下標(biāo)；ilink：指針域，指向依附于頂點ivex的下一條邊；jlink：指針域，指向依附于頂點jvex的下一條邊。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第85頁。6.2圖的存儲結(jié)構(gòu)及實現(xiàn)鄰接多重表存儲無向圖V0V2V3V1數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第86頁。圖的存儲結(jié)構(gòu)的比較——鄰接矩陣和鄰接表O（n2）O（n+e）O（n2）O（n+e）空間性能時間性能適用范圍唯一性鄰接矩陣鄰接表稠密圖稀疏圖唯一不唯一6.2圖的存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第87頁。生成樹的代價：設(shè)G=(V,E)是一個無向連通網(wǎng)，生成樹上各邊的權(quán)值之和稱為該生成樹的代價。

最小生成樹：在圖G所有生成樹中，代價最小的生成樹稱為最小生成樹。6.3最小生成樹最小生成樹的定義最小生成樹的概念可以應(yīng)用到許多實際問題中。例：在n個城市之間建造通信網(wǎng)絡(luò)，至少要架設(shè)n-1條通信線路，而每兩個城市之間架設(shè)通信線路的造價是不一樣的，那么如何設(shè)計才能使得總造價最小？數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第88頁。MST性質(zhì)假設(shè)G=(V,E)是一個無向連通網(wǎng)，U是頂點集V的一個非空子集。若(u,v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹。頂點集UV－Uu'vv'u頂點集T1T26.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第89頁?；舅枷耄涸O(shè)G=(V,E)是具有n個頂點的連通網(wǎng)，T=(U,TE)是G的最小生成樹，T的初始狀態(tài)為U={u0}（u0∈V），TE={}，重復(fù)執(zhí)行下述操作：在所有u∈U，v∈V-U的邊中找一條代價最小的邊(u,v)并入集合TE，同時v并入U，直至U=V。普里姆（Prim）算法

6.3最小生成樹Prim算法的基本思想用偽代碼描述如下：1.初始化：U={v0}；TE={}；2.重復(fù)下述操作直到U=V：2.1在E中尋找最短邊(u，v)，且滿足u∈U，v∈V-U；

2.2U=U+{v}；2.3TE=TE+{(u，v)}；關(guān)鍵:是如何找到連接U和V-U的最短邊。

數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第90頁。U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}251234192646381725ABEDCFPrim算法

6.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第91頁。Prim算法

251234192646381725ABEDCFU={A,F}V-U={B,C,D,E}cost={(A,B)34,(F,C)25,(F,D)25,(F,E)26}6.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第92頁。Prim算法

2512341926381725ABEDCFU={A,F,C}V-U={B,D,E}cost={(A,B)34,(C,D)17,(F,E)26}

6.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第93頁。Prim算法

12341926381725ABEDCFU={A,F,C,D}V-U={B,E}cost={(A,B)34,(F,E)26}

6.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第94頁。Prim算法

123419261725ABEDCFU={A,F,C,D,E}V-U={B}cost={(E,B)12}

6.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第95頁。Prim算法

1219261725ABEDCFU={A,F,C,D,E,B}V-U={}6.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第96頁。1.圖的存儲結(jié)構(gòu)：由于在算法執(zhí)行過程中，需要不斷讀取任意兩個頂點之間邊的權(quán)值，所以，圖采用鄰接矩陣存儲。數(shù)據(jù)結(jié)構(gòu)設(shè)計6.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第97頁。251234192646381725ABEDCF對于頂點C，只需保留min{arc[A][C],arc[F][C]}6.3最小生成樹2.候選最短邊集：設(shè)置數(shù)組shortEdge[n]表示候選最短邊集，數(shù)組元素包括adjvex和lowcost兩個域，分別表示候選最短邊的鄰接點和權(quán)值。數(shù)據(jù)結(jié)構(gòu)設(shè)計對于V-U中的每個頂點，只保留從該頂點到U中的某頂點的最短邊。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第98頁。候選最短邊(vi,vk)的權(quán)值為w，其中vi∈V-U，vk∈U：如何用lowcost和adjvex表示候選最短邊集？6.3最小生成樹shortEdge[i].adjvex=kshortEdge[i].lowcost=w數(shù)據(jù)結(jié)構(gòu)設(shè)計shortEdge[j].lowcost=min{shortEdge[j].lowcost,cost(vj，vk)}shortEdge[j].adjvex=k（如果邊(vj，vk)的權(quán)值較?。╉旤cvk從集合V-U進(jìn)入集合U后，依據(jù)下式更新數(shù)組shortEdge：數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第99頁。1.初始化兩個輔助數(shù)組lowcost和adjvex；2.輸出頂點u0，將頂點u0加入集合U中；3.重復(fù)執(zhí)行下列操作n-1次

3.1在lowcost中選取最短邊，取adjvex中對應(yīng)的頂點序號k；

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

3.3將頂點k加入集合U中；

3.4調(diào)整數(shù)組lowcost和adjvex；Prim算法——偽代碼

6.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第100頁?？唆斔箍枺↘ruskal）算法

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

6.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第101頁。克魯斯卡爾（Kruskal）算法

1.初始化：U=V；TE={}；2.重復(fù)下述操作直到T中的連通分量個數(shù)為1：2.1在E中尋找最短邊(u，v);2.2如果頂點u、v位于T的兩個不同連通分量，則

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

2.2.2將這兩個連通分量合為一個；2.3標(biāo)記邊(u，v)，使得(u，v)不參加后續(xù)最短邊的選?。?.3最小生成樹Kruskal算法的基本思想用偽代碼描述如下：關(guān)鍵：如何判別被考察邊的兩個頂點是否位于兩個連通分量數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第102頁。251234192646381725ABEDCFABEDCF連通分量＝{A},{B},{C},{D},{E},{F}6.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第103頁。251234192646381725ABEDCFABEDCF連通分量＝{A},{B},{C},{D},{E},{F}12連通分量＝{A},{B,E},{C},{D},{F}6.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第104頁。251234192646381725ABEDCFABEDCF連通分量＝{A,F},{B,E},{C},{D}12連通分量＝{A,F},{B,E},{C,D}176.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第105頁。251234192646381725ABEDCFABEDCF連通分量＝{A},{B,E},{C},{D},{F}12連通分量＝{A,F},{B,E},{C},{D}196.3最小生成樹17數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第106頁。251234192646381725ABEDCFABEDCF連通分量＝{A,F},{B,E},{C,D}12連通分量＝{A,F,C,D},{B,E}1917256.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第107頁。251234192646381725ABEDCFABEDCF連通分量＝{A,F,C,D},{B,E}12連通分量＝{A,F,C,D,B,E}191725266.3最小生成樹數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第108頁。6.3最小生成樹1.圖的存儲結(jié)構(gòu)：因為Kruskal算法是依次對圖中的邊進(jìn)行操作，因此考慮用邊集數(shù)組存儲圖中的邊，為了提高查找速度，將邊集數(shù)組按邊上的權(quán)排序。數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第109頁。6.3最小生成樹2.連通分量。Kruskal算法實質(zhì)上是使生成樹以一種隨意的方式生長，初始時每個頂點構(gòu)成一棵生成樹，然后每生長一次就將兩棵樹合并，到最后合并成一棵樹。因此，可以設(shè)置一個數(shù)組parent[n]，元素parent[i]表示頂點i的雙親結(jié)點，初始時，parent[i]=-1，表示頂點i沒有雙親，即該結(jié)點是所在生成樹的根結(jié)點；對于邊(u,v)，設(shè)vex1和vex2分別表示兩個頂點所在樹的根結(jié)點，如果vex1≠vex2，則頂點u和v必位于不同的連通分量，令parent[vex2]=vex1，實現(xiàn)將兩棵樹合并。求某頂點v所在生成樹的根結(jié)點只需沿數(shù)組v=parent[v]不斷查找v的雙親，直到parent[v]等于-1。數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第110頁。6.3最小生成樹1.初始化輔助數(shù)組parent[n]；num=0；2.依次考查每一條邊f(xié)or(i=0;i<arcNum;i++)2.1vex1=edge[i].from所在生成樹的根結(jié)點；

2.2vex2=edge[i].to所在生成樹的根結(jié)點；

2.3如果vex1!=vex2，執(zhí)行下述操作：

2.3.1parent[vex2]=vex1;2.3.2num++;2.3.3if(num==n-1)算法結(jié)束；數(shù)據(jù)結(jié)構(gòu)設(shè)計Kruskal算法用偽代碼進(jìn)一步描述為：數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第111頁。v1parent[0]=-1parent[1]=-1parent[2]=-1parent[3]=-1parent[4]=-1parent[5]=-16.3最小生成樹v5v0v4v3v2數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第112頁。v1parent[0]=-1parent[1]=-1parent[2]=-1parent[3]=-1parent[4]=1parent[5]=-16.3最小生成樹v5v0v4v3v212數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第113頁。v1parent[0]=-1parent[1]=-1parent[2]=-1parent[3]=2parent[4]=1parent[5]=-16.3最小生成樹v5v0v4v3v21712數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第114頁。v1parent[0]=-1parent[1]=-1parent[2]=-1parent[3]=2parent[4]=1parent[5]=06.3最小生成樹v5v0v4v3v2171219數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第115頁。v1parent[0]=2parent[1]=-1parent[2]=-1parent[3]=2parent[4]=1parent[5]=06.3最小生成樹v5v0v4v3v217121925數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第116頁。v1parent[0]=2parent[1]=-1parent[2]=-1parent[3]=2parent[4]=1parent[5]=06.3最小生成樹v5v0v4v3v217121925考查邊(v3,v5)，由于parent[3]=2，parent[2]=-1，則v3所在生成樹的根結(jié)點是v2，而parent[5]=0，parent[0]=2，則v5所在生成樹的根結(jié)點也是v2，故舍去此邊。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁，當(dāng)前為第117頁。v1parent[0]=2parent[1]=-1parent[2]=1parent[3]=2parent[4]=1parent[5]=06.3最小生成樹v5v0