數(shù)據(jù)結(jié)構(gòu)圖論部分

數(shù)據(jù)結(jié)構(gòu)圖論部分第一頁，共一百九十一頁，編輯于2023年，星期三學(xué)習(xí)目標(biāo)領(lǐng)會(huì)圖的類型定義。熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及其選用原則。熟練掌握?qǐng)D的兩種遍歷算法。理解各種圖的應(yīng)用問題的算法。重點(diǎn)和難點(diǎn)重點(diǎn)：圖的各種應(yīng)用問題的算法都比較經(jīng)典，注意理解各種圖的算法及其應(yīng)用場合。第二頁，共一百九十一頁，編輯于2023年，星期三2023/6/102知識(shí)點(diǎn)圖的類型定義圖的存儲(chǔ)表示圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷無向網(wǎng)的最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑第三頁，共一百九十一頁，編輯于2023年，星期三2023/6/103歐拉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拉第四頁，共一百九十一頁，編輯于2023年，星期三2023/6/104能否從某個(gè)地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點(diǎn)？哥尼斯堡七橋問題

第五頁，共一百九十一頁，編輯于2023年，星期三2023/6/105CADB七橋問題的圖模型歐拉回路的判定規(guī)則：1.如果通奇數(shù)橋的地方多于兩個(gè)，則不存在歐拉回路；2.如果只有兩個(gè)地方通奇數(shù)橋，可以從這兩個(gè)地方之一出發(fā)，找到歐拉回路；3.如果沒有一個(gè)地方是通奇數(shù)橋的，則無論從哪里出發(fā)，都能找到歐拉回路。第六頁，共一百九十一頁，編輯于2023年，星期三2023/6/106圖的定義圖是由頂點(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ù)不能為零，但可以沒有邊。7.1圖的定義和術(shù)語第七頁，共一百九十一頁，編輯于2023年，星期三2023/6/107線性表每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。樹形結(jié)構(gòu)每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼。圖形結(jié)構(gòu)每個(gè)數(shù)據(jù)元素可能有多個(gè)直接前驅(qū)和多個(gè)直接后繼。圖是比線性表和樹復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于語言學(xué)、邏輯學(xué)、物理、化學(xué)等領(lǐng)域。第八頁，共一百九十一頁，編輯于2023年，星期三2023/6/108如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是無向邊，則稱該圖為無向圖。若頂點(diǎn)vi和vj之間的邊沒有方向，則稱這條邊為無向邊，表示為(vi,vj)。若從頂點(diǎn)vi到vj的邊有方向，則稱這條邊為有向邊，表示為<vi,vj>。

如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是有向邊，則稱該圖為有向圖。V1V2V3V4V5V1V2V3V4圖的基本術(shù)語

第九頁，共一百九十一頁，編輯于2023年，星期三2023/6/109簡單圖：在圖中，若不存在頂點(diǎn)到其自身的邊，且同一條邊不重復(fù)出現(xiàn)。V3V4V5V1V2V3V4V5V1V2非簡單圖非簡單圖簡單圖V1V2V3V4V5

