數(shù)據(jù)結(jié)構圖論部分課件

DataStructure第七章圖100865106/9/20231學習目標領會圖的類型定義。熟悉圖的各種存儲結(jié)構及其構造算法，了解各種存儲結(jié)構的特點及其選用原則。熟練掌握圖的兩種遍歷算法。理解各種圖的應用問題的算法。重點和難點重點：圖的各種應用問題的算法都比較經(jīng)典，注意理解各種圖的算法及其應用場合。6/9/20232知識點圖的類型定義圖的存儲表示圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷無向網(wǎng)的最小生成樹拓撲排序關鍵路徑最短路徑6/9/20233歐拉1707年出生在瑞士的巴塞爾城，19歲開始發(fā)表論文，直到76歲。幾乎每一個數(shù)學領域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級數(shù)論的歐拉常數(shù)，變分學的歐拉方程，復變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計他那不倦的一生，共寫下了886本書籍和論文，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學占28%，天文學占11%，彈道學、航海學、建筑學等占3%。1733年，年僅26歲的歐拉擔任了彼得堡科學院數(shù)學教授。1741年到柏林擔任科學院物理數(shù)學所所長，直到1766年，重回彼得堡，沒有多久，完全失明。歐拉在數(shù)學上的建樹很多，對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。圖論——歐拉6/9/20234能否從某個地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點？哥尼斯堡七橋問題

6/9/20235CADB七橋問題的圖模型歐拉回路的判定規(guī)則：1.如果通奇數(shù)橋的地方多于兩個，則不存在歐拉回路；2.如果只有兩個地方通奇數(shù)橋，可以從這兩個地方之一出發(fā)，找到歐拉回路；3.如果沒有一個地方是通奇數(shù)橋的，則無論從哪里出發(fā)，都能找到歐拉回路。6/9/20236圖的定義圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：

G=(V，E)其中：G表示一個圖，V是圖G中頂點的集合，E是圖G中頂點之間邊的集合。在線性表中，元素個數(shù)可以為零，稱為空表；在樹中，結(jié)點個數(shù)可以為零，稱為空樹；在圖中，頂點個數(shù)不能為零，但可以沒有邊。7.1圖的定義和術語6/9/20237線性表每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。樹形結(jié)構每個數(shù)據(jù)元素只有一個直接前驅(qū)，但可能有多個直接后繼。圖形結(jié)構每個數(shù)據(jù)元素可能有多個直接前驅(qū)和多個直接后繼。圖是比線性表和樹復雜的數(shù)據(jù)結(jié)構，廣泛應用于語言學、邏輯學、物理、化學等領域。6/9/20238如果圖的任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖。若頂點vi和vj之間的邊沒有方向，則稱這條邊為無向邊，表示為(vi,vj)。若從頂點vi到vj的邊有方向，則稱這條邊為有向邊，表示為<vi,vj>。

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

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

數(shù)據(jù)結(jié)構中討論的都是簡單圖。6/9/202310圖的基本術語

鄰接、依附無向圖中，對于任意兩個頂點vi和頂點vj，若存在邊(vi，vj)，則稱頂點vi和頂點vj互為鄰接點，同時稱邊(vi，vj)依附于頂點vi和頂點vj。V1V2V3V4V5V1的鄰接點：V2、V4V2的鄰接點：V1、V3、V56/9/202311圖的基本術語

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

。

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

圖的基本術語

V1V2V3V1V2V3V46/9/202313含有n個頂點的無向完全圖有多少條邊？含有n個頂點的有向完全圖有多少條??？

含有n個頂點的無向完全圖有n×(n-1)/2條邊。含有n個頂點的有向完全圖有n×(n-1)條邊。V1V2V3V1V2V3V46/9/202314稀疏圖：稱邊數(shù)很少的圖為稀疏圖；稠密圖：稱邊數(shù)很多的圖為稠密圖。頂點的度：在無向圖中，頂點v的度是指依附于該頂點的邊數(shù)，通常記為TD(v)。圖的基本術語

