數(shù)據(jù)結構-圖課件

2-6圖

*圖比樹更復雜、更一般，樹是一種簡單的圖。

*圖的應用-一范圍非常廣，如語言學、邏輯學、數(shù)

學、物理、化學、計算機科學以及各種工程學科

領域。

*在圖中，結點之間的關系可以是任意的多對多的關

系。

第二章常用數(shù)據(jù)結構及其運算

2-6圖

261畫的定義及基建術語

1.圖的定義無向圖

1)圖：由頂

G=(V,R),

其中V={V1,v2,...,vn},是頂點的非空有限集合;

R={<vi,Vj>},是頂點的有序對，

或{(Vj,Vj)},是頂點的無序對。

2)無向圖：當圖中頂點間的關系為無序對。

(V],V，二(vj,vj,稱為邊Eo

無向圖記作：G二(V,E),

例如上圖：G1=(V,E),V(G1)={1,2,3,4,5)

E(G1)={(1,2),(1,3),(1,4),(2,3),(3,5)}

第二章常用數(shù)據(jù)結構及其運算

2.6圖

261囹的定義及基建術語

3)有向圖：圖中頂點間的關系為有序對

'<vi?Vj>稱為弧A,?------?

注意：<Vj,Vj>W〈Vj,V。，弧尾弧頭

有向圖記作：G二(V,A),

例如右圖：

G2=(V,A),

V(G2)={1,2,3,4,5,6)

A(G2)={<1,2>,<2,1>,<2,4>,<2,3>,<3,5>,<5,6>,<6,3>}

第二章常用數(shù)據(jù)結構及其運算

2.6圖

261囹的定義及基建術語

4）網(wǎng)：若圖中每一條邊附有反映該邊特征的數(shù)據(jù)，則

稱為網(wǎng)，與邊相關的數(shù)據(jù)稱為權。

邊上帶權的無向圖稱為無向網(wǎng)。

弧上帶權的有向圖稱為有向網(wǎng)。

有向網(wǎng)

第二章常用數(shù)據(jù)結構及其運算

2-6圖

261畫的定義及基中術語

2.圖的基本術語

1)子圖:兩個圖G和G',G=(V,E),G5=(V5,E5)

右'憶'=『和E'三E

則稱G，為G的子圖。

第二章常用數(shù)據(jù)結構及其運算

2?6圖

2.6.1畫的定義及基本術語

2）度、入度和出度：

度：無向圖中，與某個頂點相連的邊的數(shù)目“

入度：有向圖中，以某個頂點為頭的弧的數(shù)目。

出度：以某個頂點為尾的弧的數(shù)目。

有向圖

第二章常用數(shù)據(jù)結構及其運算

2?6圖

2.6.1畫的定義及基本術語

例：有N個頂點的有向圖中，每個頂點的度最大可達

多少？

2(N-1)

第二章常用數(shù)據(jù)結構及其運算

路徑：在無向圖中，從頂點Vp到Vq的路徑----

是頂點序列(Vp,Vj],V⑵…，Vjk，Vq),且(vp,Vj]),

(vn,vi2),(Vjk，Vp)均是E中的邊。

有向路徑：在有向圖中，由頂點的弧組成。

路徑長度：路徑上邊或弧的數(shù)目。

網(wǎng)的路徑長度--路徑上權值的和。

簡單路徑：除第一個和最后一個頂點外，序列中其余

頂點各不相同的路徑。

簡單回路：第一個頂點和最后一個頂點相同的簡單路徑。

第二章常用數(shù)據(jù)結構及其運算

2.6.1畫的是G

4）連通圖和連通

連通圖（a）非連通圖（b）

在無向圖G中：

連通：若從頂點Vj到Vj存在路徑，則稱Vj和Vj是連通的。

連通圖：頂點集合V中任意兩個頂點Vj和Vj都連通，.

則稱G為連通圖。

連通分量：G中的極大連通子圖稱為該圖的連通分量。

如上圖，（a）為連通圖，（b）不是連通圖，但它有3個

連通分量：G］、G2>G3

注意：連通圖只有一個連通分量，即本身。

非連通圖有多個連通分量

第二章常用數(shù)據(jù)結構及其運算

2-6圖

261畫的定文及基中術語

5）強連通圖和強連通分量：（對于有向圖定義）

在有向圖G中：

連通：從頂點Vj到Vj有路徑，則稱從Vj到Vj是連通的。

