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

2023年2月5日

數(shù)據(jù)結(jié)構(gòu)

2023年2月5日

線性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹(shù)形結(jié)構(gòu)——一個(gè)對(duì)多個(gè)，如樹(shù)集合——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無(wú)其它關(guān)系圖形結(jié)構(gòu)——多個(gè)對(duì)多個(gè)，如圖邏輯結(jié)構(gòu)

2023年2月5日

第6章圖6.1

圖的定義和基本術(shù)語(yǔ)6.2

圖的存儲(chǔ)結(jié)構(gòu)6.3

圖的遍歷6.4

圖的應(yīng)用教學(xué)內(nèi)容

2023年2月5日

1.掌握：圖的基本概念及相關(guān)術(shù)語(yǔ)和性質(zhì)2.熟練掌握：圖的鄰接矩陣和鄰接表兩種存儲(chǔ)表示方法3.熟練掌握：圖的兩種遍歷方法DFS和BFS4.熟練掌握：最短路算法（Dijkstra算法）5.掌握：最小生成樹(shù)的兩種算法及拓?fù)渑判蛩惴ǖ乃枷虢虒W(xué)目標(biāo)

2023年2月5日

6.1圖的定義和術(shù)語(yǔ)圖：Graph=(V,E)V：頂點(diǎn)(數(shù)據(jù)元素)的有窮非空集合；

E：邊的有窮集合。無(wú)向圖：有向圖：每條邊都是無(wú)方向的每條邊都是有方向的

2023年2月5日

完全圖：任意兩個(gè)點(diǎn)都有一條邊相連無(wú)向完全圖有向完全圖n(n-1)/2條邊n(n-1)條邊

2023年2月5日

稀疏圖：有很少邊或弧的圖。稠密圖：有較多邊或弧的圖。網(wǎng)：邊/弧帶權(quán)的圖。鄰接：有邊/弧相連的兩個(gè)頂點(diǎn)之間的關(guān)系。存在(vi,vj)，則稱vi和vj互為鄰接點(diǎn)；存在<vi,vj>，則稱vi鄰接到vj，vj鄰接于vi

關(guān)聯(lián)(依附)：邊/弧與頂點(diǎn)之間的關(guān)系。存在(vi,vj)/<vi,vj>，則稱該邊/弧關(guān)聯(lián)于vi和vj

2023年2月5日

頂點(diǎn)的度：與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，記為T(mén)D(v)在有向圖中,頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。頂點(diǎn)v的入度是以v為終點(diǎn)的有向邊的條數(shù),記作ID(v)

頂點(diǎn)v的出度是以v為始點(diǎn)的有向邊的條數(shù),記作OD(v)問(wèn)：當(dāng)有向圖中僅1個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1，此時(shí)是何形狀？答：是樹(shù)！而且是一棵有向樹(shù)！

2023年2月5日

路徑：接續(xù)的邊構(gòu)成的頂點(diǎn)序列。路徑長(zhǎng)度：路徑上邊或弧的數(shù)目/權(quán)值之和。回路(環(huán))：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。簡(jiǎn)單路徑：除路徑起點(diǎn)和終點(diǎn)可以相同外，其余頂點(diǎn)均不相同的路徑。簡(jiǎn)單回路(簡(jiǎn)單環(huán))：除路徑起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)均不相同的路徑。

2023年2月5日

非連通圖

連通圖

強(qiáng)連通圖

非強(qiáng)連通圖

V0

V1

V2

V3

V0

V4

V3

V1

V2

V0

V1

V2

V3

V0

V2

V3

V1

V5

V4連通圖（強(qiáng)連通圖）在無(wú)（有）向圖G=(V,{E})中，若對(duì)任何兩個(gè)頂點(diǎn)v、u都存在從v到u的路徑，則稱G是連通圖（強(qiáng)連通圖）。

2023年2月5日

(a)(b)(c)

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2子圖設(shè)有兩個(gè)圖G=（V，{E}）、G1=（V1，{E1}），若V1V，E1E，則稱G1是G的子圖。

例:(b)、(c)是(a)的子圖權(quán)與網(wǎng)圖中邊或弧所具有的相關(guān)數(shù)稱為權(quán)。表明從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。帶權(quán)的圖稱為網(wǎng)。

2023年2月5日

連通分量（強(qiáng)連通分量）非連通圖

V0

V2

V3

V1

V5

V4無(wú)向圖G的極大連通子圖稱為G的連通分量。

