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

圖的基本概念圖的存儲(chǔ)表示圖的遍歷圖的應(yīng)用第9章圖圖的基本概念圖(Graph)

圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)

其中:V={x|x

某個(gè)數(shù)據(jù)對(duì)象}是頂點(diǎn)的有窮非空集合；

E={(x,y)|x,y

V}

或

E={<x,y>|x,y

V}是頂點(diǎn)之間關(guān)系的有窮集合。125634abcd無(wú)向圖有向圖V={1,2,3,4,5,6}E={(1,2),(1,5),(1,6),(2,3),(2,4),(3,4),(4,5),(4,6)}（邊）V={a,b,c,d}E={<a,b>,<a,d>,<b,d>,<c,a>,<d,a>,<d,b>,

<d,c>}（弧）<弧尾頂點(diǎn)，弧頭頂點(diǎn)>ADTGraph{數(shù)據(jù)對(duì)象:

D={ai|1in,n0,ai屬Elemtype類(lèi)型

數(shù)據(jù)關(guān)系:R1={<ai,aj>|ai,aj

D,1in,1jn,

每個(gè)元素可以有多個(gè)直接前驅(qū)和可以有多個(gè)直接后繼}

基本運(yùn)算:InitGraph(t);ClearGraph(t);DSF(t);BSF(t);

}抽象數(shù)據(jù)類(lèi)型數(shù)的定義125634abcd頂點(diǎn)的度

一個(gè)頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中,頂點(diǎn)的度=入度+出度。頂點(diǎn)v的入度

是以v為終點(diǎn)的有向邊的條數(shù),記作

ID(v);頂點(diǎn)v的出度

是以v為始點(diǎn)的有向邊的條數(shù),記作

OD(v)。TD(v)=ID(v)+OD(v)例：TD(1)=3TD(4)=4TD(5)=2例：TD(b)=ID(b)+OD(b)TD(d)=ID(d)+OD(d)=2+1=3=2+3=5子圖

設(shè)有兩個(gè)圖G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,則稱(chēng)圖G’是圖G的子圖。0123子圖0130123023權(quán)

某些圖的邊具有與它相關(guān)的數(shù),稱(chēng)為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。任意圖都是其自身子圖abcd8

19341123路徑

在圖G＝(V,E)中,若從頂點(diǎn)vi出發(fā),沿一些邊經(jīng)過(guò)一些頂點(diǎn)

vp1,vp2,…,

vpm，到達(dá)頂點(diǎn)vj。則稱(chēng)頂點(diǎn)序列

(vi

vp1vp2...vpm

vj)

為從頂點(diǎn)vi到頂點(diǎn)vj

的路徑。125634例：V1到V3的路徑：123、123423、16423、1544……..路徑長(zhǎng)度

非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。簡(jiǎn)單路徑

若路徑上各頂點(diǎn)v1,v2,...,vm

均不互相重復(fù),則稱(chēng)這樣的路徑為簡(jiǎn)單路徑。回路

若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm

重合,則稱(chēng)這樣的路徑為回路或環(huán)。

路徑長(zhǎng)度：

2、5、4、3……..強(qiáng)連通圖與強(qiáng)連通分量

在有向圖中,

若對(duì)于每一對(duì)頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱(chēng)此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。abcd

abcd

強(qiáng)連通圖非強(qiáng)連通圖cabd

兩個(gè)強(qiáng)連通分量圖的存儲(chǔ)表示鄰接矩陣(AdjacencyMatrix)aij=abefcdvexs123456abcdefA=010011101100010100011011100100100100利用數(shù)組vertex[]存儲(chǔ)頂點(diǎn)基本思想：利用矩陣A表示頂點(diǎn)之間的關(guān)系無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)矩陣aij=A=abcd8

19341123vexs1234A=abcd1111111000000000A=abefcdvexs123456abcdef482196