強連通圖：任意兩個頂點Vi和Vj都連通，

則稱G為強連通圖。

強連通分量：G中的極大強連通子圖稱為該圖的

強連通分量。

第二章常用數(shù)據(jù)結構及其運算

2-6圖

262圉的落儲秸構

1.鄰接矩陣(表示頂點之間的關系)

有n個頂點的圖G二(V,E),可用nXn的矩陣來表示,

矩陣元素為：

I若(Vj,Vj)或〈Vj,Vj〉是E中的邊或弧

W]={-

I0反之

若G是網(wǎng)，則鄰接矩陣中每個元素定義為：

若(Vj,Vj)或＜Vj,Vj〉是E中的邊或弧

4比月=f-、

第二章常用數(shù)據(jù)結構及其運算

例:

有向圖無向圖有向網(wǎng)

r

1110、0270019210’080006400

0100270560110000310600

10010501000003000000

0000061000140032440000

19000070000018058

V0X1V0nJ3318

21110143300750043000

lo0001800>100006900

無向圖和無向網(wǎng)的鄰接矩陣為對稱矩陣。

第二章常用數(shù)據(jù)結構及其運算

2-6圖

262圉的落儲秸構

2.鄰接表

*鄰接表是圖的一種鏈式存儲結構,在鄰接表

中，對圖中每個頂點建立一個單鏈表，并將它

們的表頭指針用向量存儲（鄰接向量）。

*第i個單鏈表中的結點依附于頂點vi的邊（有

向圖為弧），故其結點數(shù)等于vi的度（有向圖為

出度）。

第二章常用數(shù)據(jù)結構及其運算

2-6圖

2624的落儲秸構

*鏈結點結構：

表結點頭結點

adjvexdatanextarcvexdatafirarc

adjvex：鄰接域，存儲鄰接頂點

vexdata：數(shù)據(jù)域,存儲Vj

的序號；

信息;

data：數(shù)據(jù)域，存儲和邊或弧的

firarc：鏈域，指向表中

權值信息；

第一個結點。

nextarc：鏈域指示下一條邊或弧

公的結點

第二章常用數(shù)據(jù)結構及其運算

2

1

2

1A

3A

4A

1A

519621A

3546

410A

310614A

633718A

211414—?533A

f

1280—?564A

2f431―?660A

3-?230A

4->232—?344A

5f170―?6180—?

6f175―?443A

7f569A

第二章常用數(shù)據(jù)結構及其運算

2?6圖

262圉的落儲秸構

注意：'

條表頭結點有序，以向量存儲（鄰接向量）；

*無向圖的鄰接矩陣唯一，但其鄰接表不唯一

（次序與鄰接表建立時輸入次序有關）；

*對于無向圖，n個頂點，e條邊，有n個表頭

結點，2e個表結點，空間復雜度為O（n+e）；

*n個頂點的無向圖至多n（nT）/2條邊（完全

圖）。

第二章常用數(shù)據(jù)結構及其運算m

2-6圖

263囹的遍歷

從圖的某一頂點出發(fā)，沿某條路徑，依次對其

余頂點進行訪問，為了避免重復訪問，設一個

輔助數(shù)組visited[n]：

felse,初值，未訪問

visited[z]=

tureL_jUjI口J

第二章常用數(shù)據(jù)結構及其運算

2-6圖

2.6.3囹的遍歷

L深度優(yōu)先搜索(DFS)：樹的前序遍歷推廣

1)基本思想：從圖的某一個頂點V。出發(fā)進行遍歷，

首先訪問起始點V。，然后選擇V。的一個尚未訪問過

的鄰接點W,從w出發(fā)繼續(xù)深度優(yōu)先搜索，即訪問W

之后選擇W的一個尚未訪問過的鄰接點作為出發(fā)點

繼續(xù)作深度優(yōu)先搜索，直到被訪問的頂點其鄰接點

均被訪問過為止，這時需要回溯到該頂點訪問前的

頂點，繼續(xù)訪問其尚未訪問的鄰接點。這樣不斷回

溯，直到回溯到起始點V。，使所有和V。有路徑相通

的頂點都被訪問到為止。

第二章常用數(shù)據(jù)結構及其運算

2.6圖

2.6.3囹的遍歷

2)算法描述：以鄰接矩陣作為圖的存儲結構

DFS(A,n,v)

