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

第六章圖圖的邏輯結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)最小生成樹(shù)最短路徑AOV網(wǎng)與拓?fù)渑判駻OE網(wǎng)與關(guān)鍵路徑數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第1頁(yè)。歐拉1707年出生在瑞士的巴塞爾城，19歲開(kāi)始發(fā)表論文，直到76歲。幾乎每一個(gè)數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級(jí)數(shù)論的歐拉常數(shù)，變分學(xué)的歐拉方程，復(fù)變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計(jì)他一生共寫(xiě)下了886本書(shū)籍和論文，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學(xué)占28%，天文學(xué)占11%，彈道學(xué)、航海學(xué)、建筑學(xué)等占3%。歐拉對(duì)著名的哥尼斯堡七橋問(wèn)題的解答開(kāi)創(chuàng)了圖論的研究。圖論——?dú)W拉數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第2頁(yè)。能否從某個(gè)地方出發(fā)，穿過(guò)所有的橋僅一次后再回到出發(fā)點(diǎn)？哥尼斯堡七橋問(wèn)題ABCD數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第3頁(yè)。CADB七橋問(wèn)題的圖模型哥尼斯堡七橋問(wèn)題歐拉回路的判定規(guī)則：1.如果通奇數(shù)橋的地方多于兩個(gè)，則不存在歐拉回路；2.如果只有兩個(gè)地方通奇數(shù)橋，可以從這兩個(gè)地方之一出發(fā)，找到歐拉回路；3.如果沒(méi)有一個(gè)地方是通奇數(shù)橋的，則無(wú)論從哪里出發(fā)，都能找到歐拉回路。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第4頁(yè)。圖的定義6.1圖的邏輯結(jié)構(gòu)圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G=(V，E)其中：G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中頂點(diǎn)之間邊的集合。在線性表中，元素個(gè)數(shù)可以為零，稱為空表；在樹(shù)中，結(jié)點(diǎn)個(gè)數(shù)可以為零，稱為空樹(shù)；在圖中，頂點(diǎn)個(gè)數(shù)不能為零，但可以沒(méi)有邊。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第5頁(yè)。6.1圖的邏輯結(jié)構(gòu)如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是無(wú)向邊，則稱該圖為無(wú)向圖。若頂點(diǎn)vi和vj之間的邊沒(méi)有方向，則稱這條邊為無(wú)向邊，表示為(vi,vj)。若從頂點(diǎn)vi到vj的邊有方向，則稱這條邊為有向邊，表示為<vi,vj>。

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

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

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

鄰接、依附無(wú)向圖中，對(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。V0的鄰接點(diǎn)：V1、V3V1的鄰接點(diǎn)：V0、V2、V4V0V1V2V3V4數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第8頁(yè)。6.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語(yǔ)

鄰接、依附有向圖中，對(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

。

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

圖的基本術(shù)語(yǔ)

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

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

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

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

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

V0V1V2V32785哈夫曼樹(shù)中的權(quán)與網(wǎng)圖的權(quán)有何區(qū)別？7423數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第17頁(yè)。路徑：在無(wú)向圖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ù)語(yǔ)

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

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

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

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

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

且E'

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

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

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

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

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

連通分量是對(duì)無(wú)向圖的一種劃分?jǐn)?shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第24頁(yè)。強(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ù)語(yǔ)

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

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

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

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

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

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

ADTGraphData

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

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

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

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

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è)線性排列后置條件：圖保持不變endADT6.1圖的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第31頁(yè)。圖的遍歷操作圖的遍歷是在從圖中某一頂點(diǎn)出發(fā)，對(duì)圖中所有頂點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。

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

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

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

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

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

V1遍歷序列：V1V2

V2V4

V4V5

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

V1遍歷序列：V1V2

V2V4

V4V5V8

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

V1遍歷序列：V1V2

V2V4

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

V1遍歷序列：V1

V7V2V4V5V8V3

V3V6

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

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

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

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

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

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