極大連通子圖意思是：該子圖是G連通子圖，將G的任何不在該子圖中的頂點(diǎn)加入，子圖不再連通。

V0

V2

V3

V1

V5

V4連通分量

2023年2月5日

有向圖G的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。極大強(qiáng)連通子圖意思是：該子圖是G的強(qiáng)連通子圖，將D的任何不在該子圖中的頂點(diǎn)加入，子圖不再是強(qiáng)連通的。強(qiáng)連通分量

V0

V1

V2

V3

V0

V2

V3

V1

2023年2月5日

極小連通子圖：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。

生成樹(shù)：包含無(wú)向圖G所有頂點(diǎn)的極小連通子圖。生成森林：對(duì)非連通圖，由各個(gè)連通分量的生成樹(shù)的集合。連通圖G1G1的生成樹(shù)

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

2023年2月5日

6.2圖的存儲(chǔ)結(jié)構(gòu)鄰接表鄰接多重表十字鏈表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）多重鏈表重點(diǎn)介紹：鄰接矩陣(數(shù)組)表示法鄰接表(鏈?zhǔn)?表示法

2023年2月5日

建立一個(gè)頂點(diǎn)表（記錄各個(gè)頂點(diǎn)信息）和一個(gè)鄰接矩陣（表示各個(gè)頂點(diǎn)之間關(guān)系）。設(shè)圖A=(V,E)有n

個(gè)頂點(diǎn)，則圖的鄰接矩陣是一個(gè)二維數(shù)組A.Edge[n][n]，定義為：數(shù)組（鄰接矩陣）表示法

2023年2月5日

鄰接矩陣：A.Edge=（v1v2

v3v4v5）v1v2v3v4v500

0

0000

0000

00000000000000分析1：無(wú)向圖的鄰接矩陣是對(duì)稱的；分析2：頂點(diǎn)i

的度＝第i

行(列)中1的個(gè)數(shù)；特別：完全圖的鄰接矩陣中，對(duì)角元素為0，其余1。01

0

1010

1010

101110101011

1001

0

1010

1

010

1

01110101011

10頂點(diǎn)表：無(wú)向圖的鄰接矩陣表示法v1v2v3v5v4v4

2023年2月5日

分析1：有向圖的鄰接矩陣可能是不對(duì)稱的。分析2：頂點(diǎn)的出度=第i行元素之和頂點(diǎn)的入度=第i列元素之和頂點(diǎn)的度=第i行元素之和+第i列元素之和

v1v2v3v4A鄰接矩陣：A.Edge=(v1v2

v3v4)v1v2v3v400

0

000

000