數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖。第十頁，共一百九十一頁，編輯于2023年，星期三2023/6/1010圖的基本術(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、V5第十一頁，共一百九十一頁，編輯于2023年，星期三2023/6/1011圖的基本術(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第十二頁，共一百九十一頁，編輯于2023年，星期三2023/6/1012無向完全圖：在無向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無向完全圖。有向完全圖：在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向相反的兩條弧，則稱該圖為有向完全圖。

圖的基本術(shù)語

V1V2V3V1V2V3V4第十三頁，共一百九十一頁，編輯于2023年，星期三2023/6/1013含有n個(gè)頂點(diǎn)的無向完全圖有多少條邊？含有n個(gè)頂點(diǎn)的有向完全圖有多少條??？

含有n個(gè)頂點(diǎn)的無向完全圖有n×(n-1)/2條邊。含有n個(gè)頂點(diǎn)的有向完全圖有n×(n-1)條邊。V1V2V3V1V2V3V4第十四頁，共一百九十一頁，編輯于2023年，星期三2023/6/1014稀疏圖：稱邊數(shù)很少的圖為稀疏圖；稠密圖：稱邊數(shù)很多的圖為稠密圖。頂點(diǎn)的度：在無向圖中，頂點(diǎn)v的度是指依附于該頂點(diǎn)的邊數(shù)，通常記為TD(v)。圖的基本術(shù)語

頂點(diǎn)的入度：在有向圖中，頂點(diǎn)v的入度是指以該頂點(diǎn)為弧頭的弧的數(shù)目，記為ID(v)；頂點(diǎn)的出度：在有向圖中，頂點(diǎn)v的出度是指以該頂點(diǎn)為弧尾的弧的數(shù)目，記為OD(v)。第十五頁，共一百九十一頁，編輯于2023年，星期三2023/6/1015V1V2V3V4V5圖的基本術(shù)語

在具有n個(gè)頂點(diǎn)、e條邊的無向圖G中，各頂點(diǎn)的度之和與邊數(shù)之和的關(guān)系？?==niievTD12)(第十六頁，共一百九十一頁，編輯于2023年，星期三2023/6/1016V1V2V3V4圖的基本術(shù)語

在具有n個(gè)頂點(diǎn)、e條邊的有向圖G中，各頂點(diǎn)的入度之和與各頂點(diǎn)的出度之和的關(guān)系？與邊數(shù)之和的關(guān)系？evODvIDiiii==??==11)()(nn第十七頁，共一百九十一頁，編輯于2023年，星期三2023/6/1017權(quán)：是指對(duì)邊賦予的有意義的數(shù)值量。網(wǎng)：邊上帶權(quán)的圖，也稱網(wǎng)圖。圖的基本術(shù)語

V1V2V3V42785第十八頁，共一百九十一頁，編輯于2023年，星期三2023/6/1018路徑：在無向圖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。圖的基本術(shù)語

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

V1V2V3V4V1V2V5V3V4第十九頁，共一百九十一頁，編輯于2023年，星期三2023/6/1019路徑長度：圖的基本術(shù)語

非帶權(quán)圖——路徑上邊的個(gè)數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V1V2V3V4V5V1V4：長度為1V1V2V3V4：長度為3V1V2V5V3V4：長度為4第二十頁，共一百九十一頁，編輯于2023年，星期三2023/6/1020路徑長度：圖的基本術(shù)語

非帶權(quán)圖——路徑上邊的個(gè)數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V1V4：長度為8V1V2V3V4：長度為7V1V2V5V3V4：長度為15V1V2V3V4V5256328第二十一頁，共一百九十一頁，編輯于2023年，星期三2023/6/1021回路（環(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)的回路。圖的基本術(shù)語

V1V2V3V4V5V1V2V3V4第二十二頁，共一百九十一頁，編輯于2023年，星期三2023/6/1022子圖：若圖G=（V，E），G'=（V'，E'），如果V'V且E'

E，則稱圖G'是G的子圖。圖的基本術(shù)語

V1V2V3V4V5V1V2V3V4V5V1V3V4第二十三頁，共一百九十一頁，編輯于2023年，星期三2023/6/1023連通圖：在無向圖中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(i≠j)有路徑，則稱頂點(diǎn)vi和vj是連通的。如果圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱該圖是連通圖。連通分量：非連通圖的極大連通子圖稱為連通分量。

圖的基本術(shù)語

如何求得一個(gè)非連通圖的連通分量?1.含有極大頂點(diǎn)數(shù)；2.依附于這些頂點(diǎn)的所有邊。第二十四頁，共一百九十一頁，編輯于2023年，星期三2023/6/1024連通分量1

V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量2圖的基本術(shù)語

連通分量是對(duì)無向圖的一種劃分。第二十五頁，共一百九十一頁，編輯于2023年，星期三2023/6/1025強(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)連通子圖。

圖的基本術(shù)語

如何求得一個(gè)非連通圖的連通分量?第二十六頁，共一百九十一頁，編輯于2023年，星期三2023/6/1026圖的基本術(shù)語

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

強(qiáng)連通分量2V1V3V4V2第二十七頁，共一百九十一頁，編輯于2023年，星期三2023/6/1027生成樹：n個(gè)頂點(diǎn)的連通圖G的生成樹是包含G中全部頂點(diǎn)的一個(gè)極小連通子圖。

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

如何理解極小連通子圖?圖的基本術(shù)語

多——構(gòu)成回路少——不連通含有n-1條邊第二十八頁，共一百九十一頁，編輯于2023年，星期三2023/6/1028V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成樹生成森林第二十九頁，共一百九十一頁，編輯于2023年，星期三2023/6/1029圖的抽象數(shù)據(jù)類型定義如下：ADTGraph{數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂

點(diǎn)集。數(shù)據(jù)關(guān)系R：

R={VR}

VR＝{<v,w>|v,w∈V且P(v,w)，<v,w>表示從v到w的

弧，謂詞P(v,w)定義了弧<v,w>的意義

或信息}第三十頁，共一百九十一頁，編輯于2023年，星期三2023/6/1030G1=(V1,VR1)V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,

<D,B>,<D,A>,<E,C>}G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),

(D,F),(B,F),(C,F)}第三十一頁，共一百九十一頁，編輯于2023年，星期三2023/6/1031

CreateGraph(&G,V,VR);

初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。

操作結(jié)果：按V和VR的定義構(gòu)造圖G。

DestroyGraph(&G);

初始條件：圖G存在。

操作結(jié)果：銷毀圖G。

LocateVex(G,u);

初始條件：圖G存在，u和G中頂點(diǎn)有相同特征。

操作結(jié)果：若G中存在和u相同的頂點(diǎn)，則返回該頂點(diǎn)

在圖中位置；否則返回其它信息。 第三十二頁，共一百九十一頁，編輯于2023年，星期三2023/6/1032 GetVex(G,v);

初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。

操作結(jié)果：返回v的值。 FirstAdjVex(G,v);

初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。

操作結(jié)果：返回v的第一個(gè)鄰接點(diǎn)。若該頂點(diǎn)在G中沒

有鄰接點(diǎn)，則返回“空”。

NextAdjVex(G,v,w);

初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的

鄰接頂點(diǎn)。

操作結(jié)果：返回v的（相對(duì)于w的）下一個(gè)鄰接點(diǎn)。若

w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”。第三十三頁，共一百九十一頁，編輯于2023年，星期三2023/6/1033

PutVex(&G,v,value);

初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。

操作結(jié)果：對(duì)v賦值value。

InsertVex(&G,v);

初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征。

操作結(jié)果：在圖G中增添新頂點(diǎn)v。