頂點的入度：在有向圖中，頂點v的入度是指以該頂點為弧頭的弧的數(shù)目，記為ID(v)；頂點的出度：在有向圖中，頂點v的出度是指以該頂點為弧尾的弧的數(shù)目，記為OD(v)。6/9/202315V1V2V3V4V5圖的基本術語

在具有n個頂點、e條邊的無向圖G中，各頂點的度之和與邊數(shù)之和的關系？?==niievTD12)(6/9/202316V1V2V3V4圖的基本術語

在具有n個頂點、e條邊的有向圖G中，各頂點的入度之和與各頂點的出度之和的關系？與邊數(shù)之和的關系？evODvIDiiii==??==11)()(nn6/9/202317權：是指對邊賦予的有意義的數(shù)值量。網(wǎng)：邊上帶權的圖，也稱網(wǎng)圖。圖的基本術語

V1V2V3V427856/9/202318路徑：在無向圖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

V1V2V3V4V1V2V5V3V46/9/202319路徑長度：圖的基本術語

非帶權圖——路徑上邊的個數(shù)帶權圖——路徑上各邊的權之和V1V2V3V4V5V1V4：長度為1V1V2V3V4：長度為3V1V2V5V3V4：長度為46/9/202320路徑長度：圖的基本術語

非帶權圖——路徑上邊的個數(shù)帶權圖——路徑上各邊的權之和V1V4：長度為8V1V2V3V4：長度為7V1V2V5V3V4：長度為15V1V2V3V4V52563286/9/202321回路（環(huán)）：第一個頂點和最后一個頂點相同的路徑。簡單路徑：序列中頂點不重復出現(xiàn)的路徑。簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點外，其余頂點不重復出現(xiàn)的回路。圖的基本術語

V1V2V3V4V5V1V2V3V46/9/202322子圖：若圖G=（V，E），G'=（V'，E'），如果V'V

且E'

E

，則稱圖G'是G的子圖。圖的基本術語

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

圖的基本術語

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

V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量2圖的基本術語

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

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

圖的基本術語

如何求得一個非連通圖的連通分量?6/9/202326圖的基本術語

V1V2V3V4強連通分量1

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

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

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

多——構成回路少——不連通含有n-1條邊6/9/202328V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成樹生成森林6/9/202329圖的抽象數(shù)據(jù)類型定義如下：ADTGraph{數(shù)據(jù)對象V

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

點集。數(shù)據(jù)關系R

：

R={VR}

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

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

或信息}6/9/202330G1=(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)}6/9/202331

CreateGraph(&G,V,VR);

初始條件：V是圖的頂點集，VR是圖中弧的集合。

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

G。

DestroyGraph(&G);

初始條件：圖G存在。

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

G。

LocateVex(G,u);

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

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

在圖中位置；否則返回其它信息。

6/9/202332

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的最后一個鄰接點，則返回“空”。6/9/202333

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及其相關的弧。6/9/202334

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>。6/9/202335

DFSTraverse(G,Visit());

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

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

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

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

FSTraverse(G,Visit());

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

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

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

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

//最大值∞#defineMAX_VERTEX_NUM 20;

//最大頂點個數(shù)typedef

enum{DG,DN,UDG,UDN}GraphKind;//{有向圖,有向網(wǎng),無向圖,無向網(wǎng)}typedef

struct

