ACM培訓資料數據結構與算法課件

數據結構

(DATASTRUCTURE)計算機科學與工程系

10第七章圖圖的基本概念圖的存儲表示圖的遍歷與連通性最小生成樹最短路徑活動網絡207.1

圖的基本概念圖的定義

圖是由頂點集合(vertex)及頂點間的關系集合組成的一種數據結構：

Graph＝(V,E)

其中

V={x|x

某個數據對象}

是頂點的有窮非空集合；

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

V}

或

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

V&&Path(x,y)}

是頂點之間關系的有窮集合，也叫做邊(edge)集合。Path(x,y)表示從x到y(tǒng)的一條通路。30

鄰接頂點

如果(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點。子圖

設有兩個圖G＝(V,E)和G’＝(V’,E’),若V’V且E’

E,則稱圖G’是圖G的子圖。50頂點的度

一個頂點v的度是與它相關聯的邊的條數，記作TD(v)。頂點v的入度

是以v為終點(弧頭)的有向邊的條數,記作ID(v);頂點v

的出度是以v為始點(弧尾)的有向邊的條數,記作OD(v)。路徑

在圖G＝(V,E)中,若從頂點

vi出發(fā),沿一些邊經過一些頂點

vp1,vp2,…,vpm，到達頂點vj。則稱頂點序列(vi

vp1vp2...vpm

vj)

為從頂點vi到頂點vj的路徑。它經過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應是屬于E的邊。60路徑長度非帶權圖的路徑長度是指此路徑上邊的條數。帶權圖的路徑長度是指路徑上各邊的權之和。簡單路徑

若路徑上各頂點v1,v2,...,vm均不互相重復,則稱這樣的路徑為簡單路徑?；芈?/p>

若路徑上第一個頂點v1與最后一個頂點vm重合,則稱這樣的路徑為回路或環(huán)。簡單回路

除了第一個頂點和最后一個頂點外，其余頂點不重復出現的回路叫簡單回路

707.2

圖的存儲結構1）存儲特點在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的頂點表；還有一個表示各個頂點之間關系的鄰接矩陣。2）鄰接矩陣設圖A=(V,E)是一個有n個頂點的圖，則圖的鄰接矩陣是一個二維數組A[n][n]，定義：7.2.1

鄰接矩陣(AdjacencyMatrix)表示法90100

網絡的鄰接矩陣1104）圖的創(chuàng)建

思路：1307.2.2

鄰接表(AdjacencyList)1)存儲特點對于圖G中的每個頂點vi，把所有鄰接于vi的頂點vj鏈成一個單鏈表，這個單鏈表稱為頂點vi的鄰接表；將所有點的鄰接表表頭放到數組中，就構成了圖的鄰接表

140特點無向圖中頂點Vi的度為第i個單鏈表中的結點數有向圖中頂點Vi的出度為第i個單鏈表中的結點個數頂點Vi的入度為整個單鏈表中鄰接點域值是i的結點個數逆鄰接表：有向圖中對每個結點建立以Vi為頭的弧的單鏈表例G1bdac1234acdbvexdatafirstarc

4

1^

1^^

3^adjvexnext1502）數據類型描述＃defineMaxVerNum100/*最大頂點數為100*/鄰接表類型：

typedefstructArcNode{intadjvex;/*鄰接點域*/InfoType*Info;/*表示邊上信息的域info*/structArcNode*next;/*指向下一個鄰接點的指針域*/}ArcNode;表頭結點類型：

typedefstructVnode{VertexTypevertex;/*頂點域*/ArcNode*firstedge;/*邊表頭指針*/}Vnode,AdjList[MaxVertexNum];圖的類型：

typedefstruct{AdjListvertices;/*鄰接表*/intvexnum,arcnum;/*頂點數和邊數*/}ALGraph;/*ALGraph是以鄰接表方式存儲的圖類型*/1707.2.3

十字鏈表(OrthogonalList)

十字鏈表是有向圖的另一種鏈式存儲結構，它實際上是鄰接表與逆鄰接表的結合1)存儲特點圖中每一條弧有一個結點，把弧頭相同的弧連在同一鏈表上,弧尾相同的弧也連在同一鏈表上。結點結構為：頂點結點為鏈表頭結點，其結構為：1807.2.4

鄰接多重表(AdjacencyMultilist)鄰接多重表是無向圖的另一種鏈式存儲結構1)存儲特點圖中每一條邊用一個邊結點表示，其結構為：每個頂點用一個結點表示，其結構為：markivexilinkjvexjlinkdatafirstedge1907.3

圖的遍歷與連通性從圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，叫做圖的遍歷