DeleteVex(&G,v);

初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。

操作結(jié)果：刪除G中頂點(diǎn)v及其相關(guān)的弧。第三十四頁，共一百九十一頁，編輯于2023年，星期三2023/6/1034 InsertArc(&G,v,w);

初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。

操作結(jié)果：在G中增添弧<v,w>，若G是無向的，則還

增添對(duì)稱弧<w,v>。 DeleteArc(&G,v,w);

初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。

操作結(jié)果：在G中刪除弧<v,w>，若G是無向的，則還

刪除對(duì)稱弧<w,v>。第三十五頁，共一百九十一頁，編輯于2023年，星期三2023/6/1035 DFSTraverse(G,Visit());

初始條件：圖G存在，Visit是頂點(diǎn)的應(yīng)用函數(shù)。

操作結(jié)果：對(duì)圖G進(jìn)行深度優(yōu)先遍歷。遍歷過程中對(duì)每

個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦

visit()失敗，則操作失敗。

FSTraverse(G,Visit());

初始條件：圖G存在，Visit是頂點(diǎn)的應(yīng)用函數(shù)。

操作結(jié)果：對(duì)圖G進(jìn)行廣度優(yōu)先遍歷。遍歷過程中對(duì)每

個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦

visit()失敗，則操作失敗。}ADTGraph第三十六頁，共一百九十一頁，編輯于2023年，星期三2023/6/1036是否可以采用順序存儲(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ǔ)邊。7.2圖的存儲(chǔ)結(jié)構(gòu)第三十七頁，共一百九十一頁，編輯于2023年，星期三2023/6/10377.2圖的存儲(chǔ)結(jié)構(gòu)數(shù)組表示法(鄰接矩陣)將圖的頂點(diǎn)信息存儲(chǔ)在一個(gè)一維數(shù)組中，并將它的鄰接矩陣存儲(chǔ)在一個(gè)二維數(shù)組中即構(gòu)成圖的數(shù)組表示。假設(shè)圖中頂點(diǎn)數(shù)為n，則鄰接矩陣A定義為網(wǎng)的鄰接矩陣的定義為，當(dāng)vi到vj有弧相鄰接時(shí)，aij的值應(yīng)為該弧上的權(quán)值，否則為∞。第三十八頁，共一百九十一頁，編輯于2023年，星期三2023/6/1038圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示#defineINFINITY INT_MAX; //最大值∞#defineMAX_VERTEX_NUM 20; //最大頂點(diǎn)個(gè)數(shù)typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向圖,有向網(wǎng),無向圖,無向網(wǎng)}typedefstructArcCell{

VRType adj; //VRType是頂點(diǎn)關(guān)系類型。對(duì)無權(quán)圖，用1或0

//表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型。

InfoType *info; //該弧相關(guān)信息的指針

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{

VertexType vexs[MAX_VERTEX_NUM]; //頂點(diǎn)信息

AdjMatrix arcs; //鄰接矩陣

int vexnum,arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù)

GraphKind kind; //圖的種類標(biāo)志

}MGraph;第三十九頁，共一百九十一頁，編輯于2023年，星期三2023/6/1039有向圖的存儲(chǔ)結(jié)構(gòu)G1BDACG1.vexs=[A,B,C,D]G1.vexnum=4G1.arcnum=4G1.kind=DG第四十頁，共一百九十一頁，編輯于2023年，星期三2023/6/1040有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求頂點(diǎn)i的出度？鄰接矩陣的第i行元素之和。第四十一頁，共一百九十一頁，編輯于2023年，星期三2023/6/1041有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求頂點(diǎn)i的入度？鄰接矩陣的第i列元素之和。第四十二頁，共一百九十一頁，編輯于2023年，星期三2023/6/1042有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何判斷從頂點(diǎn)i到頂點(diǎn)j是否存在邊？測試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。第四十三頁，共一百九十一頁，編輯于2023年，星期三2023/6/1043無向圖的存儲(chǔ)結(jié)構(gòu)AECBDG2G2.vexs=[A,B,C,D,E]G2.vexnum=5G2.arcnum=6G2.kind=UDG第四十四頁，共一百九十一頁，編輯于2023年，星期三2023/6/1044網(wǎng)圖的存儲(chǔ)結(jié)構(gòu)ADEBC75318642G3G3.vexs=[A,B,C,D,E]G3.vexnum=5G3.arcnum=8G3.kind=UDN第四十五頁，共一百九十一頁，編輯于2023年，星期三2023/6/1045如何求頂點(diǎn)i的度？無向圖的鄰接矩陣V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4鄰接矩陣的第i行（或第i列）非零元素的個(gè)數(shù)。第四十六頁，共一百九十一頁，編輯于2023年，星期三2023/6/1046如何判斷頂點(diǎn)i和j之間是否存在邊？無向圖的鄰接矩陣V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4測試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。第四十七頁，共一百九十一頁，編輯于2023年，星期三2023/6/1047如何求頂點(diǎn)i的所有鄰接點(diǎn)？無向圖的鄰接矩陣V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4將數(shù)組中第i行元素掃描一遍，若arc[i][j]為1，則頂點(diǎn)j為頂點(diǎn)i的鄰接點(diǎn)。第四十八頁，共一百九十一頁，編輯于2023年，星期三2023/6/1048特點(diǎn)：無向圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無向圖需存儲(chǔ)空間為n(n+1)/2。有向圖鄰接矩陣不一定對(duì)稱；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n2。無向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和。有向圖中，頂點(diǎn)Vi的出度是A中第i行元素之和。頂點(diǎn)Vi的入度是A中第i列元素之和。鄰接矩陣的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：容易判定頂點(diǎn)間有無邊（?。┖陀?jì)算頂點(diǎn)的度（出度、

