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

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

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

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

線性表每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。樹形結(jié)構(gòu)每個數(shù)據(jù)元素只有一個直接前驅(qū)，但可能有多個直接后繼。圖形結(jié)構(gòu)每個數(shù)據(jù)元素可能有多個直接前驅(qū)和多個直接后繼。

圖是比線性表和樹復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于計算機、邏輯學(xué)、物理、化學(xué)等領(lǐng)域。圖的基本特性網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)社交網(wǎng)絡(luò)圖像處理物理化學(xué)結(jié)構(gòu)電腦游戲2023/10/9圖的定義圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：

G=(V，E)其中：G表示一個圖，V是圖G中頂點的集合，E是圖G中頂點之間邊的集合。在線性表中，元素個數(shù)可以為零，稱為空表；在樹中，結(jié)點個數(shù)可以為零，稱為空樹；在圖中，頂點個數(shù)不能為零，但可以沒有邊。Page15如果圖的任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖。若頂點vi和vj之間的邊沒有方向，則稱這條邊為無向邊，表示為(vi,vj)。若從頂點vi到vj的邊有方向，則稱這條邊為有向邊，表示為<vi,vj>。

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

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

數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖。鄰接、依附無向圖中，對于任意兩個頂點vi和頂點vj，若存在邊(vi，vj)，則稱頂點vi和頂點vj互為鄰接點，同時稱邊(vi，vj)依附于頂點vi和頂點vj。V1V2V3V4V5V1的鄰接點：V2的鄰接點：V2、V4V1、V3、V52023/10/9鄰接、依附有向圖中，對于任意兩個頂點vi和頂點vj，若存在弧<vi，vj>，則稱頂點vi鄰接到頂點vj，頂點vj鄰接自頂點vi，同時稱弧<vi，vj>依附于頂點vi和頂點vj

。

V1V2V3V4V1的鄰接點：V3的鄰接點：V2、V3V42023/10/9無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向相反的兩條弧，則稱該圖為有向完全圖。

V1V2V3V1V2V3V42023/10/9含有n個頂點的無向完全圖有多少條邊？含有n個頂點的有向完全圖有多少條?。?/p>