0000000注：在有向圖的鄰接矩陣中，第i行含義：以結(jié)點(diǎn)vi為尾的弧(即出度邊）；第i列含義：以結(jié)點(diǎn)vi為頭的弧(即入度邊）。頂點(diǎn)表：01

1

000

000

0

01

1

00001

1

000

000

0

01

1

000有向圖的鄰接矩陣表示法

2023年2月5日

定義為：A.Edge[i][j]=Wij

<vi,vj>或（vi,vj）∈VR∞

無(wú)邊（?。﹙1v2v3v4Nv5v65489755613鄰接矩陣：∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞N.Edge=(v1v2

v3v4v5v6

)頂點(diǎn)表：

5

7

4

8

9

5

6

5

3

1

∞

5

∞

7

∞

∞∞

∞

4

∞

∞

∞

8

∞

∞

∞∞

9∞

∞

5∞

∞

6∞

∞

∞

5

∞

∞

3

∞

∞∞

1

∞網(wǎng)（即有權(quán)圖）的鄰接矩陣表示法

2023年2月5日

優(yōu)點(diǎn)：容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊、找頂點(diǎn)的鄰接點(diǎn)等等。缺點(diǎn)：n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊;空間效率為O(n2)。對(duì)稀疏圖而言尤其浪費(fèi)空間。鄰接矩陣表示法的特點(diǎn)

2023年2月5日

//用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#defineMaxInt32767 //表示極大值，即∞#defineMVNum100 //最大頂點(diǎn)數(shù)typedefcharVerTexType; //假設(shè)頂點(diǎn)的數(shù)據(jù)類型為字符型typedef

int

ArcType; //假設(shè)邊的權(quán)值類型為整型typedef

struct{

VerTexType

vexs[MVNum]; //頂點(diǎn)表

ArcType

arcs[MVNum][MVNum]; //鄰接矩陣

int

vexnum,arcnum; //圖的當(dāng)前點(diǎn)數(shù)和邊數(shù)}AMGraph;鄰接矩陣的存儲(chǔ)表示

2023年2月5日

（1）輸入總頂點(diǎn)數(shù)和總邊數(shù)。（2）依次輸入點(diǎn)的信息存入頂點(diǎn)表中。（3）初始化鄰接矩陣，使每個(gè)權(quán)值初始化為極大值。（4）構(gòu)造鄰接矩陣。

【算法思想】采用鄰接矩陣表示法創(chuàng)建無(wú)向網(wǎng)

2023年2月5日

StatusCreateUDN(AMGraph&G){//采用鄰接矩陣表示法，創(chuàng)建無(wú)向網(wǎng)G

cin>>G.vexnum>>G.arcnum; //輸入總頂點(diǎn)數(shù)，總邊數(shù)

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

cin>>G.vexs[i]; //依次輸入點(diǎn)的信息

for(i=0;i<G.vexnum;++i) //初始化鄰接矩陣，邊的權(quán)值均置為極大值for(j=0;j<G.vexnum;++j)

G.arcs[i][j]=MaxInt;

for(k=0;k<G.arcnum;++k){//構(gòu)造鄰接矩陣

cin>>v1>>v2>>w;

//輸入一條邊依附的頂點(diǎn)及權(quán)值

i=LocateVex(G,v1);j=LocateVex(G,v2);//確定v1和v2在G中的位置G.arcs[i][j]=w;

//邊<v1,v2>的權(quán)值置為w

G.arcs[j][i]=G.arcs[i][j];

//置<v1,v2>的對(duì)稱邊<v2,v1>的權(quán)值為w}//forreturnOK;}//CreateUDN

【算法描述】

2023年2月5日

int

LocateVex(MGraph

G,VertexTypeu){/*初始條件:圖G存在,u和G中頂點(diǎn)有相同特征*//*操作結(jié)果:若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1*/

inti;

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

if(u==G.vexs[i])returni;return-1;}

2023年2月5日

對(duì)每個(gè)頂點(diǎn)vi建立一個(gè)單鏈表，把與vi有關(guān)聯(lián)的邊的信息鏈接起來(lái)，每個(gè)結(jié)點(diǎn)設(shè)為3個(gè)域；每個(gè)單鏈表有一個(gè)頭結(jié)點(diǎn)（設(shè)為2個(gè)域），存vi信息；adjvexnextarcinfodatafirstarc表結(jié)點(diǎn)頭結(jié)點(diǎn)鄰接點(diǎn)域，表示vi一個(gè)鄰接點(diǎn)的位置鏈域，指向vi下一個(gè)邊或弧的結(jié)點(diǎn)數(shù)據(jù)域，與邊有關(guān)信息（如權(quán)值）數(shù)據(jù)域，存儲(chǔ)頂點(diǎn)vi

信息鏈域，指向單鏈表的第一個(gè)結(jié)點(diǎn)

每個(gè)單鏈表的頭結(jié)點(diǎn)另外用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。鄰接表（鏈?zhǔn)剑┍硎痉?/p>

2023年2月5日

01234^1334^142^0注：鄰接表不唯一，因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的v1v2v3v4v523^142^0無(wú)向圖的鄰接表表示空間效率為O(n+2e)。若是稀疏圖(e<<n2)，比鄰接矩陣表示法O(n2)省空間。TD(Vi)=單鏈表中鏈接的結(jié)點(diǎn)個(gè)數(shù)v1v2v3v5v4v4

2023年2月5日

v1v2v3v4V4V3^V2V12^3^0^1鄰接表(出邊)V4V3V2V1^3^0^2^0逆鄰接表(入邊)有向圖的鄰接表表示空間效率為O(n+e)出度入度度：OD(Vi)＝單鏈出邊表中鏈接的結(jié)點(diǎn)數(shù)ID(Vi)＝鄰接點(diǎn)域?yàn)閂i的弧個(gè)數(shù)TD(Vi)=OD(Vi)+ID(Vi)

2023年2月5日

8064125當(dāng)鄰接表的存儲(chǔ)結(jié)構(gòu)形成后，圖便唯一確定！已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫(huà)出該網(wǎng)絡(luò)。

2023年2月5日

#defineMVNum100 //最大頂點(diǎn)數(shù)typedef

struct

ArcNode{ //邊結(jié)點(diǎn)

int

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

struct

ArcNode*nextarc;

//指向下一條邊的指針

OtherInfoinfo; //和邊相關(guān)的信息}ArcNode;typedef

struct

VNode{

VerTexTypedata; //頂點(diǎn)信息

ArcNode*firstarc; //指向第一條依附該頂點(diǎn)的邊的指針}VNode,AdjList[MVNum]; //AdjList表示鄰接表類型typedef

struct{

AdjListvertices; //鄰接表

int

vexnum,arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)}ALGraph;鄰接表的存儲(chǔ)表示

2023年2月5日

（1）輸入總頂點(diǎn)數(shù)和總邊數(shù)。（2）依次輸入點(diǎn)的信息存入頂點(diǎn)表中，使每個(gè)表頭結(jié)點(diǎn)的指針域初始化為NULL。（3）創(chuàng)建鄰接表?！舅惴ㄋ枷搿坎捎绵徑颖肀硎痉▌?chuàng)建無(wú)向網(wǎng)

2023年2月5日

StatusCreateUDG(ALGraph&G){

//采用鄰接表表示法，創(chuàng)建無(wú)向圖G

cin>>G.vexnum>>G.arcnum; //輸入總頂點(diǎn)數(shù)，總邊數(shù)

for(i=0;i<G.vexnum;++i){ //輸入各點(diǎn)，構(gòu)造表頭結(jié)點(diǎn)表

cin>>G.vertices[i].data; //輸入頂點(diǎn)值

G.vertices[i].firstarc=NULL; //初始化表頭結(jié)點(diǎn)的指針域?yàn)镹ULL}//for

for(k=0;k<G.arcnum;++k){ //輸入各邊，構(gòu)造鄰接表

cin>>v1>>v2; //輸入一條邊依附的兩個(gè)頂點(diǎn)

i=LocateVex(G,v1);j=LocateVex(G,v2);p1=newArcNode; //生成一個(gè)新的邊結(jié)點(diǎn)*p1

p1->adjvex=j; //鄰接點(diǎn)序號(hào)為j

p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;//將新結(jié)點(diǎn)*p1插入頂點(diǎn)vi的邊表頭部

p2=newArcNode;//生成另一個(gè)對(duì)稱的新的邊結(jié)點(diǎn)*p2

p2->adjvex=i; //鄰接點(diǎn)序號(hào)為i

p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2;//將新結(jié)點(diǎn)*p2插入頂點(diǎn)vj的邊表頭部

}//forreturnOK;}//CreateUDG

【算法描述】

2023年2月5日

優(yōu)點(diǎn)：空間效率高，容易尋找頂點(diǎn)的鄰接點(diǎn)；缺點(diǎn)：判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒(méi)有鄰接矩陣方便。鄰接表表示法的特點(diǎn)

2023年2月5日

v1v2v3v5v4v443210^1334^142^0v5v4v3v2v123^142^0（v1v2

v3v4v5）v1v2v3v4v500

0

0000

0000

0000000000000001

0

1010

1010

101110101011

1001

0

1010

1

010

1

01110101011

10鄰接矩陣與鄰接表表示法的關(guān)系1.聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。

2023年2月5日

2.區(qū)別：①對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān)）。②鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3.用途：鄰接矩陣多用于稠密圖；而鄰接表多用于稀疏圖鄰接矩陣與鄰接表表示法的關(guān)系

2023年2月5日

遍歷定義：從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次，就叫做圖的遍歷，它是圖的基本運(yùn)算。遍歷實(shí)質(zhì)：找每個(gè)頂點(diǎn)的鄰接點(diǎn)的過(guò)程。圖的特點(diǎn)：圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。6.3圖的遍歷

2023年2月5日

圖常用的遍歷：深度優(yōu)先搜索廣度優(yōu)先搜索解決思路：設(shè)置輔助數(shù)組

visited[n]，用來(lái)標(biāo)記每個(gè)被訪問(wèn)過(guò)的頂點(diǎn)。初始狀態(tài)為0i

被訪問(wèn)，改visited[i]為1，防止被多次訪問(wèn)怎樣避免重復(fù)訪問(wèn)？

2023年2月5日

基本思想：——仿樹(shù)的先序遍歷過(guò)程。v1v1v2v3v8v7v6v4v5DFS結(jié)果→→→→→→→v2v4v8v5v3v6v7起點(diǎn)深度優(yōu)先搜索(DFS－Depth_FirstSearch)

2023年2月5日

深度優(yōu)先搜索的步驟簡(jiǎn)單歸納：訪問(wèn)起始點(diǎn)v;若v的第1個(gè)鄰接點(diǎn)沒(méi)訪問(wèn)過(guò)，深度遍歷此鄰接點(diǎn)；若當(dāng)前鄰接點(diǎn)已訪問(wèn)過(guò)，再找v的第2個(gè)鄰接點(diǎn)重新遍歷。

2023年2月5日

深度優(yōu)先搜索的步驟詳細(xì)歸納：在訪問(wèn)圖中某一起始頂點(diǎn)

v

后，由

v出發(fā)，訪問(wèn)它的任一鄰接頂點(diǎn)

w1；再?gòu)?/p>

w1出發(fā)，訪問(wèn)與

w1鄰接但還未被訪問(wèn)過(guò)的頂點(diǎn)

w2；然后再?gòu)?/p>

w2出發(fā)，進(jìn)行類似的訪問(wèn)，…

如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn)

u為止。起點(diǎn)

2023年2月5日

深度優(yōu)先搜索的步驟詳細(xì)歸納：接著，退回一步，退到前一次剛訪問(wèn)過(guò)的頂點(diǎn)，看是否還有其它沒(méi)有被訪問(wèn)的鄰接頂點(diǎn)。

如果有，則訪問(wèn)此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類似的訪問(wèn)；

如果沒(méi)有，就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程，直到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。起點(diǎn)v2→v1→v3→v5→v4→v6

2023年2月5日

討論1：計(jì)算機(jī)如何實(shí)現(xiàn)DFS？123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS結(jié)果鄰接矩陣A輔助數(shù)組visited[n]起點(diǎn)v2→v1→v3→v5→v4→v6——開(kāi)輔助數(shù)組

visited[n]！123456101110021000103100010410000150110006000100

2023年2月5日

voidDFS(AMGraphG,intv){ //圖G為鄰接矩陣類型

cout<<v;visited[v]=true; //訪問(wèn)第v個(gè)頂點(diǎn)

for(w=0;w<G.vexnum;w++) //依次檢查鄰接矩陣v所在的行

if((G.arcs[v][w]!=0)&&(!visited[w]))DFS(G,w);//w是v的鄰接點(diǎn)，如果w未訪問(wèn)，則遞歸調(diào)用DFS}討論2：DFS算法如何編程？——可以用遞歸算法！

2023年2月5日

討論3：在圖的鄰接表中如何進(jìn)行DFS？v0→v1→v2→v3DFS結(jié)果00000123輔助數(shù)組visited[n]1000110011101111—照樣借用visited[n]！起點(diǎn)0123

2023年2月5日

討論4：鄰接表的DFS算法如何編程？voidDFS(ALGraphG,intv){ //圖G為鄰接表類型

cout<<v;visited[v]=true; //訪問(wèn)第v個(gè)頂點(diǎn)

p=G.vertices[v].firstarc;//p指向v的邊鏈表的第一個(gè)邊結(jié)點(diǎn)while(p!=NULL){ //邊結(jié)點(diǎn)非空

w=p->adjvex; //表示w是v的鄰接點(diǎn)

if(!visited[w])DFS(G,w); //如果w未訪問(wèn)，則遞歸調(diào)用DFSp=p->nextarc; //p指向下一個(gè)邊結(jié)點(diǎn)

}}——仍可用遞歸算法

2023年2月5日

用鄰接矩陣來(lái)表示圖，遍歷圖中每一個(gè)頂點(diǎn)都要從頭掃描該頂點(diǎn)所在行，時(shí)間復(fù)雜度為O(n2)。用鄰接表來(lái)表示圖，雖然有2e

個(gè)表結(jié)點(diǎn)，但只需掃描e個(gè)結(jié)點(diǎn)即可完成遍歷，加上訪問(wèn)n個(gè)頭結(jié)點(diǎn)的時(shí)間，時(shí)間復(fù)雜度為O(n+e)。結(jié)論：稠密圖適于在鄰接矩陣上進(jìn)行深度遍歷；稀疏圖適于在鄰接表上進(jìn)行深度遍歷。DFS算法效率分析

2023年2月5日

基本思想：——仿樹(shù)的層次遍歷過(guò)程廣度優(yōu)先搜索(BFS－Breadth_FirstSearch)v1v1v2v3v8v7v6v4v5BFS結(jié)果→→→→v2v3→v4v5→v6v7→v8起點(diǎn)

2023年2月5日

簡(jiǎn)單歸納：在訪問(wèn)了起始點(diǎn)v之后，依次訪問(wèn)v的鄰接點(diǎn)；然后再依次訪問(wèn)這些頂點(diǎn)中未被訪問(wèn)過(guò)的鄰接點(diǎn)；直到所有頂點(diǎn)都被訪問(wèn)過(guò)為止。廣度優(yōu)先搜索是一種分層的搜索過(guò)程，每向前走一步可能訪問(wèn)一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過(guò)程，其算法也不是遞歸的。廣度優(yōu)先搜索的步驟

2023年2月5日

討論1：計(jì)算機(jī)如何實(shí)現(xiàn)BFS？鄰接表—除輔助數(shù)組visited[n]外，還需再開(kāi)一輔助隊(duì)列起點(diǎn)輔助隊(duì)列v2已訪問(wèn)過(guò)了BFS遍歷結(jié)果入隊(duì)！初始f=n-1,r=0

2023年2月5日

（1）從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問(wèn)v，并置visited[v]的值為true，然后將v進(jìn)隊(duì)。（2）只要隊(duì)列不空，則重復(fù)下述處理。①隊(duì)頭頂點(diǎn)u出隊(duì)。②依次檢查u的所有鄰接點(diǎn)w，如果visited[w]的值為false，則訪問(wèn)w，并置visited[w]的值為true，然后將w進(jìn)隊(duì)?！舅惴ㄋ枷搿?/p>

2023年2月5日

voidBFS(GraphG,intv){//按廣度優(yōu)先非遞歸遍歷連通圖G

cout<<v;visited[v]=true; //訪問(wèn)第v個(gè)頂點(diǎn)

InitQueue(Q); //輔助隊(duì)列Q初始化，置空

EnQueue(Q,v); //v進(jìn)隊(duì)

while(!QueueEmpty(Q)){ //隊(duì)列非空

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

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

if(!visited[w]){ //w為u的尚未訪問(wèn)的鄰接頂點(diǎn)

cout<<w;visited[w]=true; EnQueue(Q,w);//w進(jìn)隊(duì)

}//if}//while}//BFS

【算法描述】

2023年2月5日

如果使用鄰接矩陣，則BFS對(duì)于每一個(gè)被訪問(wèn)到的頂點(diǎn)，都要循環(huán)檢測(cè)矩陣中的整整一行（

n個(gè)元素），總的時(shí)間代價(jià)為O(n2)。用鄰接表來(lái)表示圖，雖然有2e個(gè)表結(jié)點(diǎn)，但只需掃描e個(gè)結(jié)點(diǎn)即可完成遍歷，加上訪問(wèn)n個(gè)頭結(jié)點(diǎn)的時(shí)間，時(shí)間復(fù)雜度為O(n+e)。BFS算法效率分析

2023年2月5日

空間復(fù)雜度相同，都是O(n)(借用了堆?；蜿?duì)列）；時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無(wú)關(guān)。DFS與BFS算法效率比較

2023年2月5日

最小生成樹(shù)最短路徑拓?fù)渑判蜿P(guān)鍵路徑6.4圖的應(yīng)用

2023年2月5日

極小連通子圖：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。生成樹(shù)：包含圖G所有頂點(diǎn)的極小連通子圖（n-1條邊）。G1的生成樹(shù)連通圖G1

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2最小生成樹(shù)

2023年2月5日

DFS生成樹(shù)鄰接表01234^1334^142^0v4v3v2v1v023^142^0v0v2v1v4v3BFS生成樹(shù)v0v1v3v2v4無(wú)向連通圖畫(huà)出下圖的生成樹(shù)v0v1v2v4v4v3

2023年2月5日

求最小生成樹(shù)首先明確：使用不同的遍歷圖的方法，可以得到不同的生成樹(shù)從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹(shù)。按照生成樹(shù)的定義，n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹(shù)有n個(gè)頂點(diǎn)、n-1條邊。目標(biāo)：在網(wǎng)的多個(gè)生成樹(shù)中，尋找一個(gè)各邊權(quán)值之和最小的生成樹(shù)

2023年2月5日

必須只使用該網(wǎng)中的邊來(lái)構(gòu)造最小生成樹(shù)；必須使用且僅使用n-1條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)不能使用產(chǎn)生回路的邊構(gòu)造最小生成樹(shù)的準(zhǔn)則

2023年2月5日

欲在n個(gè)城市間建立通信網(wǎng)，則n個(gè)城市應(yīng)鋪n-1條線路；但因?yàn)槊織l線路都會(huì)有對(duì)應(yīng)的經(jīng)濟(jì)成本，而n個(gè)城市可能有n(n-1)/2條線路，那么，如何選擇n–1條線路，使總費(fèi)用最少？數(shù)學(xué)模型：頂點(diǎn)———表示城市，有n個(gè)；邊————表示線路，有n–1條；邊的權(quán)值—表示線路的經(jīng)濟(jì)代價(jià)；連通網(wǎng)——表示n個(gè)城市間通信網(wǎng)。顯然此連通網(wǎng)是一個(gè)生成樹(shù)！最小生成樹(shù)的典型用途

