數(shù)據(jù)結(jié)構(gòu)課件-圖講述

Page12023/10/9畫出下列二叉鏈表代表的二叉樹（0代表NULL指針），并完成其先序線索鏈表InfoABCDEFGHIJKLMNLtagLchild24607010012130000RtagRchild3500891100014000InfoABCDEFGHIJKLMNLtag00010101001111Lchild246273101412131391011Rtag00110001110111Rchild35658911312131401181234567891011121314Page22023/10/9數(shù)據(jù)結(jié)構(gòu)第8-1講圖的基礎(chǔ)知識(shí)清華大學(xué)自動(dòng)化系黃雙喜博士、副教授huangsx@Page32023/10/9學(xué)習(xí)目標(biāo)領(lǐng)會(huì)圖的基本概念。熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及其選用原則。熟練掌握?qǐng)D的兩種遍歷算法及應(yīng)用。理解各種圖的應(yīng)用問題的算法。重點(diǎn)和難點(diǎn)重點(diǎn)：圖的各種應(yīng)用問題的算法都比較經(jīng)典，注意理解各種圖的算法及其應(yīng)用場(chǎng)合。Page42023/10/9知識(shí)點(diǎn)圖的類型定義圖的存儲(chǔ)表示圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷最小生成樹算法拓?fù)渑判蜿P(guān)鍵路徑最短路徑圖的基礎(chǔ)知識(shí)圖的概念與基本術(shù)語圖的類型定義與存儲(chǔ)圖的遍歷圖的連通性與最小生成樹Page52023/10/92023/10/9歐拉1707年出生在瑞士的巴塞爾城，19歲開始發(fā)表論文，直到76歲。幾乎每一個(gè)數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級(jí)數(shù)論的歐拉常數(shù)，復(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拉Page72023/10/9能否從某個(gè)地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點(diǎn)？哥尼斯堡七橋問題

18世紀(jì)東普魯士哥尼斯堡被普列戈?duì)柡臃譃樗膲K,它們通過七座橋相互連接。當(dāng)時(shí)該城的市民熱衷于這樣一個(gè)游戲：“一個(gè)散步者怎樣才能從某塊陸地出發(fā)，經(jīng)每座橋一次且僅一次回到出發(fā)點(diǎn)？”2023/10/9CADB七橋問題的圖模型歐拉回路的判定規(guī)則：1.如果通奇數(shù)橋的地方多于兩個(gè)，則不存在歐拉回路；2.如果只有兩個(gè)地方通奇數(shù)橋，可以從這兩個(gè)地方之一出發(fā)，找到歐拉回路；3.如果沒有一個(gè)地方是通奇數(shù)橋的，則無論從哪里出發(fā)，都能找到歐拉回路。Page92023/10/9×√×√最短路問題（SPP－shortestpathproblem）一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的最短路。旅行商問題（TSP－travelingsalesmanproblem）一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題。中國郵遞員問題（CPP－Chinesepostmanproblem）

一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。運(yùn)輸問題(transportationproblem)某種原材料有N個(gè)產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往M個(gè)使用這些原材料的工廠。假定N個(gè)產(chǎn)地的產(chǎn)量和M家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？公路連接問題某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來，使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市。假定已經(jīng)知道了任意兩個(gè)城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最??？上述問題有兩個(gè)共同的特點(diǎn)： 一、它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為最優(yōu)化或優(yōu)化（optimization）問題； 二、它們都易于用圖形的形式直觀地描述和表達(dá)，數(shù)學(xué)上把這種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡(luò)（network）。與圖和網(wǎng)絡(luò)相關(guān)的最優(yōu)化問題就是網(wǎng)絡(luò)最優(yōu)化或稱網(wǎng)絡(luò)優(yōu)化（networkoptimization）問題。

線性表每個(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)用于計(jì)算機(jī)、邏輯學(xué)、物理、化學(xué)等領(lǐng)域。圖的基本特性網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)社交網(wǎng)絡(luò)圖像處理物理化學(xué)結(jié)構(gòu)電腦游戲2023/10/9圖的定義圖是由頂點(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ù)不能為零，但可以沒有邊。Page15如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是無向邊，則稱該圖為無向圖。若頂點(diǎn)vi和vj之間的邊沒有方向，則稱這條邊為無向邊，表示為(vi,vj)。若從頂點(diǎn)vi到vj的邊有方向，則稱這條邊為有向邊，表示為<vi,vj>。

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

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

