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

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

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

Graph＝(V,E)

其中:V={x|x

某個數(shù)據(jù)對象}是頂點的有窮非空集合；

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

V}

或

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

V}是頂點之間關(guān)系的有窮集合。125634abcd無向圖有向圖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>}（?。?lt;弧尾頂點，弧頭頂點>ADTGraph{數(shù)據(jù)對象:

D={ai|1in,n0,ai屬Elemtype類型

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

D,1in,1jn,

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

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

}抽象數(shù)據(jù)類型數(shù)的定義125634abcd頂點的度

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

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

ID(v);頂點v的出度

是以v為始點的有向邊的條數(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＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,則稱圖G’是圖G的子圖。0123子圖0130123023權(quán)

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

19341123路徑

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

vp1,vp2,…,

vpm，到達頂點vj。則稱頂點序列

(vi

vp1vp2...vpm

vj)

為從頂點vi到頂點vj

的路徑。125634例：V1到V3的路徑：123、123423、16423、1544……..路徑長度

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

若路徑上各頂點v1,v2,...,vm

均不互相重復(fù),則稱這樣的路徑為簡單路徑。回路

若路徑上第一個頂點v1與最后一個頂點vm

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

路徑長度：

2、5、4、3……..強連通圖與強連通分量

在有向圖中,

若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量。abcd

abcd

強連通圖非強連通圖cabd

兩個強連通分量圖的存儲表示鄰接矩陣(AdjacencyMatrix)aij=abefcdvexs123456abcdefA=010011101100010100011011100100100100利用數(shù)組vertex[]存儲頂點基本思想：利用矩陣A表示頂點之間的關(guān)系無向圖的鄰接矩陣是對稱矩陣aij=A=abcd8

19341123vexs1234A=abcd1111111000000000A=abefcdvexs123456abcdef482196

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

59371113鄰接表：在有向圖中，將以該頂點作為弧尾頂點的所有弧鏈接成單鏈表。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逆鄰接表逆鄰接表：在有向圖中，將以該頂點作為弧頭頂點的所有弧鏈接成單鏈表。？求頂點的度datafirstarcadjvexinfonextarc123456abcdef256134242356141448198742636107231910abefcd4

82196

73

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

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

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

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

<d,c>*確定結(jié)點*刪除結(jié)點*釋放結(jié)點<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é)點datafirstinfirstout頂點結(jié)點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)鄰接多重表（無向圖）markivexilinkjvexjlink邊結(jié)點datafirstedge頂點結(jié)點datafirstedge頂點結(jié)點markivexilinkjvexjlink邊結(jié)點typedefstructENode{intmark;intivex,jvex;structENode*ilink,*jlink;InfoTypeinfo;}ENode;鄰接多重表的數(shù)據(jù)類型typedefstructVNode{VertexTypedata;ENode*firstedge;}VNode;圖的遍歷(GraphTraversal)圖的遍歷從圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次。為了避免重復(fù)訪問，設(shè)置一個的輔助數(shù)組visited[]標志各頂點是否被訪問過。圖的遍歷的分類：深度優(yōu)先搜索

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

BFS(BreadthFirstSearch)DFS(v0)的主要步驟：(1)訪問頂點v0(2)確定第一鄰接點w(3)若w未訪問，則從w出發(fā)進行遍歷DFS(w)(4)確定下一個鄰接點w(5)重復(fù)(3)(4)直到所有鄰接點都處理結(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);}}

第一鄰接點:p=G->adjlist[v].firstarc下一個鄰接點：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第一鄰接點:p=G->adjlist[v].firstarc下一個鄰接點：p=p->nextarc深度優(yōu)先搜索DFS

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

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

(BreadthFirstSearch

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

問題：當對非連通圖遍歷時,從圖中某一頂點出發(fā),利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點,只能訪問到該頂點所在的最大連通子圖(連通分量)的所有頂點。ACDEBFGIHJONMLK非連通無向圖要實現(xià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非連通無向圖ACDEBFGHIJKONML非連通圖的連通分量對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。ACDEBFGIHJONMLK非連通無向圖ACDEBFGIHJONMLK非連通圖的連通分量1624351624351624351251042312104312542深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷遍歷序列:123456遍歷序列:125634連通圖生成樹不同的遍歷得到不同的生成樹權(quán)值之和:20權(quán)值之和:14最小生成樹

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

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

，最小生成樹T=(U,TE)（1）初始狀態(tài)：U={v0},TE=。（2）選擇滿足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[][]:利用鄰接矩陣法存儲圖i=j:cost[i][j]=0closest[]和lowcost[]分別存儲頂點序號和權(quán)值，當lowcost[i]=0:頂點i已經(jīng)吸收到U。當lowcost[i]0:頂點i未被吸收V-U。當0<lowcost[i]<：存儲頂點i與頂點closest[i]之間的權(quán)值。當lowcost[i]=：

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

N={V,E

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

T={V,

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

Dijkstra算法邊上權(quán)值為任意值的單源最短路徑問題—Bellman和Ford算法所有頂點之間的最短路徑—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算法思想:

首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。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未到達Si=1已到達記錄v0->vi可達的距離0102

記錄到達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拓撲排序(TopologicalSort)(AOV網(wǎng))計劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。例如，計算機專業(yè)學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學習。C1

高等數(shù)學C2程序設(shè)計基礎(chǔ)C3離散數(shù)學C1,C2

C4數(shù)據(jù)結(jié)構(gòu)C3,C2C5高級語言程序設(shè)計C2C6編譯方法C5,C4C7操作系統(tǒng)C4,C9C8普通物理C1C9計算機原理C8

課程代號課程名稱先修課程C8C3C5C4C9C6C7C1C2學生課程學習工程圖可以用有向圖表示一個工程。在這種有向圖中，用頂點表示活動，用有向邊<Vi,Vj>表示活動Vi必須先于活動Vj

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

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

重復(fù)以上

①

②,直到輸出所有頂點或沒有度為0的頂點。C1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C6C0C1C2C3C4C5拓撲排序的過程(a)有向無環(huán)圖C2C5C1C0C3(b)輸出頂點C4C4C1C2C5C3(c)輸出頂點C0C0C2C5C1C3(d)輸出頂點C3V1V2V3V4V5V6V3123456240012V1V2V3V4V5V62261262拓撲序列：V331V4V410V5V5020V1V11V6V60V2V2

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

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

②

事件Vi的最遲允許開始時間Vl[i]③

活動ak的最早可能開始時間

e[k]④

活動ak

的最遲允許開始時間

l[k]

⑤

時間余量

l[k]-e[k]

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