2023年2月5日

Prim（普里姆）算法Kruskal（克魯斯卡爾）算法Prime算法:

歸并頂點(diǎn)，與邊數(shù)無(wú)關(guān)，適于稠密網(wǎng)Kruskal算法：歸并邊，適于稀疏網(wǎng)如何求最小生成樹(shù)

2023年2月5日

設(shè)連通網(wǎng)絡(luò)N={V,E}1.從某頂點(diǎn)u0

出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0,v)，將其頂點(diǎn)加入到生成樹(shù)的頂點(diǎn)集合U中2.每一步從一個(gè)頂點(diǎn)在U中，而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點(diǎn)加入到U中3.直到所有頂點(diǎn)都加入到生成樹(shù)頂點(diǎn)集合U中為止普里姆算法的基本思想－－歸并頂點(diǎn)

2023年2月5日

應(yīng)用普里姆算法構(gòu)造最小生成樹(shù)的過(guò)程

2023年2月5日

設(shè)連通網(wǎng)絡(luò)N={V,E}1.構(gòu)造一個(gè)只有n個(gè)頂點(diǎn)，沒(méi)有邊的非連通圖T={V,},每個(gè)頂點(diǎn)自成一個(gè)連通分量2.在E中選最小權(quán)值的邊,若該邊的兩個(gè)頂點(diǎn)落在不同的連通分量上，則加入T中；否則舍去，重新選擇3.重復(fù)下去，直到所有頂點(diǎn)在同一連通分量上為止克魯斯卡爾算法的基本思想－歸并邊