數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖。鄰接、依附無向圖中，對(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的鄰接點(diǎn)：V2、V4V1、V3、V52023/10/9鄰接、依附有向圖中，對(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)：V3的鄰接點(diǎn)：V2、V3V42023/10/9無向完全圖：在無向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無向完全圖。有向完全圖：在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向相反的兩條弧，則稱該圖為有向完全圖。

V1V2V3V1V2V3V42023/10/9含有n個(gè)頂點(diǎn)的無向完全圖有多少條邊？含有n個(gè)頂點(diǎn)的有向完全圖有多少條??？

含有n個(gè)頂點(diǎn)的無向完全圖有n×(n-1)/2條邊。含有n個(gè)頂點(diǎn)的有向完全圖有n×(n-1)條邊。V1V2V3V1V2V3V42023/10/9稀疏圖：稱邊數(shù)很少的圖為稀疏圖；稠密圖：稱邊數(shù)很多的圖為稠密圖。頂點(diǎn)的度：在無向圖中，頂點(diǎn)v的度是指依附于該頂點(diǎn)的邊數(shù)，通常記為TD(v)。頂點(diǎn)的入度：在有向圖中，頂點(diǎn)v的入度是指以該頂點(diǎn)為弧頭的弧的數(shù)目，記為ID(v)；頂點(diǎn)的出度：在有向圖中，頂點(diǎn)v的出度是指以該頂點(diǎn)為弧尾的弧的數(shù)目，記為OD(v)。2023/10/9V1V2V3V4V5在具有n個(gè)頂點(diǎn)、e條邊的無向圖G中，各頂點(diǎn)的度之和與邊數(shù)之和的關(guān)系？?==niievTD12)(V1V2V3V4在具有n個(gè)頂點(diǎn)、e條邊的有向圖G中，各頂點(diǎn)的入度之和與各頂點(diǎn)的出度之和的關(guān)系？與邊數(shù)之和的關(guān)系？evODvIDiiii==??==11)()(nn2023/10/9權(quán)：是指對(duì)邊賦予的有意義的數(shù)值量。網(wǎng)：邊上帶權(quán)的圖，也稱網(wǎng)圖。V1V2V3V42785圖結(jié)構(gòu)中的權(quán)和哈夫曼樹中的權(quán)有什么區(qū)別？2023/10/9路徑：在無向圖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。V1V2V3V4V5一般情況下，圖中兩個(gè)頂點(diǎn)之間的路徑不唯一。在什么情況下唯一？V1到V4的路徑：V1V4

V1V2V3V4V1V2V5V3V42023/10/9路徑長度：非帶權(quán)圖——路徑上邊的個(gè)數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V1V2V3V4V5V1V4：長度為1V1V2V3V4：長度為3V1V2V5V3V4：長度為42023/10/9路徑長度：非帶權(quán)圖——路徑上邊的個(gè)數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V1V4：長度為8V1V2V3V4：長度為7V1V2V5V3V4：長度為15V1V2V3V4V52563282023/10/9回路（環(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)的回路。V1V2V3V4V5V1V2V3V42023/10/9子圖：若圖G=（V，E），G'=（V'，E'），如果V'

V

且E'

E

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

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

V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量2連通分量是對(duì)無向圖的一種劃分。Page322023/10/9強(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)連通子圖。

如何求得一個(gè)有向非連通圖的強(qiáng)連通分量?2023/10/9V1V2V3V4強(qiáng)連通分量1

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

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

如何理解極小連通子圖?多——構(gòu)成回路少——不連通含有n-1條邊2023/10/9V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成樹生成森林圖的基礎(chǔ)知識(shí)圖的概念與基本術(shù)語圖的類型定義與存儲(chǔ)圖的遍歷圖的連通性與最小生成樹Page362023/10/92023/10/9圖的抽象數(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>的意義

或信息}Page382023/10/9G1=(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)}Page392023/10/9圖的基本操作：

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)

在圖中位置；否則返回其它信息。 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)，則返回“空”。Page412023/10/9

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/10/9 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>。Page432023/10/9 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()失敗，則操作失敗。