(GraphTraversal)。為了避免重復訪問，可設置一個標志頂點是否被訪問過的輔助數組visited[]，它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個頂點i

被訪問，就立即讓visited[i]

為1，防止它被多次訪問。2107.3.1

深度優(yōu)先搜索DFS1）基本思想：任選圖中一個頂點v,訪問此頂點,并作訪問標記。從v出發(fā)，訪問它的任一未被訪問過的鄰接頂點w

，作訪問標記，并以w為新的出發(fā)點，繼續(xù)進行深度優(yōu)先搜索。當某個頂點的所有鄰接頂點都被訪問過后，則退回到前一次剛訪問過的頂點k，從k的另一個沒有被訪問的鄰接頂點出發(fā)進行深度優(yōu)先搜索。重復上述過程,直到圖中所有頂點都被訪問過為止220深度優(yōu)先搜索的示例例V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V3V6V7V52302）算法實現難點：如何標記已訪問結點v?如何查找v的所有鄰接點？解決辦法：設置一個布爾向量數組visited[n]，初值為0。若序號為i的結點已被訪問過，則visited[i]=1。根據圖的存儲方式不同，采取相應方法查找：鄰接矩陣：vi

的鄰接點是鄰接矩陣中第i行上非0元素對應的列值，若A[i][j]<>0，則vj為vi鄰接點。鄰接表：是以G.vertices[i]為表頭結點的單鏈表上的所有結點。250V1V2V4V5V3V7V6V8例1234V1V3V4V2vexdatafirstarc

2

7

8

3^^^adjvexnext5V5

6^

4

8

2^V6V7V8678

7^^^深度遍歷：V1V3V7V6V2V4V8V5260廣度優(yōu)先搜索的示例例V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V6V7V8V5290廣度優(yōu)先搜索的示例遍歷結果：A、B、C、D例300為了實現逐層訪問，算法中使用了一個隊列，以記憶正在訪問的這一層和上一層的頂點，以便于向下一層訪問。2）算法實現開始標志數組初始化Vi=1Vi訪問過BFSVi=Vi+1Vi==Vexnums結束NNYY310

BFS開始訪問Vi,置標志求V鄰接點WW存在嗎V下一鄰接點WW訪問過結束NYNY初始化隊列Vi入隊隊列空嗎隊頭V出隊訪問W,置標志W入隊NY320如果使用鄰接表表示圖，則循環(huán)的總時間代價為d1+d2+…+dn=O(e)，其中的di是頂點i的度。如果使用鄰接矩陣，則對于每一個被訪問過的頂點，循環(huán)要檢測矩陣中的n個元素，總的時間代價為O(n2)。3）算法分析3307.4

圖的連通性與生成樹7.4.1

圖的連通性問題連通圖與連通分量

在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。強連通圖與強連通分量

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

最小生成樹

1）圖的生成樹連通圖G的一個子圖如果是一棵包含G的所有頂點的樹（所有頂點均由邊連接在一起，但不存在回路,有n-1條邊），則該子圖稱為G的生成樹。生成樹是連通圖的極小連通子圖。所謂極小是指：若在樹中任意增加一條邊，則將出現一個回路；若去掉一條邊，將會使之變成非連通圖。使用不同的遍歷圖的方法，可以得到不同的生成樹360說明一個圖可以有許多棵不同的生成樹所有生成樹具有以下共同特點：生成樹的頂點個數與圖的頂點個數相同生成樹是圖的極小連通子圖一個有n個頂點的連通圖的生成樹有n-1條邊生成樹中任意兩個頂點間的路徑是唯一的在生成樹中再加一條邊必然形成回路含n個頂點n-1條邊的圖不一定是生成樹GHKI370V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8380例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林390

問題提出——要在n個城市間建立通信聯絡網，

頂點——

城市

權——

城市間建立通信線路所需花費代價

生成樹各邊的權值總和稱為生成樹的權。權最小的生成樹稱為最小生成樹。2)構造最小生成樹

問題分析n個城市間,最多可設置n(n-1)/2條線路n個城市間建立通信網,只需n-1條線路問題轉化為：如何在可能的線路中選擇n-1條，能把所有城市（頂點）均連起來，且總耗費各邊權值之和）最小1654327131791812752410400最小生成樹的重要性質：

設G=（V，E）是一個連通網絡，U是頂點集V的一個真子集。若（u，v）是G中所有的一個頂點在U,另一個頂點不在U的邊中，具有最小權值的一條邊，則一定存在G的一棵最小生成樹包括此邊。uvUV—U410①普里姆(Prim)算法普里姆算法的基本思想：假設圖G={V,E}，所求最小生成樹T=(U,TE),其中U=V,TEE

從連通網絡G={V,E}中的某一頂點u0

