數(shù)據(jù)結構課件第09章 圖

《數(shù)據(jù)結構（C++版）》

葉核亞

機械工業(yè)出版社

0

《數(shù)據(jù)結構（C++版）》

■第1章緒論IIII‘I

■第2章線性表

■第3章排序

■第4章串盤■播0c

■第5章棧與隊列

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

■第7章樹和二叉樹

■第8章查找?

/第9章圖

■第10章綜合應用設計

第9章圖

9.1圖的基本知識

9.2圖的存儲結構

9.3圖的遍歷

9.4鄰接矩陣圖類

9.5最小代價生成樹

9.6最短路徑

《數(shù)據(jù)結構（C++版）》葉核亞

圖的基本知識

-JI----

■9L1圖的定義

?9.L2結點的度

■9.L3子圖

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

《數(shù)據(jù)結構（C++版）》葉核亞

9.1.1圖的定義

?圖（graph）是由結點集合及結點間的關系集合組成

的一種數(shù)據(jù)結構。圖中的結點又稱為頂點，結點之

間的關系稱為邊（edge）。一個圖6己作

?其中，呢結點確有限集合，￡是邊的有限集合。即

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

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

?其中，（”必表示從結點姓11小勺一條雙向通路，即（“外

沒有方向；〈xM表示從結點加勺一條單向通路，

即〈xM是有方向的。

《數(shù)據(jù)結構（C++版）》葉核亞

圖結構

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

《數(shù)據(jù)結構（C++版）》葉核亞

1.無向圖Gi

?&)={/,B,CQ

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

(3)}

2.有向圖G3