入度）。缺點(diǎn)：邊數(shù)較少時(shí)，空間浪費(fèi)較大。第四十九頁，共一百九十一頁，編輯于2023年，星期三2023/6/1049網(wǎng)圖的鄰接矩陣網(wǎng)圖的鄰接矩陣可定義為：

arc[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他V1V2V3V42785025∞∞0∞∞∞∞087∞∞0arc=第五十頁，共一百九十一頁，編輯于2023年，星期三2023/6/10507.2.2圖的鄰接表表示法引入原因鄰接矩陣在稀疏圖時(shí)空間浪費(fèi)較大。實(shí)現(xiàn)為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（有向圖中指以Vi為尾的?。?。每個(gè)鏈表附設(shè)一個(gè)表頭結(jié)點(diǎn)。表結(jié)點(diǎn)adjvexnextarcinfo與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置頭結(jié)點(diǎn)datafirstarc第五十一頁，共一百九十一頁，編輯于2023年，星期三2023/6/1051圖的鄰接表存儲(chǔ)表示#defineMAX_VERTEX_NUM20;typedefstructArcNode{

int adjvex;//該弧所指向的頂點(diǎn)的位置

structArcNode *nextarc;//指向下一條弧的指針

InfoType *info;//該弧相關(guān)信息的指針

}ArcNode;typedefstructVNode{

VertexType data;//頂點(diǎn)信息

ArcNode *firstarc;//指向第一條依附該頂點(diǎn)的弧

}AdjList[MAX_VERTEX_NUM];typedefstruct{

AdjListvertices;//頂點(diǎn)數(shù)組

intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)

intkind; //圖的種類標(biāo)志

}ALGraph;第五十二頁，共一百九十一頁，編輯于2023年，星期三2023/6/1052103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2無向圖的鄰接表邊表中的結(jié)點(diǎn)表示什么？每個(gè)結(jié)點(diǎn)對(duì)應(yīng)圖中的一條邊，鄰接表的空間復(fù)雜度為O(n+e)。第五十三頁，共一百九十一頁，編輯于2023年，星期三2023/6/1053103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2無向圖的鄰接表如何求頂點(diǎn)i的度？頂點(diǎn)i的邊表中結(jié)點(diǎn)的個(gè)數(shù)。第五十四頁，共一百九十一頁，編輯于2023年，星期三2023/6/1054如何判斷頂點(diǎn)i和頂點(diǎn)j之間是否存在邊?測試頂點(diǎn)i的邊表中是否存在終點(diǎn)為j的結(jié)點(diǎn)。103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2無向圖的鄰接表第五十五頁，共一百九十一頁，編輯于2023年，星期三2023/6/1055有向圖的鄰接表V1V2V3V412∧2∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點(diǎn)i的出度？頂點(diǎn)i的出邊表中結(jié)點(diǎn)的個(gè)數(shù)。第五十六頁，共一百九十一頁，編輯于2023年，星期三2023/6/1056有向圖的鄰接表V1V2V3V412∧2∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點(diǎn)i的入度？各頂點(diǎn)的出邊表中以頂點(diǎn)i為終點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)。第五十七頁，共一百九十一頁，編輯于2023年，星期三2023/6/1057有向圖的鄰接表V1V2V3V412∧3∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點(diǎn)i的所有鄰接點(diǎn)？遍歷頂點(diǎn)i的邊表，該邊表中的所有終點(diǎn)都是頂點(diǎn)i的鄰接點(diǎn)。第五十八頁，共一百九十一頁，編輯于2023年，星期三2023/6/1058網(wǎng)圖的鄰接表V1V2V3V4278521V1V2