731084931112341984198262633107107A=010011101100010100011011100100100100鄰接矩陣所占存儲(chǔ)空間與頂點(diǎn)數(shù)成正比但圖中有無(wú)關(guān)系都分配存儲(chǔ)空間邊的插入和刪除不影響存儲(chǔ)空間大小0100？求頂點(diǎn)的度建立鄰接矩陣*鄰接矩陣初始化（置0或）*輸入頂點(diǎn)數(shù)，弧數(shù)ga->nga->e*輸入各頂點(diǎn)信息存入ga->vexs[]*輸入各邊信息（或權(quán)值）存入ga->edages[][]A=vexs1234鄰接表(AdjacencyList)基本思想：在無(wú)向圖中，將依附于某個(gè)頂點(diǎn)的所有邊（邊結(jié)點(diǎn)）以單鏈表形式鏈接，每個(gè)鏈表設(shè)立一個(gè)表頭結(jié)點(diǎn)。abefcd123456abcdef(a,b)(a,e)(a,f)256(b,a)(b,c)(b,d)134(c,b)(c,d)24(d,b)(d,c)(d,e)(d,f)2356(e,a)(e,d)(f,a)(f,d)1414datafirstarc4

82196

73

10481987426adjvexinfonextarc36107231910adjvexnextarc注：在無(wú)向圖中每個(gè)邊生成兩個(gè)結(jié)點(diǎn)？插入和刪除(d,f)=(f,d)?求頂點(diǎn)的度datafirstarc1234abcd8

59371113鄰接表：在有向圖中，將以該頂點(diǎn)作為弧尾頂點(diǎn)的所有弧鏈接成單鏈表。abcd<a,b><a,d>2847<b,d>49<c,a>13<d,a><d,b><d,c>15211313datafirstarc1234abcd<c,a><d,a>3345<a,b><d,b><d,c>413<a,d><b,d>184111749逆鄰接表逆鄰接表：在有向圖中，將以該頂點(diǎn)作為弧頭頂點(diǎn)的所有弧鏈接成單鏈表。？求頂點(diǎn)的度datafirstarcadjvexinfonextarc123456abcdef256134242356141448198742636107231910abefcd4

82196

73

10建立鄰接表*鄰接表初始化（置各單鏈表為空表ga[].firstarc=NULL）*輸入各頂點(diǎn)信息存入

ga[].data*輸入各邊信息，生成新結(jié)點(diǎn)，插入相應(yīng)的單鏈中。abcd8

59371113datafirstarc1234abcd2847491315211313鄰接表的基本操作插入：