2023年2月5日

應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程√√√√×√×√

2023年2月5日

用有向圖來(lái)描述一個(gè)工程或系統(tǒng)的進(jìn)行過(guò)程。一個(gè)工程可以分為若干個(gè)子工程，只要完成了這些子工程（活動(dòng)），就可以導(dǎo)致整個(gè)工程的完成。①AOV網(wǎng)(ActivityOnVertices)—用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)②AOE網(wǎng)(ActivityOnEdges)—用邊表示活動(dòng)的網(wǎng)絡(luò)比如教學(xué)計(jì)劃的制定哪些課程是必須先修的，哪些課程是可以并行學(xué)習(xí)的。有向無(wú)環(huán)圖及其應(yīng)用

2023年2月5日

C1

高等數(shù)學(xué)

C2

程序設(shè)計(jì)基礎(chǔ)

C3

離散數(shù)學(xué)C1,C2

C4

數(shù)據(jù)結(jié)構(gòu)C3,C2C5

高級(jí)語(yǔ)言程序設(shè)計(jì)C2C6

編譯方法C5,C4C7

操作系統(tǒng)C4,C9C8

普通物理C1C9

計(jì)算機(jī)原理C8

課程代號(hào)課程名稱先修課程

2023年2月5日

學(xué)生課程學(xué)習(xí)工程圖數(shù)據(jù)結(jié)構(gòu)離散數(shù)學(xué)程序設(shè)計(jì)基礎(chǔ)對(duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判颍玫降耐負(fù)溆行蛐蛄袨镃1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C6

2023年2月5日

輸入AOV網(wǎng)絡(luò)。令n為頂點(diǎn)個(gè)數(shù)。 在AOV網(wǎng)絡(luò)中選一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn),并輸出之;