V3V40123vertexfirstedge∧52∧83∧70∧第五十九頁，共一百九十一頁，編輯于2023年，星期三2023/6/1059優(yōu)缺點(diǎn)優(yōu)點(diǎn)：空間較??；無向圖容易求各頂點(diǎn)的度；有向圖容易求頂點(diǎn)的出度；缺點(diǎn)：求有向圖頂點(diǎn)的入度則不容易，要遍歷整個(gè)表。為了求頂點(diǎn)的入度，有時(shí)可設(shè)逆鄰接表（指向某頂點(diǎn)的鄰接點(diǎn)鏈接成單鏈表）。bdac0123acdbdatafirstarc30^0^^2^adjvexnext逆鄰接表第六十頁，共一百九十一頁，編輯于2023年，星期三2023/6/10607.2.3圖的十字鏈表表示法引入原因?qū)τ谕粋€(gè)有向圖需要同時(shí)用鄰接表和逆鄰接表時(shí)，不方便。實(shí)現(xiàn)將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個(gè)結(jié)點(diǎn)表示，由于在鄰接表和逆鄰接表中的頂點(diǎn)數(shù)據(jù)是相同的，則在十字鏈表中只需要出現(xiàn)一次，但需保留分別指向第一條"出弧"和第一條"入弧"的指針。G1bdac0123acdbdatafirstarc2130^^^^adjvexnext鄰接表第六十一頁，共一百九十一頁，編輯于2023年，星期三2023/6/10617.2.3圖的十字鏈表表示法引入原因?qū)τ谕粋€(gè)有向圖需要同時(shí)用鄰接表和逆鄰接表時(shí)，不方便。實(shí)現(xiàn)將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個(gè)結(jié)點(diǎn)表示，由于在鄰接表和逆鄰接表中的頂點(diǎn)數(shù)據(jù)是相同的，則在十字鏈表中只需要出現(xiàn)一次，但需保留分別指向第一條"出弧"和第一條"入弧"的指針。G1bdac逆鄰接表0123acdbdatafirstarc30^0^^2^adjvexnext第六十二頁，共一百九十一頁，編輯于2023年，星期三2023/6/1062弧結(jié)點(diǎn)tailvexheadvexhlinktlinkinfo頂點(diǎn)結(jié)點(diǎn)datafirstinfirstout弧尾位置弧頭位置弧尾相同的下一條弧指針弧相關(guān)信息的指針弧頭相同的下一條弧指針指向該頂點(diǎn)第一條入弧指向該頂點(diǎn)第一條出弧第六十三頁，共一百九十一頁，編輯于2023年，星期三2023/6/106302012320323130bdacabcd0123^^^^^^^^求結(jié)點(diǎn)的入度和出度的方法？第六十四頁，共一百九十一頁，編輯于2023年，星期三2023/6/10647.2.4圖的鄰接多重表表示法引入原因無向圖的鄰接表中每一條邊有兩個(gè)結(jié)點(diǎn)，給對(duì)圖的邊進(jìn)行訪問的操作帶來不便。有些時(shí)候需要同時(shí)找到表示同一條邊的兩個(gè)結(jié)點(diǎn)（如刪除一條邊）。aecbd0123acdbdatafirstarc3101^^^adjvexnext4e324^04212^第六十五頁，共一百九十一頁，編輯于2023年，星期三2023/6/1065實(shí)現(xiàn)每條邊用一個(gè)結(jié)點(diǎn)表示。邊結(jié)點(diǎn)markivexilinkjvexjlinkinfo頂點(diǎn)結(jié)點(diǎn)markfirstedge訪問標(biāo)記邊依附的一個(gè)頂點(diǎn)邊依附的另一個(gè)頂點(diǎn)依附這個(gè)頂點(diǎn)的下一條邊指針依附這個(gè)頂點(diǎn)的下一條邊指針訪問標(biāo)記指向第一條依附該頂點(diǎn)的邊第六十六頁，共一百九十一頁，編輯于2023年，星期三2023/6/1066aecbd0123acdb4e010323212441^^^^^第六十七頁，共一百九十一頁，編輯于2023年，星期三2023/6/10677.3圖的遍歷圖的遍歷從圖中某一頂點(diǎn)出發(fā)，訪問圖中其余頂點(diǎn)，使每個(gè)頂點(diǎn)被訪問一次且只被訪問一次?？梢詮膱D中任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷。遍歷中需解決的問題確定一搜索路徑；確保每個(gè)頂點(diǎn)被訪問到；確保每個(gè)頂點(diǎn)只能被訪問一次。解決方法深度優(yōu)先和廣度優(yōu)先。設(shè)輔助數(shù)組visited，初始時(shí)，數(shù)組元素的值均為0或false，表示未被遍歷，一旦遍歷，就置為1或true。第六十八頁，共一百九十一頁，編輯于2023年，星期三2023/6/10687.3.1深度優(yōu)先搜索方法從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)；然后依次從V0的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。訪問任意一個(gè)與V0鄰接的頂點(diǎn)W1，再從W1出發(fā)；訪問與W1鄰接且未被訪問過的任意頂點(diǎn)W2，再從W2出發(fā)；重復(fù)以上過程，直到一個(gè)所有鄰接點(diǎn)都被訪問過的頂點(diǎn)為止；退回到尚有鄰接點(diǎn)未被訪問過的頂點(diǎn)，再從該頂點(diǎn)出發(fā)；直到所有的被訪問過的頂點(diǎn)的鄰接點(diǎn)都已被訪問過為止。第六十九頁，共一百九十一頁，編輯于2023年，星期三2023/6/1069深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5

V5第七十頁，共一百九十一頁，編輯于2023年，星期三2023/6/1070深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8

V8第七十一頁，共一百九十一頁，編輯于2023年，星期三2023/6/1071深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1圖的邏輯結(jié)構(gòu)V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8第七十二頁，共一百九十一頁，編輯于2023年，星期三2023/6/1072深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1

V7V2V4V5V8V3

V3V6

V6V7第七十三頁，共一百九十一頁，編輯于2023年，星期三2023/6/1073深度優(yōu)先遍歷算法7.4、7.5Boolenvisited[MAX]; //訪問標(biāo)志數(shù)組Status(*visitFunc)(intv); //函數(shù)變量voidDFSTraverse(GraphG,Status(*visit)(intv)){

//對(duì)圖G作深度優(yōu)先遍歷 visitFunc=visit; //使用全局變量visitFunc，

//使DFS不必設(shè)函數(shù)指針參數(shù) for(v=0;v<G.vexnum;++v)

visited[v]=FALSE; //訪問標(biāo)識(shí)數(shù)組初始化 for(v=0;v<G.vexnum;++v)