出發(fā)，選擇與它關聯的具有最小權值的邊(u0,v)，將其頂點加入到生成樹的頂點集合U中。以后每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權值最小的邊(u,v),把它的頂點加入到集合U中。如此繼續(xù)下去，直到網絡中的所有頂點都加入到生成樹頂點集合U中為止。420

算法實現:(略)

算法分析：

上述算法的初始化時間是O(1)，k循環(huán)中有兩個循環(huán)語句，其時間大致為：

令O(1)為某一正常數C，展開上述求和公式可知其數量級仍是n的平方。所以，整個算法的時間復雜性是O(n2)430②克魯斯卡爾(Kruskal)

算法克魯斯卡爾算法的基本思想：設有一個有n個頂點的連通網絡G={V,E}，最初先構造一個只有n個頂點，沒有邊的非連通圖T={V,},圖中每個頂點自成一個連通分量。在E中選取一條具有最小權值的邊(u,v)，若該邊的兩個頂點落在兩個不同的連通分量上，則將此邊加入到T中；否則將此邊舍去，重新選擇一條權值最小的邊。如此上步，直到T中所有頂點在同一個連通分量上為止。440應用克魯斯卡爾算法構造最小生成樹的過程例1654326513566425165432123454507.5

有向無環(huán)圖及其應用計劃、施工過程、生產流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。例如，計算機專業(yè)學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。7.5.1

活動網絡(ActivityNetwork)

用頂點表示活動的網絡(AOV網絡)460

C1

高等數學C2程序設計基礎C3離散數學C1,C2

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

課程代號課程名稱先修課程470學生課程學習工程圖480可以用有向圖表示一個工程。在這種有向圖中，用頂點表示活動，用有向邊<Vi,Vj>表示活動間的優(yōu)先關系，Vi必須先于活動Vj

進行。這種有向圖叫做頂點表示活動的AOV網絡(ActivityOnVertices)。在AOV網絡中，如果活動Vi必須在活動Vj之前進行，則存在有向邊<Vi,Vj>，AOV網絡中不能出現有向回路，即有向環(huán)。在AOV網絡中如果出現了有向環(huán)，則意味著某項活動應以自己作為先決條件。因此，對給定的AOV網絡，必須先判斷它是否存在有向環(huán)。490檢測有向環(huán)的一種方法是對AOV網絡構造它的拓撲有序序列。即將各個頂點(代表各個活動)排列成一個線性有序的序列，使得AOV網絡中所有應存在的前驅和后繼關系都能得到滿足。拓撲排序：從某個集合上的一個偏序得到該集合上的一個全序，這個操作稱為拓撲排序。1）拓撲排序500例如，對學生選課工程圖進行拓撲排序，得到的拓撲有序序列為

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

或C1,C8,C9,C2,C5,C3,C4,C7,C65102）進行拓撲排序的方法

輸入AOV網絡，令n為頂點個數在AOV網絡中選一個沒有直接前驅的頂點（即此頂點入度為0）,并輸出之；從圖中刪去該頂點,同時刪去所有它發(fā)出的有向邊;重復以上兩步,直到全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅，再也找不到沒有前驅的頂點了。這時AOV網絡中必定存在有向環(huán)。520C0C1C2C3C4C5例：拓撲排序的過程(a)有向無環(huán)圖(b)輸出頂點C4(c)輸出頂點C0C2C5C1C0C3C4C1C2C5C3C0C2C5C1C3(d)輸出頂點C3530C1C2C5(e)輸出頂點C2C5C1(f)輸出頂點C1C5(g)輸出頂點C5(h)拓撲排序完成540AOV網絡及其鄰接表表示C0C1C2C3C4C5

destnext

C0C1C2C30C4C50012345countdataadj

130103

1

30

5

1

50

0

1

50在鄰接表中增設了一個count域，記錄各個頂點入度。入度為零的頂點即無前驅的頂點。5503）拓撲排序算法入度為0的頂點即為沒有前驅的頂點。刪除頂點及相應弧的操作可轉換為弧頭頂點入度減1。為避免重復檢查入度為0的頂點，在算法中使用一個鏈式棧將入度為0的頂點鏈接在一起，供選擇和輸出無前驅的頂點。只要出現入度為零的頂點，就將它加入棧中。560算法描述使用這種棧的拓撲排序算法可以描述如下：

