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

《數(shù)據(jù)結(jié)構(gòu)（C++版）》

葉核亞

機(jī)械工業(yè)出版社

0

《數(shù)據(jù)結(jié)構(gòu)（C++版）》

■第1章緒論IIII‘I

■第2章線性表

■第3章排序

■第4章串盤■播0c

■第5章棧與隊(duì)列

■第6章數(shù)組和廣義表

■第7章樹和二叉樹

■第8章查找?

/第9章圖

■第10章綜合應(yīng)用設(shè)計(jì)

第9章圖

9.1圖的基本知識

9.2圖的存儲結(jié)構(gòu)

9.3圖的遍歷

9.4鄰接矩陣圖類

9.5最小代價(jià)生成樹

9.6最短路徑

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

圖的基本知識

-JI----

■9L1圖的定義

?9.L2結(jié)點(diǎn)的度

■9.L3子圖

?9.L4路徑、回路及連通性

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

9.1.1圖的定義

?圖（graph）是由結(jié)點(diǎn)集合及結(jié)點(diǎn)間的關(guān)系集合組成

的一種數(shù)據(jù)結(jié)構(gòu)。圖中的結(jié)點(diǎn)又稱為頂點(diǎn)，結(jié)點(diǎn)之

間的關(guān)系稱為邊（edge）。一個(gè)圖6己作

?其中，呢結(jié)點(diǎn)確有限集合，￡是邊的有限集合。即

V=｛x\x^某個(gè)數(shù)據(jù)元素集合｝

昆｛（“外區(qū)片4或良｛〈XV〉因廣。

?其中，（”必表示從結(jié)點(diǎn)姓11小勺一條雙向通路，即（“外

沒有方向；〈xM表示從結(jié)點(diǎn)加勺一條單向通路，

即〈xM是有方向的。

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

圖結(jié)構(gòu)

(a)哥尼斯堡七橋，無向圖G](c)有向圖G3

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

1.無向圖Gi