if(!visited[v])DFS(G,v); //對(duì)尚未訪問的

//頂點(diǎn)調(diào)用DFS}第七十四頁，共一百九十一頁，編輯于2023年，星期三2023/6/1074voidDFS(GraphG,intv){

//從第v個(gè)頂點(diǎn)出發(fā)遞歸地對(duì)圖G進(jìn)行深度優(yōu)先搜索 visitFunc(v); //訪問第v個(gè)頂點(diǎn) visited[v]=TRUE; //設(shè)訪問標(biāo)志 for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(!visited[w])DFS(G,w); //對(duì)v的尚未訪問過的鄰接

//頂點(diǎn)w遞歸調(diào)用DFS}//DFS第七十五頁，共一百九十一頁，編輯于2023年，星期三2023/6/1075V1V2V4V5V3V7V6V8深度遍歷：V10123V1V3V4V2datafirstarc1672^^^adjvexnext4V5530^40171^V6V7V8567625243^^^V3V7V6V2V5V8V4第七十六頁，共一百九十一頁，編輯于2023年，星期三2023/6/1076V1V2V4V5V3V7V6V80123V1V3V4V2datafirstarc1672^^^adjvexnext4V55^371^V6V7V85676^^^深度遍歷：V1V3V7V6V2V4V8V5第七十七頁，共一百九十一頁，編輯于2023年，星期三2023/6/10777.3.2廣度優(yōu)先搜索方法從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依次訪問V0的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。廣度優(yōu)先遍歷的過程是以v為起始點(diǎn)，由近至遠(yuǎn)，依次訪問和v有路徑相通且最短路徑長度為1,2,…的頂點(diǎn)。第七十八頁，共一百九十一頁，編輯于2023年，星期三2023/6/1078廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V1第七十九頁，共一百九十一頁，編輯于2023年，星期三2023/6/1079廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V3第八十頁，共一百九十一頁，編輯于2023年，星期三2023/6/1080廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V5第八十一頁，共一百九十一頁，編輯于2023年，星期三2023/6/1081廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V7第八十二頁，共一百九十一頁，編輯于2023年，星期三2023/6/1082廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V8第八十三頁，共一百九十一頁，編輯于2023年，星期三2023/6/1083V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V1V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V1第八十四頁，共一百九十一頁，編輯于2023年，星期三2023/6/1084廣度優(yōu)先遍歷算法7.6voidBFSTraverse(GraphG,Status(*visit)(intv)){

//對(duì)圖G進(jìn)行廣度優(yōu)先搜索遍歷 for(v=0;v<G.vexnum;++v)visited[v]=FALSE; InitQueue(Q); //設(shè)置空隊(duì)列Q for(v=0;v<G.vexnum;++v) if(!visited[v]){ //v未被訪問

visited[v]=TRUE;Visit(v); //訪問v

EnQueue(Q,v); //v入隊(duì)列

while(!QueueEmpty(Q)){

DeQueue(Q,u); //隊(duì)頭元素出隊(duì)并置為u

for(w=FirstAdjVex(G,u);w>=0;w=NextAjdVex(G,u,w))

if(!visited[w]){

visited[w]=TRUE;Visit(w);//訪問第w個(gè)頂點(diǎn)

EnQueue(Q,w);

}//if

}//while

}//ifDestroyQueue(Q);}//BFSTraverse1

2

3

4

5

6

7

8

9

10

11

12第八十五頁，共一百九十一頁，編輯于2023年，星期三2023/6/10851423501231342datafirstarc4432^^^adjvexnext450^40032^11第八十六頁，共一百九十一頁，編輯于2023年，星期三2023/6/10867·4圖的連通性問題7.4.1無向圖的連通分量和生成樹無向圖的連通分量對(duì)于連通圖，僅需從圖中任一頂點(diǎn)出發(fā)，進(jìn)行DFS或BFS搜索，即可遍歷圖的全部頂點(diǎn)；對(duì)于非連通圖，則需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行DFS或BFS搜索，才能遍歷完圖的全部頂點(diǎn)。每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行DFS或BFS搜索過程中所得的頂點(diǎn)訪問序列就是各連通分量的頂點(diǎn)集。第八十七頁，共一百九十一頁，編輯于2023年，星期三2023/6/1087ABLMCFDEGHKIJ鄰接表1211109876543210MLKJIHGFEDCBA1152112004301087106612117612901191第八十八頁，共一百九十一頁，編輯于2023年，星期三2023/6/1088深度優(yōu)先遍歷的結(jié)果為(3次DFS過程)從A出發(fā)：ALMJBFC從D出發(fā)：DE從G出發(fā)：GKHI連通分量：三個(gè)頂點(diǎn)集+依附于這個(gè)頂點(diǎn)集中頂點(diǎn)的邊。DEGHKIABLMCFJ第八十九頁，共一百九十一頁，編輯于2023年，星期三2023/6/1089生成樹所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖稱為生成樹。一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊；一個(gè)圖可以有許多棵不同的生成樹。對(duì)于連通圖，調(diào)用DFS所經(jīng)過的邊的集合和圖的全部頂點(diǎn)構(gòu)成了圖的極小連通子圖，即連通圖的一棵深度優(yōu)先生成樹。對(duì)于連通圖，調(diào)用BFS所經(jīng)過的邊的集合和圖的全部頂點(diǎn)構(gòu)成了圖的極小連通子圖，即連通圖的一棵廣度優(yōu)先生成樹。對(duì)于非連通圖，每個(gè)連通分量的頂點(diǎn)集和所經(jīng)過的邊一起構(gòu)成若干棵生成樹，這些連通圖的生成樹構(gòu)成非連通圖的生成森林。第九十頁，共一百九十一頁，編輯于2023年，星期三2023/6/1090V1V2V4V5V3V7V6V8V7V6V3V5V8V4V2V1深度遍歷V1V2V4V5V3V7V6V8深度優(yōu)先生成樹第九十一頁，共一百九十一頁，編輯于2023年，星期三2023/6/1091V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V1廣度遍歷V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹第九十二頁，共一百九十一頁，編輯于2023年，星期三2023/6/1092ABLMCFDEGHKIJ深度優(yōu)先遍歷： ALMJBFC