<b,c>*確定單鏈表*生成新結(jié)點(diǎn)636*頭插鏈表注：有向圖只插入(或刪除）一個(gè)結(jié)點(diǎn)，而無(wú)向圖需插入（或刪除）兩個(gè)結(jié)點(diǎn)。刪除：

<d,c>*確定結(jié)點(diǎn)*刪除結(jié)點(diǎn)*釋放結(jié)點(diǎn)<c,a>十字鏈表(有向圖)abcd8

59371113a

a

a

b

a

c

a

d

a

12

<a,b>a

14<a,d>a

24

<b,d>a

31

<c,a>a

41

<d,a>a

42

<d,b>a

43

<d,c>tailvexheadvexhlinktlinkinfo弧結(jié)點(diǎn)datafirstinfirstout頂點(diǎn)結(jié)點(diǎn)a

46(d,f)abefcd4

82196

73

10ABCDEFa

12(a,b)a

15(a,e)a

16(a,f)a

23(b,c)a

24(b,d)a

34(c,d)a

45(d,e)鄰接多重表（無(wú)向圖）markivexilinkjvexjlink邊結(jié)點(diǎn)datafirstedge頂點(diǎn)結(jié)點(diǎn)datafirstedge頂點(diǎn)結(jié)點(diǎn)markivexilinkjvexjlink邊結(jié)點(diǎn)typedefstructENode{intmark;intivex,jvex;structENode*ilink,*jlink;InfoTypeinfo;}ENode;鄰接多重表的數(shù)據(jù)類(lèi)型typedefstructVNode{VertexTypedata;ENode*firstedge;}VNode;圖的遍歷(GraphTraversal)圖的遍歷從圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次。為了避免重復(fù)訪問(wèn)，設(shè)置一個(gè)的輔助數(shù)組visited[]標(biāo)志各頂點(diǎn)是否被訪問(wèn)過(guò)。圖的遍歷的分類(lèi)：深度優(yōu)先搜索

DFS(DepthFirstSearch)廣度優(yōu)先搜索

BFS(BreadthFirstSearch)DFS(v0)的主要步驟：(1)訪問(wèn)頂點(diǎn)v0(2)確定第一鄰接點(diǎn)w(3)若w未訪問(wèn)，則從w出發(fā)進(jìn)行遍歷DFS(w)(4)確定下一個(gè)鄰接點(diǎn)w(5)重復(fù)(3)(4)直到所有鄰接點(diǎn)都處理結(jié)束深度優(yōu)先搜索DFS(DepthFirstSearch)DFS(v0){visite(v0);visited[v0]=1;w=FIRST(v0);while(存在w){if(visited[w]==0)DFS(w);w=NEXT(v0,w);}}

125634datafirstarc123456abcdef5623142435624114DFS(v0){visite(v0);visited[v0]=1;w=FIRST(v0);while(存在w){if(visited[v0]==0)DFS(w);w=NEXT(v0,w);}}

第一鄰接點(diǎn):p=G->adjlist[v].firstarc下一個(gè)鄰接點(diǎn)：p=p->nextarcBFS(v0){init(Q);visite(v0);visited[v0]=1;enqueue(Q,v0);while(!empty(Q)){v=dequeue(Q);w=FIRST(v);while(存在w){if(visited[w]==0){visite(w);visited[w]=1;enqueue(Q,w);}w=NEXT(v,w);}}}125634datafirstarc123456abcdef5623142435624114第一鄰接點(diǎn):p=G->adjlist[v].firstarc下一個(gè)鄰接點(diǎn)：p=p->nextarc深度優(yōu)先搜索DFS

(DepthFirstSearch)深度優(yōu)先搜索過(guò)程的示例ACDEGBFIHACDEGBFIH123456791234567889深度優(yōu)先搜索過(guò)程

深度優(yōu)先生成樹(shù)前進(jìn)回退廣度優(yōu)先搜索BFS

(BreadthFirstSearch

)廣度優(yōu)先搜索的示例ACDEGBFIH123456789123456789廣度優(yōu)先搜索過(guò)程ACDEGBFHI廣度優(yōu)先生成樹(shù)

問(wèn)題：當(dāng)對(duì)非連通圖遍歷時(shí),從圖中某一頂點(diǎn)出發(fā),利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn),只能訪問(wèn)到該頂點(diǎn)所在的最大連通子圖(連通分量)的所有頂點(diǎn)。ACDEBFGIHJONMLK非連通無(wú)向圖要實(shí)現(xiàn)任意圖的遍歷，則要掃描圖中的所有頂點(diǎn)。TRQVER(){for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]=0)DFS(vi);}TRQVER(){for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]=0)BFS(vi);}ACDEBFGIHJONMLK非連通無(wú)向圖ACDEBFGHIJKONML非連通圖的連通分量對(duì)于非連通的無(wú)向圖，所有連通分量的生成樹(shù)組成了非連通圖的生成森林。ACDEBFGIHJONMLK非連通無(wú)向圖ACDEBFGIHJONMLK非連通圖的連通分量1624351624351624351251042312104312542深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷遍歷序列:123456遍歷序列:125634連通圖生成樹(shù)不同的遍歷得到不同的生成樹(shù)權(quán)值之和:20權(quán)值之和:14最小生成樹(shù)