BFSTraverse(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()失敗，則操作失敗。}ADTGraph2023/10/9是否可以采用頂點(diǎ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ù)組表示法(鄰接矩陣)將圖的頂點(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)值，否則為∞。1、圖的鄰接矩陣表示法2023/10/9圖的數(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/10/9有向圖的存儲(chǔ)結(jié)構(gòu)G1BDACG1.vexs=[A,B,C,D]G1.vexnum=4G1.arcnum=4G1.kind=DGPage482023/10/9V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求頂點(diǎn)i的出度？鄰接矩陣的第i行元素之和。Page492023/10/9V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求頂點(diǎn)i的入度？鄰接矩陣的第i列元素之和。2023/10/9V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何判斷從頂點(diǎn)i到頂點(diǎn)j是否存在邊？測(cè)試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。2023/10/9無向圖的存儲(chǔ)結(jié)構(gòu)AECBDG2G2.vexs=[A,B,C,D,E]G2.vexnum=5G2.arcnum=6G2.kind=UDG2023/10/9如何求頂點(diǎn)i的度？V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4鄰接矩陣的第i行（或第i列）非零元素的個(gè)數(shù)。2023/10/9如何判斷頂點(diǎn)i和j之間是否存在邊？V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4測(cè)試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。Page542023/10/9如何求頂點(diǎn)i的所有鄰接點(diǎn)？V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4將數(shù)組中第i

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

為頂點(diǎn)i的鄰接點(diǎn)。網(wǎng)圖的鄰接矩陣定義：

arc[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）∞/0若i=j∞其他V1V2V3V42785∞25∞∞∞∞∞∞∞∞87∞∞∞arc=Page562023/10/9ADEBC75318642G3G3.vexs=[A,B,C,D,E]G3.vexnum=5G3.arcnum=8G3.kind=UDN2023/10/9鄰接矩陣表示的特點(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/10/92、圖的鄰接表表示法引入原因鄰接矩陣在稀疏圖時(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)（頂點(diǎn)結(jié)點(diǎn)）。表結(jié)點(diǎn)adjvexnextarcinfo與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置頭結(jié)點(diǎn)datafirstarcPage592023/10/9圖的鄰接表存儲(chǔ)表示#defineMAX_VERTEX_NUM20;typedefstructArcNode{

int adjvex;

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

structArcNode *nextarc;

//指向下一條弧的指針

InfoType *info;

//該弧相關(guān)信息的指針

}ArcNode;//邊表結(jié)點(diǎn)typedefstructVNode{

VertexType data;

//頂點(diǎn)信息

ArcNode *firstarc;

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

}AdjList[MAX_VERTEX_NUM];//頂點(diǎn)表typedefstruct{

AdjListvertices;

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

intvexnum,arcnum;

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

intkind;

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

}ALGraph;Page602023/10/9103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2邊表中的結(jié)點(diǎn)表示什么？每個(gè)結(jié)點(diǎn)對(duì)應(yīng)圖中的一條邊，鄰接表的空間復(fù)雜度為O(n+2e)。2023/10/9103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2如何求頂點(diǎn)i的度？頂點(diǎn)i的邊表中結(jié)點(diǎn)的個(gè)數(shù)。無向圖的鄰接表2023/10/9如何判斷頂點(diǎn)i和頂點(diǎn)j之間是否存在邊?測(cè)試頂點(diǎn)i的邊表中是否存在終點(diǎn)為j的結(jié)點(diǎn)。103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2Page63有向圖的鄰接表V1V2V3V412∧3∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點(diǎn)i的出度？頂點(diǎn)i的出邊表中結(jié)點(diǎn)的個(gè)數(shù)。2023/10/9V1V2V3V412∧3∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點(diǎn)i的入度？各頂點(diǎn)的出邊表中以頂點(diǎn)i為終點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)。Page652023/10/9V1V2V3V412∧3∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點(diǎn)i的所有鄰接點(diǎn)？遍歷頂點(diǎn)i的邊表，該邊表中的所有終點(diǎn)都是頂點(diǎn)i的鄰接點(diǎn)。Page662023/10/9網(wǎng)圖的鄰接表V1V2V3V4278521V1V2