DE

GKHIABLMCFJDEGHKI深度優(yōu)先生成森林第九十三頁，共一百九十一頁，編輯于2023年，星期三2023/6/10937.4.2最小生成樹問題描述用一個(gè)連通網(wǎng)表示n個(gè)居民點(diǎn)和各個(gè)居民點(diǎn)之間可能架設(shè)的通訊線路，網(wǎng)中邊上的權(quán)值表示架設(shè)這條線路所需經(jīng)費(fèi)。在n個(gè)居民點(diǎn)間構(gòu)建通訊網(wǎng)只需架設(shè)n-1條線路，則工程隊(duì)面臨的問題是架設(shè)哪幾條線路能使總的工程費(fèi)用最低？問題均等價(jià)于：在含有n個(gè)頂點(diǎn)的連通網(wǎng)中選擇n-1條邊，構(gòu)成一棵極小連通子圖，并使該連通子圖中n-1條邊上權(quán)值之和達(dá)到最小，則稱這棵連通子圖為連通網(wǎng)的最小生成樹。類似此類的問題很多。16543271317918127524101654327139510第九十四頁，共一百九十一頁，編輯于2023年，星期三2023/6/1094MST性質(zhì)假設(shè)G=(V,E)是一個(gè)無向連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹。頂點(diǎn)集UV－Uu'vv'u頂點(diǎn)集T1T2第九十五頁，共一百九十一頁，編輯于2023年，星期三2023/6/1095構(gòu)造最小生成樹方法方法一：克魯斯卡爾(Kruskal)算法基本思想為使生成樹上總的權(quán)值之和達(dá)到最小，則應(yīng)使每一條邊上的權(quán)值盡可能地小，自然應(yīng)從權(quán)值最小的邊選起，直至選出n-1條互不構(gòu)成回路的權(quán)值最小邊為止。具體作法初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V,{})，每個(gè)頂點(diǎn)自成一個(gè)連通分量；在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊；依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止。第九十六頁，共一百九十一頁，編輯于2023年，星期三2023/6/1096251234162646381725ABEDCFABEDCF連通分量＝{A},{B},{C},{D},{E},{F}第九十七頁，共一百九十一頁，編輯于2023年，星期三2023/6/1097251234162646381725ABEDCFABEDCF連通分量＝{A},{B},{C},{D},{E},{F}12連通分量＝{A},{B,E},{C},{D},{F}第九十八頁，共一百九十一頁，編輯于2023年，星期三2023/6/1098251234162646381725ABEDCFABEDCF連通分量＝{A},{B,E},{C},{D},{F}12連通分量＝{A,F},{B,E},{C},{D}16第九十九頁，共一百九十一頁，編輯于2023年，星期三2023/6/1099251234162646381725ABEDCFABEDCF連通分量＝{A,F},{B,E},{C},{D}12連通分量＝{A,F},{B,E},{C,D}1617第一百頁，共一百九十一頁，編輯于2023年，星期三2023/6/10100251234162646381725ABEDCFABEDCF連通分量＝{A,F},{B,E},{C,D}12連通分量＝{A,F,C,D},{B,E}161725第一百零一頁，共一百九十一頁，編輯于2023年，星期三2023/6/10101251234162646381725ABEDCFABEDCF連通分量＝{A,F,C,D},{B,E}12連通分量＝{A,F,C,D,B,E}16172526第一百零二頁，共一百九十一頁，編輯于2023年，星期三2023/6/101021.初始化：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ù)最短邊的選??；Kruskal算法——偽代碼第一百零三頁，共一百九十一頁，編輯于2023年，星期三2023/6/10103克魯斯卡爾(Kruskal)算法voidminitree_KRUSKAL(void){ intn,i,m,min,k,j; VEXt[M]; EDGEe[M]; printf("Inputnumberofvertexandedge:");

scanf("%d,%d",&n,&m); for(i=1;i<=n;i++){

printf(“t[%d].data=:”,i);

scanf(“%d”,&t[i].data);

t[i].set=i;} for(i=0;i<m;i++){

printf("vexh,vext,weight:");

scanf("%d,%d,%d",&e[i].vexh,&e[i].vext,&e[i].weight);

e[i].flag=0;}第一百零四頁，共一百九十一頁，編輯于2023年，星期三2023/6/10104 i=1; while(i<n){ min=MAX;

for(j=0;j<m;j++) if(e[j].weight<min&&e[j].flag==0)

{min=e[j].weight;k=j;}

if(t[e[k].vexh].set!=t[e[k].vext].set){

e[k].flag=1;

t[e[k].vext].set=t[e[k].vexh].set;

for(j=1;j<=n;j++)

if(t[j].set==t[e[k].vext].set)

t[j].set=t[e[k].vexh].set;

i++;

}

else

e[k].flag=2; } for(i=0;i<m;i++)

if(e[i].flag==1)

printf("%d,%d:%d\n",e[i].vexh,e[i].vext,e[i].weight);}時(shí)間復(fù)雜度為O(ne)第一百零五頁，共一百九十一頁，編輯于2023年，星期三2023/6/10105方法二：普里姆(Prim)算法基本思想首先選取圖中任意一個(gè)頂點(diǎn)v作為生成樹的根，之后繼續(xù)往生成樹中添加頂點(diǎn)w，則在頂點(diǎn)w和頂點(diǎn)v之間必須有邊，且該邊上的權(quán)值應(yīng)在所有和v相鄰接的邊中屬最小。具體作法TE是N上最小生成樹中邊的集合初始令U={u0},(u0V),TE=；在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)；將(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)；重復(fù)上述操作直至U=V為止，則T=(V,{TE})為最小生成樹。第一百零六頁，共一百九十一頁，編輯于2023年，星期三2023/6/10106關(guān)鍵:是如何找到連接U和V-U的最短邊。