從圖中刪去該頂點(diǎn),同時(shí)刪去所有它發(fā)出的有向邊;

重復(fù)以上2、3步,直到：全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿?；或：圖中還有未輸出的頂點(diǎn)，但已跳出處理循環(huán)。這說(shuō)明圖中還剩下一些頂點(diǎn)，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點(diǎn)了。這時(shí)AOV網(wǎng)絡(luò)中必定存在有向環(huán)。拓?fù)渑判蛩惴ǖ乃枷耄貜?fù)選擇沒(méi)有直接前驅(qū)的頂點(diǎn)

2023年2月5日

拓?fù)渑判虻倪^(guò)程

2023年2月5日

最后得到拓?fù)湫蛄?/p>

C4,C0,C3,C2,C1,C5

。滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對(duì)于本來(lái)沒(méi)有這種關(guān)系的頂點(diǎn)，如C4和C2，也排出了先后次序關(guān)系。

2023年2月5日

典型用途：交通問(wèn)題。如：城市A到城市B有多條線路，但每條線路的交通費(fèi)（或所需時(shí)間）不同，那么，如何選擇一條線路，使總費(fèi)用（或總時(shí)間）最少？問(wèn)題抽象：在帶權(quán)有向圖中A點(diǎn)（源點(diǎn)）到達(dá)B點(diǎn)（終點(diǎn)）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。（注：最短路徑與最小生成樹(shù)不同，路徑上不一定包含n個(gè)頂點(diǎn)）最短路徑