(1)建立入度為零的頂點棧;輸出頂點計數器=0(2)當入度為零的頂點棧不空時,重復執(zhí)行從棧中取出頂點元素,并輸出之;計數器+1從AOV網絡中刪去這個頂點和它發(fā)出的邊,邊的終頂點入度減1;如果邊的終頂點入度減至0,則該頂點進入度為零的頂點棧;(3)如果輸出頂點個數少于AOV網絡的頂點個數,則報告網絡中存在有向環(huán)。570分析此拓撲排序算法可知，如果AOV網絡有n個頂點，e條邊，在拓撲排序的過程中，搜索入度為零的頂點，建立鏈式棧所需要的時間是O(n)。在正常的情況下，有向圖有n個頂點，每個頂點進一次棧，出一次棧，共輸出n次。頂點入度減一的運算共執(zhí)行了e次。所以總的時間復雜度為O(n+e)。4）算法分析5807.5.2

用邊表示活動的網絡(AOE網絡)如果在無環(huán)的帶權有向圖中

用有向邊表示一個工程中的活動(Activity)

用邊上權值表示活動持續(xù)時間(Duration)

用頂點表示事件

(Event)

則這樣的有向圖叫做用邊表示活動的網絡，簡稱AOE(ActivityOnEdges)網絡。AOE網絡在某些工程估算方面非常有用。例如，可以使人們了解：

(1)完成整個工程至少需要多少時間(假設沒有環(huán))?(2)為縮短完成工程所需的時間,應當加快哪些活動?590在AOE網絡中,有些活動順序進行，有些活動并行進行。從源點到各個頂點，以至從源點到匯點的有向路徑可能不止一條。這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，整個工程才算完成。因此，完成整個工程所需的時間取決于從源點到匯點的最長路徑長度，即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關鍵路徑(CriticalPath)。1）關鍵路徑6001324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=10要找出關鍵路徑，必須找出關鍵活動，即不按期完成就會影響整個工程完成的活動。關鍵路徑上的所有活動都是關鍵活動。因此，只要找到了關鍵活動，就可以找到關鍵路徑.

例如，下圖就是一個AOE網。6102）如何求關鍵路徑定義幾個與計算關鍵活動有關的量：事件Vi

的最早發(fā)生時間Ve(i)是從源點V0

到頂點Vi的最長路徑長度。事件Vi的最遲發(fā)生時間Vl[i]是在保證匯點Vn

在Ve[n]時刻完成的前提下，事件Vi

的允許的最遲開始時間?；顒觓k的最早開始時間e[k]：設活動ak在邊<Vi,Vj>上，則e[k]是從源點V0到頂點Vi

的最長路徑長度。因此,e[k]=Ve[i]。活動ak的最遲開始時間l[k]是在不會引起時間延誤的前提下,該活動允許的最遲開始時間。

l[k]=Vl[j]-dur(<i,j>)其中,dur(<i,j>)是完成ak所需的時間。620時間余量l[k]-e[k]表示活動ak的最早開始時間和最遲開始時間的時間余量。l[k]==e[k]表示活動ak是沒有時間余量的關鍵活動。為找出關鍵活動,需要求各個活動的e[k]與l[k]，以判別是否l[k]==e[k].為求得e[k]與l[k]，需要先求得從源點V0到各個頂點Vi的Ve[i]和Vl[i]。630求Ve[i]的遞推公式從Ve[1]=0開始，向前遞推

<Vi,Vj>S2,j=2,,n

其中S2是所有指向頂點Vi的有向邊<Vj

,Vi

>的集合從Vl[n]=Ve[n]開始，反向遞推

<Vi,Vj>S1,j=n-1,n-2,,1

其中S1是所有從頂點Vi

發(fā)出的有向邊<Vi

,Vj

>的集合這兩個遞推公式的計算必須分別在拓撲有序及逆拓撲有序的前提下進行。640

算法分析

在拓撲排序求Ve[i]和逆拓撲有序求Vl[i]時,所需時間為O(n+e),求各個活動的e[k]和l[k]時所需時間為O(e),總共花費時間仍然是O(n+e)。6507.6

最短路徑(ShortestPath)問題提出:

用帶權的有向圖表示一個交通運輸網，圖中：頂點——表示城市邊——表示城市間的交通聯系權——表示沿此線路運輸所花的時間或費用等

問題：從某頂點出發(fā)，沿圖到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑——最短路徑最短路徑：如果從圖中某一頂點(稱為源點)到達另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑，使得沿此路徑各邊上的權值總和達到最小。問題解法單源最短路徑—Dijkstra算法任意頂點對之間的最短路徑—Floyd算法6607.6.1

單源最短路徑問題問題的提法：

給定一個帶權有向圖D與源點v，求從v到D中其它頂點的最短路徑。限定各邊上的權值大于或等于0。為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產生最短路徑的算法。6701)迪杰斯特拉(Dijkstra)算法基本思想

按路徑長度遞增次序產生最短路徑:把V分成兩組：

(1)S：已求出最短路徑的頂點的集合(2)V-