ArcCell{

VRType

adj;

//VRType是頂點關系類型。對無權圖，用1或0

//表示相鄰否；對帶權圖，則為權值類型。

InfoType *info; //該弧相關信息的指針

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef

struct{

VertexType

vexs[MAX_VERTEX_NUM]; //頂點信息

AdjMatrix

arcs;

//鄰接矩陣

int

vexnum,arcnum;

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

GraphKind

kind;

//圖的種類標志

}MGraph;6/9/202339有向圖的存儲結(jié)構G1BDACG1.vexs=[A,B,C,D]G1.vexnum=4G1.arcnum=4G1.kind=DG6/9/202340有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求頂點i的出度？鄰接矩陣的第i行元素之和。6/9/202341有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求頂點i的入度？鄰接矩陣的第i列元素之和。6/9/202342有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何判斷從頂點i到頂點j是否存在邊？測試鄰接矩陣中相應位置的元素arc[i][j]是否為1。6/9/202343無向圖的存儲結(jié)構AECBDG2G2.vexs=[A,B,C,D,E]G2.vexnum=5G2.arcnum=6G2.kind=UDG6/9/202344網(wǎng)圖的存儲結(jié)構ADEBC75318642G3G3.vexs=[A,B,C,D,E]G3.vexnum=5G3.arcnum=8G3.kind=UDN6/9/202345如何求頂點i的度？無向圖的鄰接矩陣V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4鄰接矩陣的第i行（或第i列）非零元素的個數(shù)。6/9/202346如何判斷頂點i和j之間是否存在邊？無向圖的鄰接矩陣V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4測試鄰接矩陣中相應位置的元素arc[i][j]是否為1。6/9/202347如何求頂點i的所有鄰接點？無向圖的鄰接矩陣V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4將數(shù)組中第i

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

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

入度）。缺點：邊數(shù)較少時，空間浪費較大。6/9/202349網(wǎng)圖的鄰接矩陣網(wǎng)圖的鄰接矩陣可定義為：

arc[i][j]＝

wij

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

025∞∞0∞∞∞∞087∞∞0arc=6/9/2023507.2.2圖的鄰接表表示法引入原因鄰接矩陣在稀疏圖時空間浪費較大。實現(xiàn)為圖中每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點表示依附于頂點Vi的邊（有向圖中指以Vi為尾的?。?。每個鏈表附設一個表頭結(jié)點。表結(jié)點adjvexnextarcinfo與Vi鄰接的點在表頭數(shù)組中的位置頭結(jié)點datafirstarc6/9/202351圖的鄰接表存儲表示#defineMAX_VERTEX_NUM20;typedef

struct

ArcNode{

int

adjvex;

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

struct

ArcNode *nextarc;

//指向下一條弧的指針

InfoType *info;

//該弧相關信息的指針

}ArcNode;typedef

struct

VNode{

VertexType data;

//頂點信息

ArcNode *firstarc;

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

}AdjList[MAX_VERTEX_NUM];typedef

struct{

AdjList

vertices;

//頂點數(shù)組

int

vexnum,arcnum;

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

intkind;

//圖的種類標志

}ALGraph;6/9/202352103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2無向圖的鄰接表邊表中的結(jié)點表示什么？每個結(jié)點對應圖中的一條邊，鄰接表的空間復雜度為O(n+e)。6/9/202353103∧23∧1∧01∧V1V2

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

V3V40123vertexfirstedgeV1V3V4V2無向圖的鄰接表6/9/202355有向圖的鄰接表V1V2V3V412∧2∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點i的出度？頂點i的出邊表中結(jié)點的個數(shù)。6/9/202356有向圖的鄰接表V1V2V3V412∧2∧0∧V1V2

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

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

V3V40123vertexfirstedge∧52∧83∧70∧6/9/202359優(yōu)缺點優(yōu)點：空間較??；無向圖容易求各頂點的度；有向圖容易求頂點的出度；缺點：求有向圖頂點的入度則不容易，要遍歷整個表。為了求頂點的入度，有時可設逆鄰接表（指向某頂點的鄰接點鏈接成單鏈表）。bdac0123acdbdatafirstarc3

0^

0^^2^adjvexnext逆鄰接表6/9/2023607.2.3圖的十字鏈表表示法引入原因?qū)τ谕粋€有向圖需要同時用鄰接表和逆鄰接表時，不方便。實現(xiàn)將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結(jié)點表示，由于在鄰接表和逆鄰接表中的頂點數(shù)據(jù)是相同的，則在十字鏈表中只需要出現(xiàn)一次，但需保留分別指向第一條"出弧"和第一條"入弧"的指針。G1bdac0123acdbdatafirstarc

2

1

3