普里姆（Prim）算法

利用MST性質(zhì)，可以用下述方法構(gòu)造候選最短邊集：對(duì)應(yīng)V-U中的每個(gè)頂點(diǎn)，保留從該頂點(diǎn)到U中的各頂點(diǎn)的最短邊。第一百零七頁，共一百九十一頁，編輯于2023年，星期三2023/6/10107U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}251234192646381725ABEDCFPrim算法

第一百零八頁，共一百九十一頁，編輯于2023年，星期三2023/6/10108Prim算法

251234192646381725ABEDCFU={A,F}V-U={B,C,D,E}cost={(A,B)34,(A,C)46,(F,C)25,(F,D)25,(F,E)26}第一百零九頁，共一百九十一頁，編輯于2023年，星期三2023/6/10109Prim算法

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

第一百一十頁，共一百九十一頁，編輯于2023年，星期三2023/6/10110Prim算法

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

第一百一十一頁，共一百九十一頁，編輯于2023年，星期三2023/6/10111Prim算法

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

第一百一十二頁，共一百九十一頁，編輯于2023年，星期三2023/6/10112Prim算法

251234192646381725ABEDCFU={A,F,C,D,E,B}V-U={}第一百一十三頁，共一百九十一頁，編輯于2023年，星期三2023/6/10113數(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如何用數(shù)組lowcost和adjvex表示候選最短邊集？第一百一十四頁，共一百九十一頁，編輯于2023年，星期三2023/6/10114i數(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)用舉例——最小生成樹第一百一十五頁，共一百九十一頁，編輯于2023年，星期三2023/6/101151.初始化兩個(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算法——偽代碼

第一百一十六頁，共一百九十一頁，編輯于2023年，星期三2023/6/10116普里姆算法7.9voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){

//按普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造G的最小生成樹，輸出T的各條邊。 k=LocateVex(G,u); for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化

if(j!=k)closedge[j]={u,G.arcs[k][j].adj}; closedge[k].lowcost=0;//初始狀態(tài)，U＝{u} for(i=1;i<G.vexnum;++i){//選擇其余G.vexnum-1個(gè)頂點(diǎn)

k=minimum(closedge);//求出T的下一個(gè)結(jié)點(diǎn)邊

printf(closedge[k].adjvex,G.vexs[k]);//輸出生成樹的邊

closedge[k].lowcost=0;//第k頂點(diǎn)并入U(xiǎn)集

for(j=0;j<G.vexnum;++j)

if(G.arcs[k][j].adj<closedge[j].lowcost)

//新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊

closedge[j]={G.vexs[k],G.arcs[k][j].adj};

}//for}//MiniSpanTree時(shí)間復(fù)雜度為O(n2)第一百一十七頁，共一百九十一頁，編輯于2023年，星期三2023/6/10117最小生成樹算法的分析普里姆算法和圖的邊數(shù)無關(guān)，適合邊稠密的情況。克魯斯卡爾算法適合邊稀疏的情況。第一百一十八頁，共一百九十一頁，編輯于2023年，星期三2023/6/101187.5有向無環(huán)圖及其應(yīng)用有向無環(huán)圖無環(huán)的有向圖叫有向無環(huán)圖，簡稱DAG圖。應(yīng)用在工程計(jì)劃和管理方面有著廣泛而重要的應(yīng)用。描述一項(xiàng)工程或系統(tǒng)的進(jìn)行進(jìn)程的有效工具。對(duì)整個(gè)工程和系統(tǒng)，人們關(guān)心的是兩方面的問題：一是工程能否順利進(jìn)行；二是完成整個(gè)工程所必須的最短時(shí)間。對(duì)應(yīng)到有向圖即為進(jìn)行拓?fù)渑判蚝颓箨P(guān)鍵路徑。123456第一百一十九頁，共一百九十一頁，編輯于2023年，星期三2023/6/101197.5.1拓?fù)渑判蛘n程代號(hào)課程名稱先修課C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語言語言的設(shè)計(jì)和分析計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)？第一百二十頁，共一百九十一頁，編輯于2023年，星期三2023/6/10120AOV網(wǎng)