{

visit(v);〃訪問頂點v

visited[v]<-TRUE;//置已訪問標志

for(j=1;j〈二n;j++)

if(A[v][j]==l&&!visited[j])

DFS(A,n,j);

第二章常用數(shù)據(jù)結構及其運算

例:

(a)(b)

圖(a)：vl,v2,v3,v5,v4v3,vl,v2,v4,v5

v2,vl,v3,v5,v4v4,vl,v2,v3,v5

圖(b)：vl,v2,v3,v6,v5,v7,v8,v4,v9

v9,v4,vl,v2,v3,v6,v5,v7,v8

v3,vl,v2,v4,v9,v6,v5,v7,v8

第二章常用數(shù)據(jù)結構及其運算

2-6圖

2.6.3囹的遍歷

2.廣度優(yōu)先搜索（BFS）（類似于樹的層次遍歷）

1）基本思想：訪問了起始點V。之后，首先依次訪

問V。的各個鄰接點，然后再依次訪問這些頂點中未

被訪問過的鄰接點，以此類推，直到所有被訪問到

的頂點的鄰接點都被訪問過為止。

2）算法描述：為了搜索需要，應設置一個循環(huán)隊

歹U,存放已被訪問過的頂點。

第二章常用數(shù)據(jù)結構及其運算m

2-6圖

2.6.3囹的遍歷

BFS(AdjList,n,v)

(

訪問頂點v;visited[v]=TRUE;

front=n-l;rear=O;CQ[rear]=v;

while(rear!=front){

front=(front+l)%n;v=CQ[front];

p=AdjList[v].firarc;

while(p!二NULL){

if(!visited[p->adjvex]){

訪問p->adjvex;visited[p->adjvex]=TRUE;

rear-(rear+1)%n;CQ[rear]=p->adjvex;

)

p=p->nextarc;

第二章常用數(shù)據(jù)結構及其運算

2-6圖

263囹的遍歷

圖(b)：vl,v2,v3,v4,v6,v9,v5,v7,v8

v9,v4,vl,v2,v3,v6,v5,v7,v8

2-6圖

263囹的遍歷

例：

DFS：vl,v2,v3,v6,v9,v5,v8,v4,v7

BFS：vl,v2,v4,v5,v3,v7,v6,v8,v9

第二章常用數(shù)據(jù)結構及其運算

2.6圖

2.6.34的遍歷

3.復雜度分析

*空間復雜度：O(n)

*時間復雜度：

鄰接表：O(e),e為邊數(shù)

鄰接矩陣：。(標)

(0^第二章常用數(shù)據(jù)結構及其運算I<|A

2-6圖

264圉的應用

1.單源最短路徑

1）問題的提出

*背景：從一個給定的城市出發(fā)，能否到

達其它各城市？走哪條路花費最少？

*數(shù)據(jù)結構：用有向網(wǎng)表示，頂點表示城

市，弧代表路段，弧上的權值代表兩城市間的

距離或運輸所需的代價。我們稱出發(fā)點為源點,

其它點為終點。則問題可描述為：從有向網(wǎng)的

源點到其它各終點有否路徑？最短路徑是什么?

最短路徑的長度是多少？

第二章常用數(shù)據(jù)結構及其運算

2-6圖

264圉的應用

*路徑的三種情況：

①沒有路徑；

②只有一條路徑，即為最短路徑;

③有多條路經(jīng)，存在最短的。

設頂點v2為源點，貝I」：

v2到v6：沒有路徑

v2到vl：只有一條，長度35

v2到v4：有三條，最短為30

第二章常用數(shù)據(jù)結構及其運算

2-6圖

264圉的應用

條定義：

給定有向圖網(wǎng)G=(V,A)和源點vO,求從vO到G

中其余各頂點的最短路徑。

例：以v6為源點，則各最短路

5)徑為：

v6->vl:21(v6->v2->v3->vl)

v6->v2:5

v6->v3:12(v6->v2->v3)

v6->v4:25(v6->v4)

v6->v5:無路徑

第二章常用數(shù)據(jù)結構及其運算

123456

06OO8cDOO

1807OOOO10

9OO0158OO

264圉的OO8120OOOO

OOOO480OO

2）算法月6245OO25OO0

路徑〈V0,Vk＞,從這些路徑中找出一條長度最短

的路徑〈v0,u＞,然后對其余各條路徑進行適當

調整：若在圖中存在?。║,Vk〉,且〈U,Vk〉和

＜V0,U＞兩條弧上權之和小于弧〈V。,Vk＞的權，則

以路徑（V0,U,Vk＞代替〈V0,Vk＞。在調整后的各

條路徑中，再找長度最短的路徑，以此類推。

3）過程：

二①初始化

設AS[n][n]為有向網(wǎng)的帶權鄰接矩陣，

AS[i][j]表示弧〈Vj,Vj＞上的權值，若〈Vj,V》

不存在,則為8

第二章常用數(shù)據(jù)結構及其運算

2-6圖

264圉的應用

S:最短路徑的終點集合（初值為{v。}）

DIST[n]:各終點當前找到的最短路徑的長度

（初始值為DIST[i]=AS[vo][i]）

②選擇u,使得：

DIST[u]=mm{DIST[w]|w史工w￡/}

S=SU{〃}

其中憶為有向圖的頂點集。

第二章常用數(shù)據(jù)結構及其運算

2?6圖

264畫的應用

③對于所有不在S中的終點w,若:

DIST[u]+AS[u^]<DIST[w],則

DIST[w]=DIST[u]+AS[u][w]

④重復操作②、③共n-1次，可求得從V。到各終點的

最短路徑。

*幾個量的說明：

S[n]：記錄了從源點出發(fā)的最短路徑的終點集合。

DIST[n]：記錄各終點當前找到的最短路徑的長度。

PATHM：PATH[i]表示從源點到頂點vi之間的最短路徑

N的前驅頂點，初始值為源點vO,若不存在，則為空。—

少第二章常用數(shù)據(jù)結構及其運算<

264圉的

例：

DIST[1:6]PATH[1:6]

S123456123456

{6}245OO25OO0_6666

{6,2}2351225OO026266

{6,2,3}2151225OO0_3626|6

{623,1}2151225OO036266

{6,2,334}2151225OO036266

則輸出PATH和Distant：6->l:6->2->3->l21;6->2:6->25;

6->3:6->2->312;6->4:6->425;

石、6->5:無路徑；6->6:6->60;

第二章常用數(shù)據(jù)結構及其運算

2-6圖

264圉的應用

2.拓撲排序（AOV網(wǎng)，頂點表示活動的有向網(wǎng)）

1）問題的描述：

*用有向圖描述工程的進行過程，子工程稱為活動，

在圖中用頂點表示，兩頂點間的弧表示活動間的優(yōu)先

關系，這種有向圖稱為作業(yè)活動網(wǎng)或AOV網(wǎng)。

頂點i到頂點j有路徑，稱i是j的前驅，j是i的后繼；

若從i到j只有一條弧，則稱i是j的直接前驅，j是i的

直接后繼。

第二章常用數(shù)據(jù)結構及其運算

2-6圖

264圉的應用

引例：一個軟件專業(yè)學生學習課程

C1：程序設計先修無

C2：離散數(shù)學C1

C3：數(shù)據(jù)結構ClC2

C4：匯編語言C1

C5：語言設計與分析C3C4

第二章常用數(shù)據(jù)結構及其運算

2-6圖

264圉的應用

*拓撲有序序列及拓撲排序

死鎖-一在AOV網(wǎng)中不允許存在有向回路，否則

某項活動的開工將以自己工作的完成作為先決條

件，這種現(xiàn)象稱為死鎖。

拓撲有序序列--若有向圖中沒有回路出現(xiàn)，則

可構造得到包含有向圖中全部頂點的序列，這種

序列稱為拓撲有序序列。

拓撲排序-一對AOV網(wǎng)構造拓撲有序序列的操作

稱為拓撲排序。

第二章常用數(shù)據(jù)結構及其運算

2）拓撲排序方法：

①在有向圖中選取一個沒有前驅的頂點（入度為0）

輸出；

②在圖中刪除該頂點和以它為尾的所有弧。

③Repeat①，②，直到全部頂點輸出。（答案不唯一）

（0^第二章常用數(shù)據(jù)結構及其運算

2.6圖

264圉的應用

可能的拓撲：可能的拓撲:

6->1->4->3->2->51->2->3->4->5

1->3->2->6->4->51->4->2->3->5

1->2->4->3->5

第二章常用數(shù)據(jù)結構及其運算

2-6圖

264圉的應用

3）拓撲排序的鄰接表和鏈棧:

頂入指

鄰接表,點度針

10

22A

31

AOV網(wǎng)42

53A

60

鏈棧：所有入度為零的頂點構成一鏈棧

第二章常用數(shù)據(jù)結構及其運算

2-6圖

264圉的應用

操作：①建立一個入度為0的頂點的棧；

②選取一個入度為0的頂點輸出；

③弧頭頂點的入度減1；

④Repeat①?③，直到全部頂點輸出

第二章常用數(shù)據(jù)結構及其運算

2、0、1、3、4、50,2,1,3,4,5

第二章常用數(shù)據(jù)結構及其運算

2?6圖

264圉的應用

3.關鍵路徑（以邊表示活動的網(wǎng)：AOE）

1）問題描述

*AOE網(wǎng)：一個帶權的有向無環(huán)圖。

頂點V/表示事件

Mai：表示活動

權：表示活動的持續(xù)時間。

源點：一個入度為零的點（工程起點，只有一個）

匯點：一個出度為零的點（工程結束，只有一個）

*研究的問題

①完成整個工程需要多少時間？

、②哪些活動是影響工程進度的關鍵？

第二章常用數(shù)據(jù)結構及其運算m

2-6圖

264圉的應用

*關鍵路徑：完成工程的最短時間是從源點到匯點的最長

路徑長度，這條最長的路徑稱作關鍵路徑。

施事件vj最早發(fā)生時間ve(j)：從ve(l)二0開始向前遞推

ve(7)=Max{ve(z)+dut(<i〉j>)}

<i,j>eT,2<j<n

活動aj由弧〈i,j>表示，其持續(xù)時間記為

dut?i,j?,T是所有以j為頭的弧的集合ai

第二章常用數(shù)據(jù)結構及其運算

2-6圖

264圉的應用

*事件vj最遲發(fā)生時間vl(j)：從vl(n)=ve(n)

開始向后遞推

vl(7)=Min{vl(左)一dut(<j,k>)}

<j,k>GS,1<j<n—1▲

其中s是所有以j為尾的弧的集合［T二/，

注意：以上兩個遞推公式的計算必須在拓撲有序和逆

拓撲有序的前提下進行，即：ve(j)必須在Vj的所有前

驅的最早發(fā)生時間求得之后才能確定，而vl(j)必須在

:'Vj的所有后繼的最遲發(fā)生時間之后才能確定。

y第二章常用數(shù)據(jù)結構及其運算

2-6圖

264圉的應用

*活動最早開始時間e(i)：

e⑴二ve(j)

*活動最遲開始時間l(i)：活動ai最遲必須開

始進行的時間。

1(i)=vl(k)-dut(<j,k?―?

*關鍵活動：如果l(i)-e(i)=0,則稱乙為關鍵活

動。關鍵路徑上的活動都是關鍵活動。

第二章常用數(shù)據(jù)結構及其運算

2-6圖

264圉的應用

2)求解關鍵路徑過程：

①輸入e條弧，建立AOE網(wǎng)；

②從源點V1出發(fā)，令ve(l)=0,按拓撲有序求其余各

頂點的ve(j),若得到的拓撲有序序列中的頂點個數(shù)

小于網(wǎng)中頂點個數(shù)，說明存在環(huán)，不能求關鍵路徑；

③從匯點％出發(fā)，令vl(n)=ve(n),按逆拓撲有序求

其余各頂點的vl(j)；

④ve和vl值，求每條弧(每個活動)的e(i)和l(i),

找出滿足e(i)二1⑴的關鍵活動，從而求得關鍵路徑。

第二章常用數(shù)據(jù)結構及其運算

2-6圖

264圉的應用

'3)復雜度分析：

計算ve和vl的時間復雜度：0(n+e)

計算e和1的時間復雜度：0(e)

求關鍵路徑的總的時間復雜度：0(n+e)

第二章常用數(shù)據(jù)結構及其運算

例：AOE網(wǎng)采用鄰接矩陣存儲，其三元組表示為：

(1,2,3),(1,3,2),(2,4,2),(2,5,3),(3,4,4),(3,6,3),

(4,6,2),(5,6,1),求ve、vLe⑴、班)和關鍵路徑。

解：根據(jù)三元組表示，該AOE網(wǎng)為：

第二章常用數(shù)據(jù)結構及其運算

頂點vevl活動e11-e

vl00al011

v234a2000

v322a3341

v466a4341

匯點v567a5220

v688a6253

a7660

a8671

得關鍵路徑：vl