0^^^^adjvexnext鄰接表6/9/2023617.2.3圖的十字鏈表表示法引入原因?qū)τ谕粋€有向圖需要同時用鄰接表和逆鄰接表時，不方便。實現(xiàn)將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個結(jié)點表示，由于在鄰接表和逆鄰接表中的頂點數(shù)據(jù)是相同的，則在十字鏈表中只需要出現(xiàn)一次，但需保留分別指向第一條"出弧"和第一條"入弧"的指針。G1bdac逆鄰接表0123acdbdatafirstarc3

0^

0^^2^adjvexnext6/9/202362弧結(jié)點tailvexheadvexhlinktlinkinfo頂點結(jié)點datafirstinfirstout弧尾位置弧頭位置弧尾相同的下一條弧指針弧相關信息的指針弧頭相同的下一條弧指針指向該頂點第一條入弧指向該頂點第一條出弧6/9/20236302012320323130bdacabcd0123^^^^^^^^求結(jié)點的入度和出度的方法？6/9/2023647.2.4圖的鄰接多重表表示法

引入原因無向圖的鄰接表中每一條邊有兩個結(jié)點，給對圖的邊進行訪問的操作帶來不便。有些時候需要同時找到表示同一條邊的兩個結(jié)點（如刪除一條邊）。aecbd0123acdbdatafirstarc

3

1

0

1^^^adjvexnext4e

3

2

4^

0

42

12^6/9/202365實現(xiàn)每條邊用一個結(jié)點表示。邊結(jié)點markivexilinkjvexjlinkinfo頂點結(jié)點markfirstedge訪問標記邊依附的一個頂點邊依附的另一個頂點依附這個頂點的下一條邊指針依附這個頂點的下一條邊指針訪問標記指向第一條依附該頂點的邊6/9/202366aecbd0123acdb4e0103

23212441^^^^^6/9/2023677.3圖的遍歷圖的遍歷從圖中某一頂點出發(fā)，訪問圖中其余頂點，使每個頂點被訪問一次且只被訪問一次?？梢詮膱D中任意一個頂點出發(fā)進行遍歷。遍歷中需解決的問題確定一搜索路徑；確保每個頂點被訪問到；確保每個頂點只能被訪問一次。解決方法深度優(yōu)先和廣度優(yōu)先。設輔助數(shù)組visited，初始時，數(shù)組元素的值均為0或false，表示未被遍歷，一旦遍歷，就置為1或true。6/9/2023687.3.1深度優(yōu)先搜索方法從圖的某一頂點V0出發(fā)，訪問此頂點；然后依次從V0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止。訪問任意一個與V0鄰接的頂點W1，再從W1出發(fā)；訪問與W1鄰接且未被訪問過的任意頂點W2，再從W2出發(fā)；重復以上過程，直到一個所有鄰接點都被訪問過的頂點為止；退回到尚有鄰接點未被訪問過的頂點，再從該頂點出發(fā)；直到所有的被訪問過的頂點的鄰接點都已被訪問過為止。6/9/202369深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5

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

V1遍歷序列：V1V2

V2V4

V4V5V8

V86/9/202371深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1圖的邏輯結(jié)構V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

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

V1遍歷序列：V1

V7V2V4V5V8V3

V3V6

V6V76/9/202373深度優(yōu)先遍歷算法7.4、7.5Boolenvisited[MAX]; //訪問標志數(shù)組Status(*visitFunc)(intv); //函數(shù)變量voidDFSTraverse(GraphG,Status(*visit)(intv)){

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

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

，

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

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

visited[v]=FALSE;

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

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

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

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

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

visitFunc(v);

//訪問第v個頂點

visited[v]=TRUE;

//設訪問標志

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

//頂點w遞歸調(diào)用DFS}//DFS6/9/202375V1V2V4V5V3V7V6V8深度遍歷：V10123V1V3V4V2datafirstarc1

6

7

2^^^adjvexnext4V55

3

0^

4

0

1

7

1^V6V7V8567

6

2

5

2

4

3^^^V3V7V6V2V5V8V46/9/202376V1V2V4V5V3V7V6V80123V1V3V4V2datafirstarc

1

6

7

2^^^adjvexnext4V5

5^

3

7

1^V6V7V8567

6^^^深度遍歷：V1V3V7V6V2V4V8V56/9/2023777.3.2