2023年2月5日

一頂點(diǎn)到其余各頂點(diǎn)兩種常見(jiàn)的最短路徑問(wèn)題：一、單源最短路徑—用Dijkstra（迪杰斯特拉）算法二、所有頂點(diǎn)間的最短路徑—用Floyd（弗洛伊德）算法任意兩頂點(diǎn)之間

2023年2月5日

目的：

設(shè)一有向圖G=（V,E），已知各邊的權(quán)值，以某指定點(diǎn)v0為源點(diǎn)，求從v0到圖的其余各點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。源點(diǎn)從F→A的路徑有4條：①F→A：24②F→B→A：5＋18=23③F→B→C→A：5+7+9=21④

F→D→C→A：25+12+9=36又：從F→B的最短路徑是哪條？從F→C的最短路徑是哪條？單源最短路徑問(wèn)題（Dijkstra算法）

2023年2月5日

v0(v0,v1)10源點(diǎn)終點(diǎn)

最

短路

徑路徑長(zhǎng)度(v0,v1,v2)(v0,v3,v2)(v0,v3)30

v1

v2

v3

v4100(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)例2：6001234509070討論：計(jì)算機(jī)如何自動(dòng)求出這些最短路徑？(v0,v1,v2,v4)60

2023年2月5日

先找出從源點(diǎn)v0到各終點(diǎn)vk的直達(dá)路徑（v0,vk），即通過(guò)一條弧到達(dá)的路徑。從這些路徑中找出一條長(zhǎng)度最短的路徑（v0,u）,然后對(duì)其余各條路徑進(jìn)行適當(dāng)調(diào)整：若在圖中存在?。╱,vk），且（v0,u）+（u,vk）<（v0,vk）,則以路徑（v0,u,vk）代替（v0,vk）。在調(diào)整后的各條路徑中，再找長(zhǎng)度最短的路徑，依此類推。Dijkstra算法的思想

