第七章 圖教學(xué)課件

8

2?匚

統(tǒng)

〒

料

小

苗得

制率

S東

料掘里

L

-0

〒Z

。匚

統(tǒng)“

?在線性表中，一個(gè)元素只能和其直接前驅(qū)或

接后繼相關(guān)；

?在樹中，一個(gè)結(jié)點(diǎn)可以和其下一層的多個(gè)孩子

結(jié)點(diǎn)相關(guān)，以及上一層的雙親結(jié)點(diǎn)相關(guān)，但不

能和其他的任何結(jié)點(diǎn)直接相關(guān)；

?圖(Graph)是一種較線性結(jié)枸和樹更為復(fù)雜的

數(shù)據(jù)結(jié)構(gòu)。而對亍圖來說,中任意兩個(gè)結(jié)點(diǎn)

之間都可以直接相關(guān)，因此圖形結(jié)枸非常復(fù)雜

的結(jié)構(gòu)定義:

圖是由一個(gè)頂點(diǎn)集V和一個(gè)弧集E構(gòu)

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

Graph=(V,E)

頂點(diǎn)：圖中電數(shù)據(jù)元素。設(shè)它的集合用

V(Vertex)表示。

的結(jié)構(gòu)定義:

?弧：設(shè)兩個(gè)頂點(diǎn)之間的關(guān)系的集合用E(edge)

來表示，且“，V2EV,若<vl,v2>GE,如

<vl,v2)表示從vl到v2的一條弧(Arc)。

且稱vl為弧尾(Tail)(蛤點(diǎn)、尾頂點(diǎn))，v2為

孤矣(Head)(終點(diǎn)、買頂點(diǎn))，此時(shí)W圖稱

為有向圖(Digraph)。

?無向：若<vl,v2>EE必能推導(dǎo)的<v2,vl>

GE,即E是對稱的，死/用無序?qū)V1,V2J代

替有序?qū)?表示vl和v2<間的一條①(Edge)。

此時(shí)的圖稱為元向圖(Undigraph)。

名旎1和*^誦^--當(dāng)■向E

%

由亍“弧”是有方向的，因此稱由頂點(diǎn)集和弧VA

集枸成的圖為有向圖。

例如：

Gj=(V19E)

其中,

V1={A,B,C,D,E}