廣度優(yōu)先搜索方法從圖的某一頂點V0出發(fā)，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止。廣度優(yōu)先遍歷的過程是以v為起始點，由近至遠，依次訪問和v有路徑相通且最短路徑長度為1,2,…的頂點。6/9/202378廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V16/9/202379廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V36/9/202380廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V56/9/202381廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V76/9/202382廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V86/9/202383V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V1V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V16/9/202384廣度優(yōu)先遍歷算法7.6voidBFSTraverse(GraphG,Status(*visit)(intv)){

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

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

InitQueue(Q);

//設置空隊列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

}//if

DestroyQueue(Q);}//BFSTraverse1

2

3

4

5

6

7

8

9

10

11

126/9/2023851423501231342datafirstarc

4

4

3

2^^^adjvexnext45

0^4

0

0

3

2^

1

16/9/2023867·4圖的連通性問題7.4.1無向圖的連通分量和生成樹無向圖的連通分量對于連通圖，僅需從圖中任一頂點出發(fā)，進行DFS或BFS搜索，即可遍歷圖的全部頂點；對于非連通圖，則需從多個頂點出發(fā)進行DFS或BFS搜索，才能遍歷完圖的全部頂點。每一次從一個新的起始點出發(fā)進行DFS或BFS搜索過程中所得的頂點訪問序列就是各連通分量的頂點集。6/9/202387ABLMCFDEGHKIJ鄰接表1211109876543210MLKJIHGFEDCBA11521120043010871066121176129011916/9/202388深度優(yōu)先遍歷的結(jié)果為(3次DFS過程)從A出發(fā)：ALMJBFC從D出發(fā)：DE從G出發(fā)：GKHI連通分量：三個頂點集+依附于這個頂點集中頂點的邊。DEGHKIABLMCFJ6/9/202389生成樹所有頂點均由邊連接在一起，但不存在回路的圖稱為生成樹。一個有n個頂點的連通圖的生成樹有n-1條邊；一個圖可以有許多棵不同的生成樹。對于連通圖，調(diào)用DFS所經(jīng)過的邊的集合和圖的全部頂點構成了圖的極小連通子圖，即連通圖的一棵深度優(yōu)先生成樹。對于連通圖，調(diào)用BFS所經(jīng)過的邊的集合和圖的全部頂點構成了圖的極小連通子圖，即連通圖的一棵廣度優(yōu)先生成樹。對于非連通圖，每個連通分量的頂點集和所經(jīng)過的邊一起構成若干棵生成樹，這些連通圖的生成樹構成非連通圖的生成森林。6/9/202390V1V2V4V5V3V7V6V8V7V6V3V5V8V4V2V1深度遍歷V1V2V4V5V3V7V6V8深度優(yōu)先生成樹6/9/202391V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V1廣度遍歷V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹6/9/202392ABLMCFDEGHKIJ深度優(yōu)先遍歷： ALMJBFC

DE