含有n個頂點的無向完全圖有n×(n-1)/2條邊。含有n個頂點的有向完全圖有n×(n-1)條邊。V1V2V3V1V2V3V42023/10/9稀疏圖：稱邊數(shù)很少的圖為稀疏圖；稠密圖：稱邊數(shù)很多的圖為稠密圖。頂點的度：在無向圖中，頂點v的度是指依附于該頂點的邊數(shù)，通常記為TD(v)。頂點的入度：在有向圖中，頂點v的入度是指以該頂點為弧頭的弧的數(shù)目，記為ID(v)；頂點的出度：在有向圖中，頂點v的出度是指以該頂點為弧尾的弧的數(shù)目，記為OD(v)。2023/10/9V1V2V3V4V5在具有n個頂點、e條邊的無向圖G中，各頂點的度之和與邊數(shù)之和的關(guān)系？?==niievTD12)(V1V2V3V4在具有n個頂點、e條邊的有向圖G中，各頂點的入度之和與各頂點的出度之和的關(guān)系？與邊數(shù)之和的關(guān)系？evODvIDiiii==??==11)()(nn2023/10/9權(quán)：是指對邊賦予的有意義的數(shù)值量。網(wǎng)：邊上帶權(quán)的圖，也稱網(wǎng)圖。V1V2V3V42785圖結(jié)構(gòu)中的權(quán)和哈夫曼樹中的權(quán)有什么區(qū)別？2023/10/9路徑：在無向圖G=(V,E)中，從頂點vp到頂點vq之間的路徑是一個頂點序列(vp=vi0,vi1,vi2,…,vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向圖，則路徑也是有方向的，頂點序列滿足<vij-1,vij>∈E。V1V2V3V4V5一般情況下，圖中兩個頂點之間的路徑不唯一。在什么情況下唯一？V1到V4的路徑：V1V4

V1V2V3V4V1V2V5V3V42023/10/9路徑長度：非帶權(quán)圖——路徑上邊的個數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V1V2V3V4V5V1V4：長度為1V1V2V3V4：長度為3V1V2V5V3V4：長度為42023/10/9路徑長度：非帶權(quán)圖——路徑上邊的個數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V1V4：長度為8V1V2V3V4：長度為7V1V2V5V3V4：長度為15V1V2V3V4V52563282023/10/9回路（環(huán)）：第一個頂點和最后一個頂點相同的路徑。簡單路徑：序列中頂點不重復(fù)出現(xiàn)的路徑。簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路。V1V2V3V4V5V1V2V3V42023/10/9子圖：若圖G=（V，E），G'=（V'，E'），如果V'

V

且E'

E

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

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

V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量2連通分量是對無向圖的一種劃分。Page322023/10/9強連通圖：在有向圖中，對圖中任意一對頂點vi和vj

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

如何求得一個有向非連通圖的強連通分量?2023/10/9V1V2V3V4強連通分量1

強連通分量2V1V3V4V22023/10/9生成樹：n個頂點的連通圖G的生成樹是包含G中全部頂點的一個極小連通子圖。

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

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

：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂

點集。數(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是圖的頂點集，VR是圖中弧的集合。

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

G。

DestroyGraph(&G);

初始條件：圖G存在。

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

G。

LocateVex(G,u);

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

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

在圖中位置；否則返回其它信息。 GetVex(G,v);

初始條件：圖G存在，v是G中某個頂點。

操作結(jié)果：返回v的值。

FirstAdjVex(G,v);

初始條件：圖G存在，v是G中某個頂點。

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

有鄰接點，則返回“空”。

NextAdjVex(G,v,w);

初始條件：圖G存在，v是G中某個頂點，w是v的

鄰接頂點。

操作結(jié)果：返回v的（相對于w的）下一個鄰接點。若

w是v的最后一個鄰接點，則返回“空”。Page412023/10/9

PutVex(&G,v,value);

初始條件：圖G存在，v是G中某個頂點。

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

InsertVex(&G,v);

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

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

DeleteVex(&G,v);

初始條件：圖G存在，v是G中某個頂點。

操作結(jié)果：刪除G中頂點v及其相關(guān)的弧。2023/10/9 InsertArc(&G,v,w);

初始條件：圖G存在，v和w是G中兩個頂點。

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

增添對稱弧<w,v>。

DeleteArc(&G,v,w);

初始條件：圖G存在，v和w是G中兩個頂點。

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

刪除對稱弧<w,v>。Page432023/10/9 DFSTraverse(G,Visit());

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

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

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

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

BFSTraverse(G,Visit());

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

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

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

visit()失敗，則操作失敗。}ADTGraph2023/10/9是否可以采用頂點的順序存儲結(jié)構(gòu)存儲圖?圖的特點：頂點之間的關(guān)系是m:n，即任何兩個頂點之間都可能存在關(guān)系（邊），無法通過存儲位置表示這種任意的邏輯關(guān)系，所以，圖無法采用順序存儲結(jié)構(gòu)。如何存儲圖?考慮圖的定義，圖是由頂點和邊組成的，分別考慮如何存儲頂點、如何存儲邊。數(shù)組表示法(鄰接矩陣)將圖的頂點信息存儲在一個一維數(shù)組中，并將它的鄰接矩陣存儲在一個二維數(shù)組中即構(gòu)成圖的數(shù)組表示。假設(shè)圖中頂點數(shù)為n，則鄰接矩陣A定義為網(wǎng)的鄰接矩陣的定義為，當(dāng)vi到vj有弧相鄰接時，aij的值應(yīng)為該弧上的權(quán)值，否則為∞。1、圖的鄰接矩陣表示法2023/10/9圖的數(shù)組(鄰接矩陣)存儲表示#defineINFINITY INT_MAX;

//最大值∞#defineMAX_VERTEX_NUM 20;

//最大頂點個數(shù)typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向圖,有向網(wǎng),無向圖,無向網(wǎng)}typedefstructArcCell{

VRType adj;

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

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

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

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

VertexType vexs[MAX_VERTEX_NUM]; //頂點信息

AdjMatrix arcs;

//鄰接矩陣

int vexnum,arcnum;

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

GraphKind kind;

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

}MGraph;2023/10/9有向圖的存儲結(jié)構(gòu)G1BDACG1.vexs=[A,B,C,D]G1.vexnum=4G1.arcnum=4G1.kind=DGPage482023/10/9V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求頂點i的出度？鄰接矩陣的第i行元素之和。Page492023/10/9V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求頂點i的入度？鄰接矩陣的第i列元素之和。2023/10/9V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何判斷從頂點i到頂點j是否存在邊？測試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。2023/10/9無向圖的存儲結(jié)構(gòu)AECBDG2G2.vexs=[A,B,C,D,E]G2.vexnum=5G2.arcnum=6G2.kind=UDG2023/10/9如何求頂點i的度？V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4鄰接矩陣的第i行（或第i列）非零元素的個數(shù)。2023/10/9如何判斷頂點i和j之間是否存在邊？V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4測試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。Page542023/10/9如何求頂點i的所有鄰接點？V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4將數(shù)組中第i

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

為頂點i的鄰接點。網(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鄰接矩陣表示的特點：無向圖的鄰接矩陣對稱，可壓縮存儲；有n個頂點的無向圖需存儲空間為n(n+1)/2。有向圖鄰接矩陣不一定對稱；有n個頂點的有向圖需存儲空間為n2。無向圖中頂點Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和。有向圖中，頂點Vi的出度是A中第i行元素之和。頂點Vi的入度是A中第i列元素之和。鄰接矩陣的優(yōu)缺點優(yōu)點：容易判定頂點間有無邊（弧）和計算頂點的度（出度、

入度）。缺點：邊數(shù)較少時，空間浪費較大。2023/10/92、圖的鄰接表表示法引入原因鄰接矩陣在稀疏圖時空間浪費較大。實現(xiàn)為圖中每個頂點建立一個單鏈表（邊表），第i個單鏈表中的結(jié)點表示依附于頂點Vi的邊（有向圖中指以Vi為尾的?。Ｃ總€鏈表附設(shè)一個表頭結(jié)點（頂點結(jié)點）。表結(jié)點adjvexnextarcinfo與Vi鄰接的點在表頭數(shù)組中的位置頭結(jié)點datafirstarcPage592023/10/9圖的鄰接表存儲表示#defineMAX_VERTEX_NUM20;typedefstructArcNode{

int adjvex;

//該弧所指向的頂點的位置

structArcNode *nextarc;

//指向下一條弧的指針

InfoType *info;

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

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

VertexType data;

//頂點信息

ArcNode *firstarc;

//指向第一條依附該頂點的弧

}AdjList[MAX_VERTEX_NUM];//頂點表typedefstruct{

AdjListvertices;

//頂點數(shù)組

intvexnum,arcnum;

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

intkind;

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

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

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

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

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

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

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

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

V3V40123vertexfirstedge∧52∧83∧70∧2023/10/9優(yōu)缺點優(yōu)點：空間較省；無向圖容易求各頂點的度；有向圖容易求頂點的出度；缺點：求有向圖頂點的入度則不容易，要遍歷整個表。為了求頂點的入度，有時可設(shè)逆鄰接表（指向某頂點的鄰接點鏈接成單鏈表）。bdac0123acdbdatafirstarc30^0^^2^adjvexnext逆鄰接表2023/10/93圖的十字鏈表表示法引入原因?qū)τ谕粋€有向圖需要同時用鄰接表和逆鄰接表時，不方便。實現(xiàn)將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結(jié)點表示，由于在鄰接表和逆鄰接表中的頂點數(shù)據(jù)是相同的，則在十字鏈表中只需要出現(xiàn)一次，但需保留分別指向第一條"出弧"和第一條"入弧"的指針。G1bdac0123acdbdatafirstarc2130^^^^adjvexnext鄰接表2023/10/9引入原因?qū)τ谕粋€有向圖需要同時用鄰接表和逆鄰接表時，不方便。實現(xiàn)將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結(jié)點表示，由于在鄰接表和逆鄰接表中的頂點數(shù)據(jù)是相同的，則在十字鏈表中只需要出現(xiàn)一次，但需保留分別指向第一條"出弧"和第一條"入弧"的指針。G1bdac逆鄰接表0123acdbdatafirstarc30^0^^2^adjvexnext2023/10/9弧結(jié)點tailvexheadvexhlinktlinkinfo頂點結(jié)點datafirstinfirstout弧尾位置弧頭位置弧頭相同的下一條弧指針弧相關(guān)信息的指針弧尾相同的下一條弧指針指向該頂點第一條入弧指向該頂點第一條出弧2023/10/902012320323130bdacabcd0123^^^^^^^^求結(jié)點的入度和出度的方法？弧頭弧尾出邊入邊同尾同頭Page722023/10/94圖的鄰接多重表表示法引入原因無向圖的鄰接表中每一條邊有兩個結(jié)點，給對圖的邊進(jìn)行訪問的操作帶來不便。有些時候需要同時找到表示同一條邊的兩個結(jié)點（如刪除一條邊）。aecbd0123acdbdatafirstarc3101^^^adjvexnext4e324^04212^Page73實現(xiàn)每條邊用一個結(jié)點表示。邊結(jié)點markivexilinkjvexjlinkinfo頂點結(jié)點markfirstedge訪問標(biāo)記邊依附的一個頂點邊依附的另一個頂點依附這個頂點的下一條邊指針依附這個頂點的下一條邊指針訪問標(biāo)記指向第一條依附該頂點的邊2023/10/9aecbd0123acdb4e010323212441^^^^^圖的基礎(chǔ)知識圖的概念與基本術(shù)語圖的類型定義與存儲圖的遍歷圖的連通性與最小生成樹Page752023/10/92023/10/9圖的遍歷從圖中某一頂點出發(fā)，訪問圖中其余頂點，使每個頂點被訪問一次且只被訪問一次?？梢詮膱D中任意一個頂點出發(fā)進(jìn)行遍歷。遍歷中需解決的問題確定一搜索路徑；確保每個頂點被訪問到；確保每個頂點只能被訪問一次。解決方法深度優(yōu)先和廣度優(yōu)先。設(shè)輔助數(shù)組visited，初始時，數(shù)組元素的值均為0或false，表示未被遍歷，一旦遍歷，就置為1或true。Page771深度優(yōu)先搜索方法從圖的某一頂點V0出發(fā)，訪問此頂點；然后依次從V0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止。訪問任意一個與V0鄰接的頂點W1，再從W1出發(fā)；訪問與W1鄰接且未被訪問過的任意頂點W2，再從W2出發(fā)；重復(fù)以上過程，直到一個所有鄰接點都被訪問過的頂點為止；退回到尚有鄰接點未被訪問過的頂點，再從該頂點出發(fā)；直到所有的被訪問過的頂點的鄰接點都已被訪問過為止。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)){

//對圖G作深度優(yōu)先遍歷

visitFunc=visit; //使用全局變量visitFunc，

//使DFS不必設(shè)函數(shù)指針參數(shù)

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

visited[v]=FALSE;

//訪問標(biāo)識數(shù)組初始化

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

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

//頂點調(diào)用DFS}2023/10/9voidDFS(GraphG,intv){

//從第v個頂點出發(fā)遞歸地對圖G進(jìn)行深度優(yōu)先搜索

visitFunc(v);

//訪問第v個頂點

visited[v]=TRUE;

//設(shè)訪問標(biāo)志

for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(!visited[w])DFS(G,w); //對v的尚未訪問過的鄰接

//頂點w遞歸調(diào)用DFS}//DFS2023/10/9V1V2V4V5V3V7V6V8深度遍歷：V1

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

V3V7V6V2V4V8V5Page862廣度優(yōu)先搜索方法從圖的某一頂點V0出發(fā)，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止。

廣度優(yōu)先遍歷的過程是以v為起始點，由近至遠(yuǎn)，依次訪問和v有路徑相通且最短路徑長度為1,2,…

的頂點。Page872023/10/9廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V1Page882023/10/9廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V3Page892023/10/9廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V5Page902023/10/9廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V7Page912023/10/9廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V8Page922023/10/9廣度優(yōu)先遍歷算法voidBFSTraverse(GraphG,Status(*visit)(intv)){

//對圖G進(jìn)行廣度優(yōu)先搜索遍歷

for(v=0;v<G.vexnum;++v)visited[v]=FALSE; InitQueue(Q);

//設(shè)置空隊列Q for(v=0;v<G.vexnum;++v) if(!visited[v]){

//v未被訪問

visited[v]=TRUE;Visit(v);

//訪問v

EnQueue(Q,v);

//v入隊列

while(!QueueEmpty(Q)){

DeQueue(Q,u);

//隊頭元素出隊并置為u

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

if(!visited[w]){

visited[w]=TRUE;Visit(w);

//訪問第w個頂點

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ù)語圖的類型定義與存儲圖的遍歷圖的連通性與最小生成樹Page942023/10/9Page952023/10/9無向圖的連通分量對于連通圖，僅需從圖中任一頂點出發(fā)，進(jìn)行DFS或BFS搜索，即可遍歷圖的全部頂點；對于非連通圖，則需從多個頂點出發(fā)進(jìn)行DFS或BFS搜索，才能遍歷完圖的全部頂點。每一次從一個新的起始點出發(fā)進(jìn)行DFS或BFS搜索過程中所得的頂點訪問序列就是各連通分量的頂點集。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連通分量：三個頂點集+依附于這個頂點集中頂點的邊。DEGHKIABLMCFJ2023/10/9生成樹所有頂點均由邊連接在一起，但不存在回路的圖稱為生成樹。一個有n個頂點的連通圖的生成樹有n-1條邊；一個圖可以有許多棵不同的生成樹。對于連通圖，調(diào)用DFS所經(jīng)過的邊的集合和圖的全部頂點構(gòu)成了圖的極小連通子圖，即連通圖的一棵深度優(yōu)先生成樹。對于連通圖，調(diào)用BFS所經(jīng)過的邊的集合和圖的全部頂點構(gòu)成了圖的極小連通子圖，即連通圖的一棵廣度優(yōu)先生成樹。對于非連通圖，每個連通分量的頂點集和所經(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)的最小生成樹問題描述用一個連通網(wǎng)表示n個居民點和各個居民點之間可能架設(shè)的通訊線路，網(wǎng)中邊上的權(quán)值表示架設(shè)這條線路所需經(jīng)費。在n個居民點間構(gòu)建通訊網(wǎng)只需架設(shè)n-1條線路，則工程隊面臨的問題是架設(shè)哪幾條線路能使總的工程費用最低？問題均等價于：在含有n個頂點的連通網(wǎng)中選擇n-1條邊，構(gòu)成一棵極小連通子圖，并使該連通子圖中n-1條邊上權(quán)值之和達(dá)到最小，則稱這棵連通子圖為連通網(wǎng)的最小生成樹。類似此類的問題很多。16543271317918127524101654327139510最小生成樹的性質(zhì)設(shè)G=(V，E)是一個帶權(quán)連通圖，U是頂點集V的一個非空子集。若u∈U，v∈V-U，且(u,v)是U中頂點到V-U中頂點之間權(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個頂點而無邊的非連通圖T=(V,{})，每個頂點自成一個連通分量；在E中選取代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價最小的邊；依此類推，直至T中所有頂點都在同一連通分量上為止。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中的連通分量個數(shù)為12.1在E中尋找最短邊(u，v);2.2如果頂點u、v位于T的兩個不同連通分量，則

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

2.2.2將這兩個連通分量合為一個，編號改為相同；

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

初值：Vset[i]=i，表示每個頂點各自組成一個連通分量，連通分量的編號簡單地使用頂點在圖中的位置(編號)?！舢?dāng)往T中增加一條邊(vi，vj)時，先檢查Vset[i]和Vset[j]值：☆

若Vset[i]=Vset[j]：vi和vj處在同一個連通分量中；☆若Vset[i]≠Vset[j]：vi和vj不在同一個連通分量中2023/10/9克魯斯卡爾(Kruskal)算法for(j=0;j<G->vexnum;j++)Vset[j]=j;/*初始化數(shù)組Vset[n]，記錄連通分量編號*/sort(G->edgelist);/*對邊表按權(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];/*若邊的兩個頂點的連通分量編號不同,邊加入到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，成為一個連通分量

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)算法基本思想首先選取圖中任意一個頂點v作為生成樹的根，之后繼續(xù)往生成樹中添加頂點w，則在頂點w和頂點v之間必須有邊，且該邊上的權(quán)值應(yīng)在所有和v相鄰接的邊中屬最小。具體作法

TE是N上最小生成樹中邊的集合初始令U={u0},(u0V),TE=；在所有uU,vV-U的邊(u,v)E中，找一條代價最小的邊(u0,v0)；將(u0,v0)并入集合TE，同時v0并入U；重復(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