2023年2月5日

①初始化：● 將源點(diǎn)v0加到S中，即S[v0]

=

true；● 將v0到各個(gè)終點(diǎn)的最短路徑長(zhǎng)度初始化為權(quán)值，即D[i]

=

G.arcs[v0][vi]，(vi∈V

?

S)；● 如果v0和頂點(diǎn)vi之間有弧，則將vi的前驅(qū)置為v0，即Path[i]

=

v0，否則Path[i]

=

?1。②選擇下一條最短路徑的終點(diǎn)vk，使得：

D[k]

=

Min{D[i]|vi∈V

?

S}【算法思想】

2023年2月5日

③將vk加到S中，即S[vk]

=

true。④更新從v0出發(fā)到集合V

?

S上任一頂點(diǎn)的最短路徑的長(zhǎng)度，同時(shí)更改vi的前驅(qū)為vk。若D[k]+G.arcs[k][i]<D[i]，則D[i]=D[k]+G.arcs[k][i];Path[i]=k;。⑤重復(fù)②～④

n

?

1次，即可按照路徑長(zhǎng)度的遞增順序，逐個(gè)求得從v0到圖上其余各頂點(diǎn)的最短路徑?！舅惴ㄋ枷搿?/p>

2023年2月5日

2023年2月5日

(v0,v2)+(v2,v3)<(v0,v3)終點(diǎn)

從v0到各終點(diǎn)的dist值和最短路徑v1v2v3v4v5vjS之外的當(dāng)前最短路徑之頂點(diǎn)60{v0,v2,v3}50{v0,v4,v3}30{v0,v4}90{v0,v4,v5}60{v0,v4,v3,v5}5540312100603010102050s{v0,v2}{v0,v2,v4}{v0,v2,v4