GKHIABLMCFJDEGHKI深度優(yōu)先生成森林6/9/2023937.4.2最小生成樹問題描述用一個連通網(wǎng)表示n個居民點和各個居民點之間可能架設的通訊線路，網(wǎng)中邊上的權值表示架設這條線路所需經(jīng)費。在n個居民點間構建通訊網(wǎng)只需架設n-1條線路，則工程隊面臨的問題是架設哪幾條線路能使總的工程費用最低？問題均等價于：在含有n個頂點的連通網(wǎng)中選擇n-1條邊，構成一棵極小連通子圖，并使該連通子圖中n-1條邊上權值之和達到最小，則稱這棵連通子圖為連通網(wǎng)的最小生成樹。類似此類的問題很多。165432713179181275241016543271395106/9/202394MST性質(zhì)假設G=(V,E)是一個無向連通網(wǎng)，U是頂點集V的一個非空子集。若(u,v)是一條具有最小權值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹。頂點集UV－Uu'vv'u頂點集T1T26/9/202395構造最小生成樹方法方法一：克魯斯卡爾(Kruskal)算法基本思想為使生成樹上總的權值之和達到最小，則應使每一條邊上的權值盡可能地小，自然應從權值最小的邊選起，直至選出n-1條互不構成回路的權值最小邊為止。具體作法初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V,{})，每個頂點自成一個連通分量；在E中選取代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價最小的邊；依此類推，直至T中所有頂點都在同一連通分量上為止。6/9/202396251234162646381725ABEDCFABEDCF連通分量＝{A},{B},{C},{D},{E},{F}6/9/202397251234162646381725ABEDCFABEDCF連通分量＝{A},{B},{C},{D},{E},{F}12連通分量＝{A},{B,E},{C},{D},{F}6/9/202398251234162646381725ABEDCFABEDCF連通分量＝{A},{B,E},{C},{D},{F}12連通分量＝{A,F},{B,E},{C},{D}166/9/202399251234162646381725ABEDCFABEDCF連通分量＝{A,F},{B,E},{C},{D}12連通分量＝{A,F},{B,E},{C,D}16176/9/2023100251234162646381725ABEDCFABEDCF連通分量＝{A,F},{B,E},{C,D}12連通分量＝{A,F,C,D},{B,E}1617256/9/2023101251234162646381725ABEDCFABEDCF連通分量＝{A,F,C,D},{B,E}12連通分量＝{A,F,C,D,B,E}161725266/9/20231021.初始化：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中標記邊(u，v)，使得(u，v)不參加后續(xù)最短邊的選取；Kruskal算法——偽代碼6/9/2023103克魯斯卡爾(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;}6/9/2023104

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);}時間復雜度為O(ne)6/9/2023105方法二：普里姆(Prim)算法基本思想首先選取圖中任意一個頂點v作為生成樹的根，之后繼續(xù)往生成樹中添加頂點w，則在頂點w和頂點v之間必須有邊，且該邊上的權值應在所有和v相鄰接的邊中屬最小。具體作法

TE是N上最小生成樹中邊的集合初始令U={u0},(u0V),TE=；在所有uU,vV-U的邊(u,v)E中，找一條代價最小的邊(u0,v0)；將(u0,v0)并入集合TE，同時v0并入U；重復上述操作直至U=V為止，則T=(V,{TE})為最小生成樹。6/9/2023106關鍵:是如何找到連接U和V-U的最短邊。

普里姆（Prim）算法

利用MST性質(zhì)，可以用下述方法構造候選最短邊集：對應V-U中的每個頂點，保留從該頂點到U中的各頂點的最短邊。6/9/2023107U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}251234192646381725ABEDCFPrim算法

6/9/2023108Prim算法

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}6/9/2023109Prim算法

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

6/9/2023110Prim算法

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

6/9/2023111Prim算法

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

6/9/2023112Prim算法

251234192646381725ABEDCFU={A,F,C,D,E,B}V-U={}6/9/2023113數(shù)組lowcost[n]：用來保存集合V-U中各頂點與集合U中頂點最短邊的權值，lowcost[v]=0表示頂點v已加入最小生成樹中；數(shù)組adjvex[n]：用來保存依附于該邊（集合V-U中各頂點與集合U中頂點的最短邊）在集合U中的頂點。數(shù)據(jù)結(jié)構設計表示頂點vi和頂點vk之間的權值為w，其中：vi∈V-U且vk

∈Ulowcost[i]=wadjvex[i]=k如何用數(shù)組lowcost和adjvex表示候選最短邊集？6/9/2023114

i

數(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}{}

應用舉例——最小生成樹6/9/20231151.初始化兩個輔助數(shù)組lowcost和adjvex；2.輸出頂點u0，將頂點u0加入集合U中；3.重復執(zhí)行下列操作n-1次

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

3.2輸出頂點k和對應的權值；

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

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