(minimumcostspanningtree)最小生成樹(shù)----在一個(gè)連通網(wǎng)得到的所有生成樹(shù)中,權(quán)值之和最小的生成樹(shù)稱(chēng)為最小生成樹(shù).3564257156146352使用且僅使用該網(wǎng)絡(luò)中的n-1條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)必須頂點(diǎn)；不能使用產(chǎn)生回路的邊；各邊上的權(quán)值的總和達(dá)到最小。應(yīng)用:在若干個(gè)城市中建立通訊網(wǎng)。MST性質(zhì)：設(shè)G=（V,E）是一個(gè)連通網(wǎng)絡(luò)，U是頂點(diǎn)集V的一個(gè)子集。若（u,v）是G中所有的一個(gè)端點(diǎn)在U（即uU）里，另一個(gè)端點(diǎn)不在U（即vV-U）里的邊中，具有最小權(quán)值的一條邊，則一定存在G的一棵最小生成樹(shù)包含此邊（u,v）。UV-U反正法證明：假設(shè)G中任何一棵最小生成樹(shù)中都不包含邊（u,v）。v’u’vu設(shè)T是一棵最小生成樹(shù)，不包（u,v）,一定要包含一條邊（u’,v’）。若用（u,v）取代（u’,v’）得到一棵新的生成樹(shù)T’,由于W（u,v）<W（u,v），則T’的權(quán)<T的權(quán)，與假設(shè)矛盾。535642571561463525461356242361657756643255普里姆(Prim)算法基本思想：

設(shè)連通網(wǎng)絡(luò)N=(V,E)

，最小生成樹(shù)T=(U,TE)（1）初始狀態(tài)：U={v0},TE=。（2）選擇滿(mǎn)足MST性質(zhì)的一條邊（u,v）,其中uU，vV-U，且邊（u,v）的權(quán)值最小。（3）吸收vU,吸收（u,v）TE。（4）重復(fù)（2）（3），直到U=V。553512461423606577556321435642571560352410615

6053150754570

235

06

4260cost[][]lowcostclosest0615

00000

0最小5540最小222最小最小2050034012345cost[][]:利用鄰接矩陣法存儲(chǔ)圖i=j:cost[i][j]=0closest[]和lowcost[]分別存儲(chǔ)頂點(diǎn)序號(hào)和權(quán)值，當(dāng)lowcost[i]=0:頂點(diǎn)i已經(jīng)吸收到U。當(dāng)lowcost[i]0:頂點(diǎn)i未被吸收V-U。當(dāng)0<lowcost[i]<：存儲(chǔ)頂點(diǎn)i與頂點(diǎn)closest[i]之間的權(quán)值。當(dāng)lowcost[i]=：

頂點(diǎn)i未與已吸收的頂點(diǎn)之間沒(méi)有關(guān)系（邊）。3564257156146352克魯斯卡爾(Kruskal)算法基本思想：設(shè)有有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)

N={V,E

},最初先構(gòu)造一個(gè)只有n個(gè)頂點(diǎn),沒(méi)有邊的非連通圖