V3V40123vertexfirstedge∧52∧83∧70∧2023/10/9優(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/10/93圖的十字鏈表表示法引入原因?qū)τ谕粋€(gè)有向圖需要同時(shí)用鄰接表和逆鄰接表時(shí)，不方便。實(shí)現(xiàn)將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個(gè)結(jié)點(diǎn)表示，由于在鄰接表和逆鄰接表中的頂點(diǎn)數(shù)據(jù)是相同的，則在十字鏈表中只需要出現(xiàn)一次，但需保留分別指向第一條"出弧"和第一條"入弧"的指針。G1bdac0123acdbdatafirstarc2130^^^^adjvexnext鄰接表2023/10/9引入原因?qū)τ谕粋€(gè)有向圖需要同時(shí)用鄰接表和逆鄰接表時(shí)，不方便。實(shí)現(xiàn)將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個(gè)結(jié)點(diǎn)表示，由于在鄰接表和逆鄰接表中的頂點(diǎn)數(shù)據(jù)是相同的，則在十字鏈表中只需要出現(xiàn)一次，但需保留分別指向第一條"出弧"和第一條"入弧"的指針。G1bdac逆鄰接表0123acdbdatafirstarc30^0^^2^adjvexnext2023/10/9弧結(jié)點(diǎn)tailvexheadvexhlinktlinkinfo頂點(diǎn)結(jié)點(diǎn)datafirstinfirstout弧尾位置弧頭位置弧頭相同的下一條弧指針弧相關(guān)信息的指針弧尾相同的下一條弧指針指向該頂點(diǎn)第一條入弧指向該頂點(diǎn)第一條出弧2023/10/902012320323130bdacabcd0123^^^^^^^^求結(jié)點(diǎn)的入度和出度的方法？弧頭弧尾出邊入邊同尾同頭Page722023/10/94圖的鄰接多重表表示法引入原因無向圖的鄰接表中每一條邊有兩個(gè)結(jié)點(diǎn)，給對(duì)圖的邊進(jìn)行訪問的操作帶來不便。有些時(shí)候需要同時(shí)找到表示同一條邊的兩個(gè)結(jié)點(diǎn)（如刪除一條邊）。aecbd0123acdbdatafirstarc3101^^^adjvexnext4e324^04212^Page73實(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/10/9aecbd0123acdb4e010323212441^^^^^圖的基礎(chǔ)知識(shí)圖的概念與基本術(shù)語圖的類型定義與存儲(chǔ)圖的遍歷圖的連通性與最小生成樹Page752023/10/92023/10/9圖的遍歷從圖中某一頂點(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。Page771深度優(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)都已被訪問過為止。Page782023/10/9深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5

V5Page792023/10/9深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8

V8Page802023/10/9深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8Page812023/10/9深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1

V7V2V4V5V8V3

V3V6

V6V72023/10/9深度優(yōu)先遍歷算法Boolenvisited[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/10/9voidDFS(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}//DFS2023/10/9V1V2V4V5V3V7V6V8深度遍歷：V1

0123V1V3V4V2datafirstarc1672^^^adjvexnext4V5530^40171^V6V7V8567625243^^^V3V7V6V2V5V8V42023/10/9V1V2V4V5V3V7V6V80123V1V3V4V2datafirstarc1672^^^adjvexnext4V55^371^V6V7V85676^^^深度遍歷：V1

V3V7V6V2V4V8V5Page862廣度優(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)。Page872023/10/9廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V1Page882023/10/9廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V3Page892023/10/9廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V5Page902023/10/9廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V7Page912023/10/9廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V8Page922023/10/9廣度優(yōu)先遍歷算法voidBFSTraverse(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

122023/10/91423501231342datafirstarc4432^^^adjvexnext450^40032^111、4、3、2、5圖的基礎(chǔ)知識(shí)圖的概念與基本術(shù)語圖的類型定義與存儲(chǔ)圖的遍歷圖的連通性與最小生成樹Page942023/10/9Page952023/10/9無向圖的連通分量對(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/10/9ABLMCFDEGHKIJ鄰接表1211109876543210MLKJIHGFEDCBA1152

112

0

0

4

3

0108

710

6

612

117

6129

0119

12023/10/9深度優(yōu)先遍歷的結(jié)果為(3次DFS過程)從A出發(fā)：ALMJBFC從D出發(fā)：DE從G出發(fā)：GKHI連通分量：三個(gè)頂點(diǎn)集+依附于這個(gè)頂點(diǎn)集中頂點(diǎn)的邊。DEGHKIABLMCFJ2023/10/9生成樹所有頂點(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/10/9V1V2V4V5V3V7V6V8V7V6V3V5V8V4V2V1深度遍歷V1V2V4V5V3V7V6V8深度優(yōu)先生成樹2023/10/9V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V1廣度遍歷V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹2023/10/9ABLMCFDEGHKIJ深度優(yōu)先遍歷： ALMJBFC

DE

GKHIABLMCFJDEGHKI深度優(yōu)先生成森林Page102網(wǎng)的最小生成樹問題描述用一個(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最小生成樹的性質(zhì)設(shè)G=(V，E)是一個(gè)帶權(quán)連通圖，U是頂點(diǎn)集V的一個(gè)非空子集。若u∈U，v∈V-U，且(u,v)是U中頂點(diǎn)到V-U中頂點(diǎn)之間權(quán)值最小的邊，則必存在一棵包含邊(u,v)的最小生成樹。構(gòu)造最小生成樹的基本原則：◆盡可能選取權(quán)值最小的邊，但不能構(gòu)成回路；◆選擇n-1條邊構(gòu)成最小生成樹。2023/10/9構(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/10/9251234162646381725ABEDCFABEDCF連通分量＝{A},{B},{C},{D},{E},{F}2023/10/9251234162646381725ABEDCFABEDCF連通分量＝{A},{B},{C},{D},{E},{F}12連通分量＝{A},{B,E},{C},{D},{F}2023/10/9251234162646381725ABEDCFABEDCF連通分量＝{A},{B,E},{C},{D},{F}12連通分量＝{A,F},{B,E},{C},{D}162023/10/9251234162646381725ABEDCFABEDCF連通分量＝{A,F},{B,E},{C},{D}12連通分量＝{A,F},{B,E},{C,D}16172023/10/9251234162646381725ABEDCFABEDCF連通分量＝{A,F},{B,E},{C,D}12連通分量＝{A,F,C,D},{B,E}1617252023/10/9251234162646381725ABEDCFABEDCF連通分量＝{A,F,C,D},{B,E}12連通分量＝{A,F,C,D,B,E}16172526Page1112023/10/91.初始化：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è)，編號(hào)改為相同；

2.3在E中標(biāo)記邊(u，v)，使得(u，v)不參加后續(xù)最短邊的選??；Kruskal算法——偽代碼解決方法：定義一個(gè)一維數(shù)組Vset[n]，存放圖T中每個(gè)頂點(diǎn)所在的連通分量的編號(hào)。◆

初值：Vset[i]=i，表示每個(gè)頂點(diǎn)各自組成一個(gè)連通分量，連通分量的編號(hào)簡單地使用頂點(diǎn)在圖中的位置(編號(hào))。◆當(dāng)往T中增加一條邊(vi，vj)時(shí)，先檢查Vset[i]和Vset[j]值：☆

若Vset[i]=Vset[j]：vi和vj處在同一個(gè)連通分量中；☆若Vset[i]≠Vset[j]：vi和vj不在同一個(gè)連通分量中2023/10/9克魯斯卡爾(Kruskal)算法for(j=0;j<G->vexnum;j++)Vset[j]=j;/*初始化數(shù)組Vset[n]，記錄連通分量編號(hào)*/sort(G->edgelist);/*對(duì)邊表按權(quán)值從小到大排序*/j=0;k=0;while(k<G->vexnum-1&&j<G->edgenum){s1=Vset[G->edgelist[j].vex1];s2=Vset[G->edgelist[j].vex2];/*若邊的兩個(gè)頂點(diǎn)的連通分量編號(hào)不同,邊加入到TE中*/if(s1!=s2)

{TE[k].vex1=G->edgelist[j].vex1;TE[k].vex2=G->edgelist[j].vex2;TE[k].weight=G->edgelist[j].weight;k++;for(v=0;v<G->vexnum;v++)//將Vset中所有值等于s2的都改為s1，成為一個(gè)連通分量

if(Vset[v]==s2)Vset[v]=s1;}j++;}free(Vset);return(TE);為什么k<G->vexnum-1？O(n)O(e㏒e)O(n)O(n^2)O(e㏒e+n2)2023/10/9方法二：普里姆(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})為最小生成樹。構(gòu)造最小生成樹方法2023/10/9U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}251234192646381725ABEDCF2023/10/9251234192646381725ABEDCFU={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/10/9251234192646381725ABEDCFU={A,F,C}V-U={B,D,E}cost={(A,B)34,(F,D)25,(C,D)17