?&)={/,B,CQ

&Gi)={(CQ,(GQ,(4),(4。),(40,(CH,

(3)}

2.有向圖G3

g)={4BfG

&?)={〈A@，〈耳力〉，⑷。，〈GO}

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

3.完全圖

(a)有向完全圖占

《數(shù)據(jù)結(jié)構(gòu)(C++版)》葉核亞

4.帶權(quán)圖

5.相鄰結(jié)點(diǎn)

(a)帶權(quán)的無向圖q

《數(shù)據(jù)結(jié)構(gòu)(C++版)》葉核亞

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

1.度、入度、出度

①圖中與結(jié)點(diǎn)環(huán)目關(guān)聯(lián)的邊的數(shù)目稱為結(jié)點(diǎn)的

度(degree),記作TD(D。

2.度與邊的關(guān)系

nn

Z【D"z）=ZOD“z.）=e

1〃i=\i=\

"笆TD（匕）

nnn

2i=\ZTD（匕）=ZID（匕）+ZOD（匕）=2e

Z=1Z=1Z=1

《數(shù)據(jù)結(jié)構(gòu)(C++版)》葉核亞

、.9.L3子圖

-JI------------

i.子圖、真子圖

(Al)(A2)(A3)(BI)(B2)(B3)(B4)

(a)Gi的部分其子圖(b)(八的部分其子圖

2.生成子圖

①如果G是曲子圖，且％%稱圖G是設(shè)勺生成子

圖。

《數(shù)據(jù)結(jié)構(gòu)(C++版)》葉核亞

9.1.4路徑、回路及連通性

1.路徑、路徑長度、回路

2.有根的圖、圖的根

3.連通圖

4.強(qiáng)連通圖

(b)強(qiáng)連通的有向圖

《數(shù)據(jù)結(jié)構(gòu)(C++版)》葉核亞

9.2圖的存儲結(jié)構(gòu)

?921鄰接矩陣

■9.2.2鄰接表

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

、9.2,1鄰接矩陣

■JI---------------------

i.鄰接矩陣的定義

2.鄰接矩陣與結(jié)點(diǎn)的[1若（匕,I）eE或<匕#/>eE

若（匕，V/）eE或<匕，V/〉氏E

（a）無向圖1010100

0110011

二

10120000

11101010

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

3,帶權(quán)圖的鄰接矩陣

w(vpvy)若匕wV/且(匕，匕)e￡或<V.,vj>GE

)=〈s若%wV/且(vz.,Vj)g￡或<匕,V/>任E

0若匕二v

、“J

05oc200

5068oo「045

A4=oo6037A5=602

283093oo0

0000790

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

9.2,2鄰接表

i.無向圖的鄰接表

datanext

datanext

1A

匕也V4

2也匕?V3---------AV4A

3匕?曠4A

4V4

V1AV2---------V3A

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

2.有向圖的鄰接表

V4A

(a)出邊表(b)入邊表

《數(shù)據(jù)結(jié)構(gòu)(C++版)》葉核亞

9.3圖的遍歷

?9.31深度優(yōu)先遍歷

■9.3.2廣度優(yōu)先遍歷

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

49?3.1深度優(yōu)先遍歷

(a)從頂點(diǎn)為出發(fā)，一種可能的訪問序列為：｛匕，也，立，匕｝(b)從頂點(diǎn)v出發(fā)，一種可能的訪問序列為｛為，0，匕，叱｝

《數(shù)據(jù)結(jié)構(gòu)(C++版)》葉核亞

49?3.2廣度優(yōu)先遍歷

①

V

v

(a)從頂點(diǎn)叫出發(fā)，一種可能的訪問序列為：｛?，為，匕，4)(b)從頂點(diǎn)］，4出發(fā)，一種可能的訪問序列為｛h，Vl，V3,V2｝

《數(shù)據(jù)結(jié)構(gòu)(C++版)》葉核亞

9.4鄰接矩陣圖類

1.聲明帶權(quán)值的邊為結(jié)構(gòu)體

structEdgeNodel〃帶權(quán)值的邊

intinit;〃邊的起點(diǎn)

intend;〃邊的終點(diǎn)

intweight;〃邊的權(quán)值

）；

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

2.聲明鄰接矩陣圖類

#include<iostream.h>

classGraphl〃鄰接矩陣圖類

(

private:

intvisited[IVIaxSize];〃訪問標(biāo)記數(shù)組

voidunvisited();〃設(shè)置未訪問標(biāo)記

voiddepthfs(intk);〃從結(jié)點(diǎn)k開始的深度優(yōu)先遍歷

voidbreadthfs(intk);〃從結(jié)點(diǎn)k開始的廣度優(yōu)先遍歷

public:

charvertex[MaxSize];〃圖的結(jié)點(diǎn)集合，MaxSize為最大結(jié)點(diǎn)數(shù)

intmat[MaxSize][IVIaxSize];〃圖的鄰接矩陣

intvertCount;〃圖的結(jié)點(diǎn)數(shù)

intedgeCount;〃圖的邊數(shù)

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

3,構(gòu)造函數(shù)，初始化一個(gè)圖

Graphl::Graph1()〃初始化圖的結(jié)點(diǎn)集合和鄰接矩陣

(

■nti,j;

for(i=0;i<MaxSize;i++)〃初始化圖的結(jié)點(diǎn)集合

vertex[i]='

for(i=0;i<MaxSize;i++)〃初始化圖的鄰接矩陣

for(j=0;j<MaxSize;j++)

if(i==j)

mat[i]U]=O;〃數(shù)據(jù)元素權(quán)值為0

else

mat[i][j]=IVIaxWeight;〃權(quán)值為無窮大

vertCount=0;〃當(dāng)前結(jié)點(diǎn)數(shù)為0

edgeCount=0;〃當(dāng)前邊數(shù)為0

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

4.以結(jié)點(diǎn)集和邊集構(gòu)造一個(gè)圖

voidGraphl::createGraph(intn,charvert[],intm,EdgeNode1edge[])

〃以結(jié)點(diǎn)集合和邊集合構(gòu)造一個(gè)圖

vertCount=n;〃圖的結(jié)點(diǎn)個(gè)數(shù)

inti,j,k;

for(i=0;i<n;i++)〃初始結(jié)點(diǎn)加入結(jié)點(diǎn)集合

vertex[i]=vert[i];

edgeCount=m;〃圖的邊數(shù)

for(k=0;k<m;k++)〃初始邊值加入鄰接矩陣

(

i=edge[k].init;〃邊的起點(diǎn)

j=edge[k].end;〃邊的終點(diǎn)

mat[i][j]=edge[k].weight;〃邊的權(quán)值

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

5.輸出圖的結(jié)點(diǎn)集合和

鄰接矩陣

ostream&operator<<(ostream&out,Graph1&g1)

(〃輸出圖的結(jié)點(diǎn)集合和鄰接矩陣

coutvv”圖的結(jié)點(diǎn)集合為{";

intij；

for(i=0;i<g1.vertCount-1;i++)

cout<<g1.vertex[i]<<",

cout<<g1.vertex[i]<<,,}"<<endl;

coutvv”圖的令B接矩陣為"vVendl;

for(i=0;i<g1.vertCount;i++)

(

for(j=0;j<g1.vertCount;j++)

if(g1.mat[i][j]==MaxWeight)〃權(quán)值為無窮大時(shí)

cout<<,，oo\tM;

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

6.圖的深度優(yōu)先遍歷

voidGraphl::unvisited()〃設(shè)置未訪問標(biāo)記

(

for(inti=0;i<vertCount;i++)

visited[i]=O;

voidGraphl::depthfs(intk)〃從結(jié)點(diǎn)k開始的深度優(yōu)先遍歷

(

inti=k,j=O;〃i下標(biāo)從0開始

cout<<vertex[i]<<"〃訪問結(jié)點(diǎn)

visited[i]=1;〃設(shè)置訪問標(biāo)記

while(j<vertCount)〃查找與k相鄰的其他結(jié)點(diǎn)

if(i!=j&amat[i][j]>0&&mat[i][j]<IVIaxWeight&&

visited[j]==O）

depthfs(j);〃遞歸

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

7.圖的廣度優(yōu)先遍歷

typedefintdataType;〃抽象數(shù)據(jù)類型dataType定義為int

#include"Queuel.h"〃順序循環(huán)隊(duì)列類

圖的廣度優(yōu)先遍歷算法中，同樣需要使用成員變量visited數(shù)組。算法實(shí)現(xiàn)如下:

voidGraph1::breadthfs(intk)〃從結(jié)點(diǎn)k開始的廣度優(yōu)先遍歷

〃卜為起始結(jié)點(diǎn)下標(biāo)

Queuelq1(vertCount);〃設(shè)置空隊(duì)列

inti=k;

cout<<vertex[i]<<"〃訪問起始結(jié)點(diǎn)

visited[i]=1;〃設(shè)置訪問標(biāo)記

q1.enQueue(i);〃訪問過的結(jié)點(diǎn)k入隊(duì)

while(!q1.isEmpty())〃隊(duì)列不空時(shí)

(

i=q1.deQueue();〃出隊(duì),i是結(jié)點(diǎn)K的數(shù)組下標(biāo)

intj=0;

〃本-t-k匕人口"n甘Z+hZdr上T

《數(shù)據(jù)結(jié)構(gòu)(C++版)》葉核亞

例9-1創(chuàng)建鄰接矩陣圖類對象

」L并遍歷圖

constintMaxSize=10;〃定義最大結(jié)點(diǎn)數(shù)

constintMaxWeight=9999;〃定義權(quán)值為無窮大

#include"Graphl.h"〃鄰接矩陣圖類

voidmain()

(

charvert口H'ABCDE”;

EdgeNodeledge1[]={{0,1,1},{0,3,1},比向圖G6的邊集合

[1,0,1},{1,2,1},{1,3,1},

(2,1,1},{2,4,1},

(3,0,1},{3,1,1},

(4,2,1}};

Graphlg1,g2;

g1.createGraph(5,vert,10,edge1);

cout<<g1;

〃質(zhì)11月J爾由小1百午

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

9.5最小代價(jià)生成樹

?9?51樹與圖

?9.5.2生成樹

■9.5.3最小代價(jià)生成樹

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

4951樹與圖

（a）樹（b）去掉一邊成森林，非連通圖（c）加上一邊就不是樹，而是有回路的圖

圖9-11樹、森林與圖

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

例9-2以樹結(jié)構(gòu)描述測試假幣的稱

重策略。

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

952生成樹

i.生成樹的定義

①如果圖說無向圖G的生成子圖且說樹，則圖廠

稱為圖G的生成樹。

(a)無向圖Gf(b)從D出發(fā)的深度優(yōu)先生成樹(c)從C出發(fā)的廣度優(yōu)先生成樹

《數(shù)據(jù)結(jié)構(gòu)(C++版)》葉核亞

2.生成森林

3.帶權(quán)圖的生成樹

（C）廣度優(yōu)先生成樹

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

9.5.3最小代價(jià)生成樹

設(shè)G是一個(gè)連通的帶權(quán)圖，叱3為邊e上的

權(quán)，何麗生成樹，那么加各邊權(quán)之

和為

例7)=Z例＞)

e^T

上式稱為生成樹陰勺權(quán)，也稱為生成樹的代

價(jià)(cost)o權(quán)最小的生成樹稱為最小

生成樹或最小代價(jià)生成樹。

《數(shù)據(jù)結(jié)構(gòu)(C++版)》葉核亞

⑴最小代價(jià)生成樹

《數(shù)據(jù)結(jié)構(gòu)（C++版）》葉核亞

2.普里姆算法

(e)選擇與/關(guān)聯(lián)的權(quán)值最小的邊加入⑴最小代價(jià)生成樹

《數(shù)據(jù)結(jié)構(gòu)(C++版)》葉核亞

￡?6最短路徑

1.單源最短路徑

源點(diǎn)一約、占八、、路徑路徑長度最短路徑

（匕，匕）2/

匕

31，匕，畛）12

（匕