T={V,

},圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。當(dāng)在E中選到一條具有最小權(quán)值的邊時(shí),若該邊的兩個(gè)頂點(diǎn)落在不同的連通分量上，則將此邊加入到T中;否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此重復(fù)下去,直到所有頂點(diǎn)在同一個(gè)連通分量上為止。54613212345回路最短路徑(ShortestPath)最短路徑問(wèn)題：從圖中某一頂點(diǎn)(稱(chēng)為源點(diǎn))到達(dá)另一頂點(diǎn)(稱(chēng)為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。問(wèn)題解法:邊上權(quán)值非負(fù)情形的單源最短路徑問(wèn)題—

Dijkstra算法邊上權(quán)值為任意值的單源最短路徑問(wèn)題—Bellman和Ford算法所有頂點(diǎn)之間的最短路徑—Floyd算法74613257361110142211107461325736111014227221.2--101.3--2arrive1.3.4--41.3.6--13

41.3.4.5--81.3.4.6--101115:path=1345length=8arrive1.3.4.5.7--1514:path=134length=41.3.4.5.2--9107461325112:path=13452length=913:path=13length=2arrive616:path=1346length=10arrive31.3.4.6.7--13717:path=13467length=13arrivearrive算法思想:

首先求出長(zhǎng)度最短的一條最短路徑，再參照它求出長(zhǎng)度次短的一條最短路徑，依次類(lèi)推，直到從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑全部求出為止。Dijkstra算法0102

100

12

0211

2046140

71160373011107461325736111014227221.2--101.3--2arrive1.3.4--41.3.6--13

41.3.4.5--81.3.4.6--1011arrive1.3.4.5.7--151.3.4.5.2--91074613251arrive6arrive31.3.4.6.7--137arrivearrive

sdistpath12345671000000Si=0未到達(dá)Si=1已到達(dá)記錄v0->vi可達(dá)的距離0102

記錄到達(dá)vi的路徑1111111最小(Si=0)121修正:dist[min]+cost[min][i]<dist[i]?0133043最小(Si=0)1430840104最小(Si=0)1840950155最小(Si=0)195最小(Si=0)110401361136path=1346710432101003050206010V0V1

V0V1

10V0V3

V0V3

30V0V2

V0V3V2

50V0V4

V0V3V2V4

50拓?fù)渑判?TopologicalSort)(AOV網(wǎng))計(jì)劃、施工過(guò)程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個(gè)叫做“活動(dòng)”的子工程。完成了這些活動(dòng)，這個(gè)工程就可以完成了。例如，計(jì)算機(jī)專(zhuān)業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門(mén)課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。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)課程名稱(chēng)先修課程C8C3C5C4C9C6C7C1C2學(xué)生課程學(xué)習(xí)工程圖可以用有向圖表示一個(gè)工程。在這種有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊<Vi,Vj>表示活動(dòng)Vi必須先于活動(dòng)Vj

進(jìn)行。這種有向圖叫做頂點(diǎn)表示活動(dòng)的AOV網(wǎng)絡(luò)(ActivityOnVertices)。在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路,即有向環(huán)。如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。因此，對(duì)給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。檢測(cè)有向環(huán)的一種方法是對(duì)AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄?。即將各個(gè)頂點(diǎn)(代表各個(gè)活動(dòng))排列成一個(gè)線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿(mǎn)足。拓?fù)渑判駽8C3C5C4C9C6C7C1C2拓?fù)渑判?---①在AOV網(wǎng)絡(luò)中選一個(gè)沒(méi)有直接前驅(qū)（度為0）的頂點(diǎn),輸出；

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

重復(fù)以上

①

②,直到輸出所有頂點(diǎn)或沒(méi)有度為0的頂點(diǎn)。C1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C6C0C1C2C3C4C5拓?fù)渑判虻倪^(guò)程(a)有向無(wú)環(huán)圖C2C5C1C0C3(b)輸出頂點(diǎn)C4C4C1C2C5C3(c)輸出頂點(diǎn)C0C0C2C5C1C3(d)輸出頂點(diǎn)C3V1V2V3V4V5V6V3123456240012V1V2V3V4V5V62261262拓?fù)湫蛄校篤331V4V410V5V5020V1V11V6V60V2V2

51關(guān)鍵路徑(CriticalPath)(AOE網(wǎng)絡(luò))頂點(diǎn)Vi表示事件，弧ak表示活動(dòng)，其權(quán)值為該活動(dòng)持續(xù)的時(shí)間。每個(gè)事件發(fā)生時(shí)在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可是開(kāi)始。問(wèn)題：（1）工程至少需要多少時(shí)間？最短時(shí)間（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？關(guān)鍵路徑a9=21325a1=6a2=47689a10=2a8=7a5=1a6=3a7=9a3=5a4=14a11=4幾個(gè)與計(jì)算關(guān)鍵活動(dòng)有關(guān)的量：①

事件Vi的最早可能開(kāi)始時(shí)間Ve(i)

②

事件Vi的最遲允許開(kāi)始時(shí)間Vl[i]③

活動(dòng)ak的最早可能開(kāi)始時(shí)間

e[k]④

活動(dòng)ak

的最遲允許開(kāi)始時(shí)間

l[k]

⑤

時(shí)間余量

l[k]-e[k]

a9=21325a1=6a2=47689a10=2a8=5a5=1a6=3a7=9a3=5a4=14a11=4Ve123456