3.3.2w=頂點(diǎn)v的下一個(gè)鄰接點(diǎn)；數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第49頁(yè)。6.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)系（邊），無(wú)法通過(guò)存儲(chǔ)位置表示這種任意的邏輯關(guān)系，所以，圖無(wú)法采用順序存儲(chǔ)結(jié)構(gòu)。如何存儲(chǔ)圖?考慮圖的定義，圖是由頂點(diǎn)和邊組成的，分別考慮如何存儲(chǔ)頂點(diǎn)、如何存儲(chǔ)邊。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第50頁(yè)。鄰接矩陣（數(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其它數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第51頁(yè)。無(wú)向圖的鄰接矩陣的特點(diǎn)？無(wú)向圖的鄰接矩陣6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)V0V2V3V1V0V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3主對(duì)角線為0且一定是對(duì)稱矩陣。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第52頁(yè)。如何求頂點(diǎn)i的度？無(wú)向圖的鄰接矩陣6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)鄰接矩陣的第i行（或第i列）非零元素的個(gè)數(shù)。0101101101001100arc=V0V1V2V3V0V1V2V3V0V2V3V1V0V1V2V3vertex=數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第53頁(yè)。如何判斷頂點(diǎn)i和j之間是否存在邊？無(wú)向圖的鄰接矩陣6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)測(cè)試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。0101101101001100arc=V0V1V2V3V0V1V2V3V0V2V3V1V0V1V2V3vertex=數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第54頁(yè)。如何求頂點(diǎn)i的所有鄰接點(diǎn)？無(wú)向圖的鄰接矩陣6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)將數(shù)組中第i

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

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

∞

∞

∞087∞∞0arc=數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第60頁(yè)。鄰接矩陣存儲(chǔ)無(wú)向圖的類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圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第61頁(yè)。鄰接矩陣中圖的基本操作——構(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)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第62頁(yè)。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;//輸入邊依附的兩個(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ù)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第63頁(yè)。鄰接矩陣中圖的基本操作——深度優(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圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第64頁(yè)。鄰接矩陣中圖的基本操作——廣度優(yōu)先遍歷template<classDataType>voidMGraph<DataType>::BFSTraverse(intv){front=rear=-1;//初始化順序隊(duì)列

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

{v=Q[++front];//將隊(duì)頭元素出隊(duì)并送到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圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第65頁(yè)。鄰接表鄰接表存儲(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)。數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第66頁(yè)。鄰接表有兩種結(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)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第67頁(yè)。structArcNode{

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

DataTypevertex;

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

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

adjvex

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

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

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

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

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

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

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

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

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

intvertexNum,arcNum;};6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第76頁(yè)。鄰接表中圖的基本操作——構(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)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第77頁(yè)。template<classDataType>ALGraph<DataType>::ALGraph(DataTypea[],intn,inte){vertexNum=n;arcNum=e;for(i=0;i<vertexNum;i++){//輸入頂點(diǎn)信息，初始化頂點(diǎn)表adjlist[i].vertex=a[i];adjlist[i].firstedge=NULL;}6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)鄰接表中圖的基本操作——構(gòu)造函數(shù)

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

cin>>i>>j;

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

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

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

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

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

{v=Q[++front];p=adjlist[v].firstarc;//工作指針p指向頂點(diǎn)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圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第81頁(yè)。十字鏈表鄰接表6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)逆鄰接表將鄰接表與逆鄰接表合二為一?為什么要合并？V0V1V2V312∧3∧0v0v1v2v3∧01231∧3∧0∧2∧v0v1v2v3012303∧數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第82頁(yè)。十字鏈表的結(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：出邊表頭指針；數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第83頁(yè)。3031∧3210V0V1V2V323

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

ivex

ilink

jvex

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

最小生成樹(shù)：在圖G所有生成樹(shù)中，代價(jià)最小的生成樹(shù)稱為最小生成樹(shù)。6.3最小生成樹(shù)最小生成樹(shù)的定義最小生成樹(shù)的概念可以應(yīng)用到許多實(shí)際問(wèn)題中。例：在n個(gè)城市之間建造通信網(wǎng)絡(luò)，至少要架設(shè)n-1條通信線路，而每?jī)蓚€(gè)城市之間架設(shè)通信線路的造價(jià)是不一樣的，那么如何設(shè)計(jì)才能使得總造價(jià)最小？數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第88頁(yè)。MST性質(zhì)假設(shè)G=(V,E)是一個(gè)無(wú)向連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹(shù)。頂點(diǎn)集UV－Uu'vv'u頂點(diǎn)集T1T26.3最小生成樹(shù)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第89頁(yè)。基本思想：設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的連通網(wǎng)，T=(U,TE)是G的最小生成樹(shù)，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。普里姆（Prim）算法

6.3最小生成樹(shù)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頁(yè)，當(dāng)前為第90頁(yè)。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ù)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第91頁(yè)。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ù)數(shù)據(jù)結(jié)構(gòu)-第6章-圖全文共167頁(yè)，當(dāng)前為第92頁(yè)。Prim算法

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

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

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

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

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

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

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

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

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

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

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

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

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