6/9/2023116普里姆算法7.9voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){

//按普里姆算法從頂點u出發(fā)構造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個頂點

k=minimum(closedge);

//求出T的下一個結(jié)點邊

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

closedge[k].lowcost=0;

//第k頂點并入U集

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

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

//新頂點并入U后重新選擇最小邊

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

}//for}//MiniSpanTree時間復雜度為O(n2)6/9/2023117最小生成樹算法的分析普里姆算法和圖的邊數(shù)無關，適合邊稠密的情況?？唆斔箍査惴ㄟm合邊稀疏的情況。6/9/20231187.5有向無環(huán)圖及其應用有向無環(huán)圖無環(huán)的有向圖叫有向無環(huán)圖，簡稱DAG圖。應用在工程計劃和管理方面有著廣泛而重要的應用。描述一項工程或系統(tǒng)的進行進程的有效工具。對整個工程和系統(tǒng)，人們關心的是兩方面的問題：一是工程能否順利進行；二是完成整個工程所必須的最短時間。對應到有向圖即為進行拓撲排序和求關鍵路徑。1234566/9/20231197.5.1拓撲排序課程代號課程名稱先修課C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設計基礎離散數(shù)學數(shù)據(jù)結(jié)構匯編語言語言的設計和分析計算機原理編譯原理操作系統(tǒng)高等數(shù)學線性代數(shù)普通物理數(shù)值分析學生應按怎樣的順序?qū)W習這些課程，才能無矛盾、順利地完成學業(yè)？6/9/2023120AOV網(wǎng)用頂點表示活動，用弧表示活動間優(yōu)先關系的有向圖稱為頂點表示活動的網(wǎng)(ActivityOnVertexnetwork)，簡稱AOV網(wǎng)。C1C2C3C4C5C6C7C8C9C10C11C12若<vi,vj>是圖中有向邊，vi是vj的直接前驅(qū)；vj是vi的直接后繼。6/9/2023121拓撲排序把AOV網(wǎng)中各頂點按照它們相互之間的優(yōu)先關系排列成一個線性序列（拓撲序列）的過程。若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該拓撲序列就是一個工程順利完成的可行方案；否則，該工程無法順利完成。拓撲排序的方法從圖中選擇一個入度為0的頂點輸出；從圖中刪除該頂點及源自該頂點的所有??；重復以上兩步，直至全部頂點都輸出，拓撲排序順利完成。否則，若剩有入度非0的頂點，說明圖中有環(huán)，拓撲排序不能進行。6/9/2023122C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列C16/9/2023123C2C3C4C5C6C7C8C9C10C11C12C2C1拓撲序列6/9/2023124C3C4C5C6C7C8C9C10C11C12C3C2C1拓撲序列6/9/2023125C4C5C6C7C8C9C10C11C12C4C3C2C1拓撲序列6/9/2023126C5C6C7C8C9C10C11C12C5C4C3C2C1拓撲序列6/9/2023127C6C7C8C9C10C11C12C7C5C4C3C2C1拓撲序列6/9/2023128C6C8C9C10C11C12C9C7C5C4C3C2C1拓撲序列6/9/2023129C6C8C10C11C12C10C9C7C5C4C3C2C1拓撲序列6/9/2023130C6C8C11C12C11C10C9C7C5C4C3C2C1拓撲序列6/9/2023131C6C8C6C11C10C9C7C5C4C3C2C1拓撲序列C126/9/2023132C8C12C12C6C11C10C9C7C5C4C3C2C1拓撲序列6/9/2023133C8C12C6C11C10C9C7C5C4C3C2C1拓撲序列C86/9/2023134C12C6C11C10C9C7C5C4C3C2C1拓撲序列C8C1C2C3C4C5C6C7C8C9C10C11C12課程代號課程名稱先修課C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設計基礎離散數(shù)學數(shù)據(jù)結(jié)構匯編語言語言的設計和分析計算機原理編譯原理操作系統(tǒng)高等數(shù)學線性代數(shù)普通物理數(shù)值分析一個AOV網(wǎng)的拓撲序列不是唯一的編程如何實現(xiàn)？6/9/2023135321040122inlink

4

4

32^^^vexnext3^

1

4^

1

30012345^top16toptop123456鄰接表結(jié)點的入度入度為0的頂點入棧6/9/20231360122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416toptop1234566/9/20231370122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：6321041topp1234566/9/20231380122inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321041topp1234566/9/20231390122inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321041topp1234566/9/20231400112inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123