g)={4BfG

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

《數(shù)據(jù)結構（C++版）》葉核亞

3.完全圖

(a)有向完全圖占

《數(shù)據(jù)結構(C++版)》葉核亞

4.帶權圖

5.相鄰結點

(a)帶權的無向圖q

《數(shù)據(jù)結構(C++版)》葉核亞

9.1.2結點的度

1.度、入度、出度

①圖中與結點環(huán)目關聯(lián)的邊的數(shù)目稱為結點的

度(degree),記作TD(D。

2.度與邊的關系

nn

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

1〃i=\i=\

"笆TD（匕）

nnn

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

Z=1Z=1Z=1

《數(shù)據(jù)結構(C++版)》葉核亞

、.9.L3子圖

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

i.子圖、真子圖

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

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

2.生成子圖

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

圖。

《數(shù)據(jù)結構(C++版)》葉核亞

9.1.4路徑、回路及連通性

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

2.有根的圖、圖的根

3.連通圖

4.強連通圖

(b)強連通的有向圖

《數(shù)據(jù)結構(C++版)》葉核亞

9.2圖的存儲結構

?921鄰接矩陣

■9.2.2鄰接表

《數(shù)據(jù)結構（C++版）》葉核亞

、9.2,1鄰接矩陣

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

i.鄰接矩陣的定義

2.鄰接矩陣與結點的[1若（匕,I）eE或<匕#/>eE

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

（a）無向圖1010100

0110011

二

10120000

11101010

《數(shù)據(jù)結構（C++版）》葉核亞

3,帶權圖的鄰接矩陣

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ù)結構（C++版）》葉核亞

9.2,2鄰接表

i.無向圖的鄰接表

datanext

datanext

1A

匕也V4

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

3匕?曠4A

4V4

V1AV2---------V3A

《數(shù)據(jù)結構（C++版）》葉核亞

2.有向圖的鄰接表

V4A

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

《數(shù)據(jù)結構(C++版)》葉核亞

9.3圖的遍歷

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

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

《數(shù)據(jù)結構（C++版）》葉核亞

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

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

《數(shù)據(jù)結構(C++版)》葉核亞

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

①

V

v

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

《數(shù)據(jù)結構(C++版)》葉核亞

9.4鄰接矩陣圖類

1.聲明帶權值的邊為結構體

structEdgeNodel〃帶權值的邊

intinit;〃邊的起點

intend;〃邊的終點

intweight;〃邊的權值

）；

《數(shù)據(jù)結構（C++版）》葉核亞

2.聲明鄰接矩陣圖類

#include<iostream.h>

classGraphl〃鄰接矩陣圖類

(

private:

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

voidunvisited();〃設置未訪問標記

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

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

public:

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

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

intvertCount;〃圖的結點數(shù)

intedgeCount;〃圖的邊數(shù)

《數(shù)據(jù)結構（C++版）》葉核亞

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

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

(

■nti,j;

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

vertex[i]='

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

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

if(i==j)

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

else

mat[i][j]=IVIaxWeight;〃權值為無窮大

vertCount=0;〃當前結點數(shù)為0

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

《數(shù)據(jù)結構（C++版）》葉核亞

4.以結點集和邊集構造一個圖

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

〃以結點集合和邊集合構造一個圖

vertCount=n;〃圖的結點個數(shù)

inti,j,k;

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

vertex[i]=vert[i];

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

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

(

i=edge[k].init;〃邊的起點

j=edge[k].end;〃邊的終點

mat[i][j]=edge[k].weight;〃邊的權值

《數(shù)據(jù)結構（C++版）》葉核亞

5.輸出圖的結點集合和

鄰接矩陣

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

(〃輸出圖的結點集合和鄰接矩陣

coutvv”圖的結點集合為{";

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)〃權值為無窮大時

cout<<,，oo\tM;

《數(shù)據(jù)結構（C++版）》葉核亞

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

voidGraphl::unvisited()〃設置未訪問標記

(

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

visited[i]=O;

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

(

inti=k,j=O;〃i下標從0開始

cout<<vertex[i]<<"〃訪問結點

visited[i]=1;〃設置訪問標記

while(j<vertCount)〃查找與k相鄰的其他結點

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

visited[j]==O）

depthfs(j);〃遞歸

《數(shù)據(jù)結構（C++版）》葉核亞

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

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

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

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

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

〃卜為起始結點下標

Queuelq1(vertCount);〃設置空隊列

inti=k;

cout<<vertex[i]<<"〃訪問起始結點

visited[i]=1;〃設置訪問標記

q1.enQueue(i);〃訪問過的結點k入隊

while(!q1.isEmpty())〃隊列不空時

(

i=q1.deQueue();〃出隊,i是結點K的數(shù)組下標

intj=0;

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

《數(shù)據(jù)結構(C++版)》葉核亞

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

」L并遍歷圖

constintMaxSize=10;〃定義最大結點數(shù)

constintMaxWeight=9999;〃定義權值為無窮大

#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;

〃質11月J爾由小1百午

《數(shù)據(jù)結構（C++版）》葉核亞

9.5最小代價生成樹

?9?51樹與圖

?9.5.2生成樹

■9.5.3最小代價生成樹

《數(shù)據(jù)結構（C++版）》葉核亞

4951樹與圖

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

圖9-11樹、森林與圖

《數(shù)據(jù)結構（C++版）》葉核亞

例9-2以樹結構描述測試假幣的稱

重策略。

《數(shù)據(jù)結構（C++版）》葉核亞

952生成樹

i.生成樹的定義

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

稱為圖G的生成樹。

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

《數(shù)據(jù)結構(C++版)》葉核亞

2.生成森林

3.帶權圖的生成樹

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

《數(shù)據(jù)結構（C++版）》葉核亞

9.5.3最小代價生成樹

設G是一個連通的帶權圖，叱3為邊e上的

權，何麗生成樹，那么加各邊權之

和為

例7)=Z例＞)

e^T

上式稱為生成樹陰勺權，也稱為生成樹的代

價(cost)o權最小的生成樹稱為最小

生成樹或最小代價生成樹。

《數(shù)據(jù)結構(C++版)》葉核亞

⑴最小代價生成樹

《數(shù)據(jù)結構（C++版）》葉核亞

2.普里姆算法

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

《數(shù)據(jù)結構(C++版)》葉核亞

￡?6最短路徑

1.單源最短路徑

源點一約、占八、、路徑路徑長度最短路徑

（匕，匕）2/

匕

31，匕，畛）12

（匕