V[E={vA,B>,<A,E>|

vB,C>,vC,D>,<D,B

vD,A>,<E,C>}

名詞和術(shù)語--無向

由頂點(diǎn)集和2集構(gòu)成的稱作元向

例如:G2=(V2,E)

v2={A,B,C,D,E,F}

V2E={(A,B),(A,E),

(B,E),(C,D),(D,F),

(B,F),(C,F)}

假設(shè)圖中有n個(gè)頂點(diǎn)，e條邊，貝陸

含有e=n(n-l)/2條邊的無向圖稱》

完全圖；

含有e=n(n-l)條弧的有向圖稱作

有向完全圖；

弧或邊帶權(quán)的解

分別稱作有向網(wǎng)或

無向網(wǎng)。

設(shè)圖G=(Y{VE})和@

圖G=(V\{VE[),

且V'uYVE'uVE,

班核57為G的子圖。

對無向圖來說，若頂點(diǎn)v和頂點(diǎn)w之

在一條邊，則稱頂點(diǎn)V和W互為鄰接

邊(v,w)和頂點(diǎn)V和W相關(guān)聯(lián)。.

和頂點(diǎn)V關(guān)聯(lián)的邊的數(shù)目定義為邊的度。/

例如：右側(cè)圖中

ID(B)=3

ID￡A)=2

對有向圖來說,由于弧有方向性，則

有入度和出度之分

頂點(diǎn)的出度：以頂點(diǎn)

V為弧尾的弧的數(shù)目:

頂點(diǎn)的入度：以頂點(diǎn)

例如：

v為弧頭的弧的數(shù)目。

OD(B)=1

ID(B)=2頂點(diǎn)的度(TD)=、

D(B)=3出度(OD)+入度(ID)

設(shè)圖G=（y{VE}）中的一個(gè)頂點(diǎn)序列

{U=Vi,O，Vi,l，…,”,m=w}中，（Vi,j"Vi,j）eVlEq

則稱從頂點(diǎn)U到頂點(diǎn)W之間存在一條路徑。

路徑上邊的數(shù)目稱作路徑長度。

及口：從A到F長度為3

簡單路徑:指序列中頂（

的路徑{A,B，C,F}點(diǎn)不重復(fù)出現(xiàn)的路徑。\

簡單回路:指序歹U中

第一個(gè)頂點(diǎn)和最后一

個(gè)頂點(diǎn)相同的路徑。

若圖G中任意兩個(gè)頂

點(diǎn)之間都有路徑相通,

則稱此圖為連通圖；

若無向圖為非連通圖

則圖中各個(gè)極大連通

子圖稱作此圖的連通

分量。

對有向圖，若任意兩個(gè)頂點(diǎn)之間都》

一條有向路徑，則稱此有向圖為強(qiáng)連通

否則，其各個(gè)強(qiáng)連通子圖稱作它的

強(qiáng)連通分量。

假設(shè)一個(gè)連通圖有n個(gè)頂點(diǎn)和e條g

其中n?l條邊和n個(gè)頂點(diǎn)構(gòu)成一個(gè)極、

連通子圖，稱該極小連通子圖為此連通

的生成樹。

7.2圖的存儲表示V

一、圖的數(shù)組（鄰接矩陣）存儲表示

二、圖的鄰接表存儲表示

三、有向圖的十字鏈表存儲表示

，無向圖的鄰接多重表存儲表示

一、圖的數(shù)組(鄰接矩陣)存儲聲

定義:矩陣的元素為

_r0(i,j)^VE

A1(1(i,j)eVE

010010

100010

000101

001001

110000

011100

有向圖的鄰接矩陣

為非對稱矩陣

typedefintVertexType;〃是頂點(diǎn)關(guān)系類

VertexTypeVerList[MaxVertexNum];

intAdjMatrix[MaxVertexNum]

[MaxVertexNum];

〃對無權(quán)圖，用1或0表示相鄰否；

〃對帶權(quán)圖，則為權(quán)值類型。

二、圖的鄰接表

存儲表示

4/\

45

56

5F

1八

27人

有向圖的鄰接表

0

1

可見，在有向圖的2

鄰接表中不易找到3

頂點(diǎn)的弧4

有向圖的逆鄰接表

在有向圖的鄰接表

中，對每個(gè)頂點(diǎn)，

0

鏈接的是指向該頂

1

點(diǎn)的弧

2

3

4

弧的結(jié)點(diǎn)結(jié)構(gòu)adjvexnextarcinfo

typedefstructArcNode{

intadjvex;//該弧所指向的頂點(diǎn)的位

structArcNode^nextarc;

〃指向下一條弧的指針

InfbType*info;//該弧相關(guān)信息的指針

頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)datafirstarc

typedefstructVNode{

VertexTypedata;〃頂點(diǎn)信息

ArcNode^firstarc;

〃指向第一條依附該頂點(diǎn)的弧J

}VNode,AdjList[MAX_VERTEX_NUM];\

圖的結(jié)構(gòu)定義（鄰接表）

typedefstruct{

AdjListvertices;

intvexnum,arcnum;

intkind;//圖的種類標(biāo)志（

Graph;

三、有向圖的十字鏈表存儲表7

0

1

02AA

弧的結(jié)點(diǎn)結(jié)構(gòu)

tailvexheadvexhlinktlinkinfo

弧尾頂點(diǎn)位置弧頭頂點(diǎn)位置弧的相關(guān)信息

指向下一個(gè)指向下一個(gè)

有相同弧頭有相同弧尾

的結(jié)點(diǎn)的結(jié)點(diǎn)

typedefstructArcBox{//弧的結(jié)構(gòu)表示

inttailvex,headvex;InfbType*infb;

才永面說ArcBoxhlink,*tlink;

VexNode;

頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)

datafirstinfirstout

頂點(diǎn)信息數(shù)據(jù)

指向該頂點(diǎn)的指向該頂點(diǎn)的

第一條入弧第一條出弧

typedefstructVexNode{〃頂點(diǎn)的結(jié)構(gòu)表示

VertexTypedata;(

ArcBox^firstin,^firstout;,

ode;

有向圖的結(jié)構(gòu)表示（十字鏈表）Z

typedefstruct{Q

VexNodexlist[MAX_VERTEX_NUM]i

〃頂點(diǎn)結(jié)點(diǎn)（表頭向量）,

intvexnum,arcnum;

〃有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)

Eaph;

7.3圖的遍歷

從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪w

圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)J

僅被訪問一次的過程。

深度優(yōu)先搜索

令廣度優(yōu)先搜索

令遍歷應(yīng)用舉例

一、深度優(yōu)先搜索遍歷圖

連通圖的深度優(yōu)先搜索遍歷

從圖中某個(gè)頂點(diǎn)V。出發(fā)，訪問此頂\

點(diǎn)，然后依次從V。的各個(gè)未被訪問的鄰（

接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中，

所西和V。有路徑相通的頂點(diǎn)都被訪問到。）

W「W2和W3均淘

鄰接點(diǎn)，SGi、SG、

SG3分別為含頂點(diǎn)W

W2和W3的子圖。

訪問頂點(diǎn)V;

for(Wj>W2、W3)

若該鄰接點(diǎn)W未被訪問，

則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。

從上頁的圖解可見：q

1.從深度優(yōu)先搜索遍歷連通圖的過q

程類似于樹的先根遍歷；,

2.如何判別V的鄰接點(diǎn)是否被訪問？\

解決的辦法是:為每個(gè)頂點(diǎn)設(shè)立一個(gè)，

劣問標(biāo)志visited[w]^^;\

voidDFS(GraphG,intv){、

〃從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖

visited[v]=TRUE;VisitFunc(v);

for(w=FirstAdjVex(G,v);

w!=0;w=NextAdjVex(G,v,w))

if(!visited[w])DFS(G,w);

//對v的尚未訪問的鄰接頂點(diǎn)w

4一〃遞歸調(diào)用DFS

FS

,非連通圖的深度優(yōu)先搜索遍歷個(gè)

首先將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)

為FALSE,之后搜索圖中每個(gè)頂點(diǎn)，如

果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)

行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下

voidDFSTraverse(GraphG,

Status(*Visit)(intv)){

〃對圖G作深度優(yōu)先遍歷。

VisitFunc=Visit;

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

visited[v]=FALSE;〃訪問標(biāo)志數(shù)組初始化

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

if(!visited[v])DFS(G,v);

〃對尚未訪問的頂點(diǎn)調(diào)用DFS

二、廣度優(yōu)先搜索遍歷圖戈

對連通圖，從起始點(diǎn)V到真

各頂點(diǎn)必定存在路徑。

其中

V->w19V->w2?V->w8\

的路徑長度為1;(

V->w7,V->w3,V->w5)

的路徑長度為2;(

V->w6?V->w4C

的路徑長度為3。)

從圖中的某個(gè)頂點(diǎn)V。出發(fā)，并在訪雕

頂點(diǎn)之后依次訪問V。的所有未被訪問遹

鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后想

序依次訪問它們的鄰接點(diǎn)，直至圖中所有（

和V。有路徑相通的頂點(diǎn)都被訪問到。

若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖

中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重虱

上述過程，直至圖中所有頂點(diǎn)都被訪問到《

O

voidBFSTraverse(GraphG,

Status(*Visit)(intW

for(v=0;v<G.vexnum;++v)、

visited[v]=FALSE;〃初始化訪問標(biāo)志

InitQueue(Q);//置空的輔助隊(duì)列Q

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

if(!visited[v]){〃v尚未訪問

FSTraverse

visited[v]=TRUE;Visit(v);//訪問u

EnQueue(Q5v);〃v入隊(duì)列

while(!QueueEmpty(Q)){

DeQueue(Q,u);

〃隊(duì)頭元素出隊(duì)并置為u

for(w=FirstAdjVex(G,u);w!=0;

w=NextAdjVex(G必w))

if(!visited[w]){

visited[w]=TRUE;Visit(w);

EnQueue(Q5w);//訪問的頂點(diǎn)w入隊(duì)列

f

hile◎

7.4最小生成樹

問題:

假設(shè)要在n個(gè)城市之間建立通訊

聯(lián)絡(luò)網(wǎng)，則連通〃個(gè)城市只需要修建

條線路，如何在最節(jié)省經(jīng)費(fèi)的前

寂E建立這個(gè)通訊網(wǎng)？

■

該問題等價(jià)于：

構(gòu)造網(wǎng)的一棵最小生成樹）即:

在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成N

回路），使“權(quán)值之和”為最小。/

笆|3法一：（普里姆算法）

二：（克魯斯卡爾算法）

普里姆算法的基本思想:

取圖中任意一個(gè)頂點(diǎn)v作為生成樹的

之后往生成樹上添加新的頂點(diǎn)W。在添加）

的頂點(diǎn)W和已經(jīng)在生成樹上的頂點(diǎn)V之間\

必定存在一條邊，并且該邊的權(quán)值在所有

連通頂點(diǎn)V和W之間的邊中取值最小。之/

后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹

n-1個(gè)頂點(diǎn)為止。

例如:

7

3

1

14+8+3+5+16+21=6

一般情況下所添加的頂點(diǎn)應(yīng)滿足飛則

條件:在生成樹的構(gòu)造過程中，圖中

頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的

頂點(diǎn)集U和尚未落在生成樹上的頂點(diǎn)煤

V-U,則應(yīng)在所有連通U中頂點(diǎn)和v-uq

頂點(diǎn)的邊中選取權(quán)值最小的邊。

V-U

設(shè)置一個(gè)輔助數(shù)組，對當(dāng)前v-2

中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集U中頂

相連接的代價(jià)最小的邊：

struct{

VertexTypeadjvex;〃11集中的頂點(diǎn)序號

VRTypelowcost;//邊的權(quán)值(

}j^dge[MAXVERTEXNUM];?

例如:19mm148

195712m

m53mm

18m73821

?271412m8m16J

mmm21m2

18mmm1627

^losedg^\0123456

Adjvexc1d1ea1de

5,

514211￡

voidMiniSpanTree_P(MGraphG,VertexType

〃用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小樹

k=LocateVex(G,u);&

for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始夕

if(j!=k)\

closedge[j]={u,G.arcs[k][j].adj};C

closedge[k].lowcost=0;//初始，U={u}J

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

向生成樹上添加頂點(diǎn)；

k=minimum(closedge);

//求出加入生成樹的下一個(gè)頂點(diǎn)(k)

printf(closedge[k].adjvex5G.vexs[k]);

〃輸出生成樹上一條邊

closedge[k].lowcost=0;//第k頂點(diǎn)并入U(xiǎn)集

for(j=0;j<G.vexnum;+±j)

〃修改其它頂點(diǎn)的最小邊

if(G.arcsfk][j].adj<closedge[j].lowcost)

ge[j]={G.vexs[kl,G.arcs[k][j].adjV

向

克魯斯卡爾算法的基本思想:

考慮問題的出發(fā)點(diǎn)：為使生成樹上邊的陽

值之和達(dá)到最小，則應(yīng)使生成樹中每一索

邊的權(quán)值盡可能地小。

具體做法：先構(gòu)造一個(gè)只含11個(gè)頂點(diǎn)的子區(qū)

SG,然后從權(quán)值最小的邊開始，若它的添?

力梵練SG中產(chǎn)生回路，則在SG上加上這

如此重復(fù)）直至加上n-1條邊為止。

例如:

1

算法描述:

構(gòu)造非連通圖ST=(V,{});

k=i=0;〃k計(jì)選中的邊數(shù)

while(k<n-l){

卜+i;

檢查邊集E中第i條權(quán)值最小的邊(u,v);

若(u,v)加入ST后不使ST中產(chǎn)生回路,

刨瀚出邊(u,v)；且k++;

比較兩種算法

算法名普里姆算法克魯斯卡爾算;

時(shí)間復(fù)雜度O(n2)O(eloge)

適應(yīng)范圍稠密圖稀疏圖

7.5兩點(diǎn)之間的

最短路徑問題

?求從某個(gè)源點(diǎn)到其余各點(diǎn)的最

短路徑

?每一對頂點(diǎn)之間的最短路徑

求從源點(diǎn)到其余各點(diǎn)的最短路

的算法的基本思想:

依最短路徑的長度遞增的次序求得

各條路徑

其中，從源點(diǎn)到I

頂點(diǎn)V的最短路專

源點(diǎn)是所有最短路徑，

中長度最短者。（

?路徑長度最短的最短路徑的特點(diǎn)：?

在這條路徑上，必定只含一條弧，W塌

這條弧的權(quán)值最小。

■下一條路徑長度次短的最短路徑的特點(diǎn):

它只可能有兩種情況:或者是直接從源點(diǎn)

到該點(diǎn)（只含一條弧）；或者是，從源點(diǎn)經(jīng)（

再到達(dá)該頂點(diǎn)（由兩條弧組成）1

.再下一條路徑長度次短的最短路徑瞰點(diǎn)

它可能有三種情況：或者是，直接從期、

到該點(diǎn)（只含一條弧）；或者是，從源點(diǎn)a

頂點(diǎn)V1，再到達(dá)該頂點(diǎn)（由兩條弧組成）；4

者是，從源點(diǎn)經(jīng)過頂點(diǎn)V2，再到達(dá)該頂點(diǎn)）

?其余最短路徑的特點(diǎn)：）

它或者是直接從源點(diǎn)到該點(diǎn)（只哈一條（

布渾D或者是，從源點(diǎn)經(jīng)過已求得最短路（

頂點(diǎn)，再到達(dá)該頂點(diǎn)。）

求最短路徑的迪杰斯特拉算法：R

設(shè)置輔助數(shù)組Dist,其中每個(gè)分量

表示當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn)篇

的最短路徑。，

一般情況下，)

Dist[k]=＜源點(diǎn)到頂點(diǎn)k的弧上的權(quán)值》)

或者=＜源點(diǎn)到其它頂點(diǎn)的路徑長度〉，

其它頂點(diǎn)到頂點(diǎn)k的弧上的權(quán)值＞＞

1）在所有從源點(diǎn)出發(fā)的弧中選取一條

值最小的弧，即為第一條最短路徑。

G.arcs[vO][^]VO和k之間存在濯

Di