数据结构课件第09章 图

《数据结构（C++版）》

叶核亚

机械工业出版社

0

《数据结构（C++版）》

■第1章绪论IIII‘I

■第2章线性表

■第3章排序

■第4章串盘■播0c

■第5章栈与队列

■第6章数组和广义表

■第7章树和二叉树

■第8章查找।

/第9章图

■第10章综合应用设计

第9章图

9.1图的基本知识

9.2图的存储结构

9.3图的遍历

9.4邻接矩阵图类

9.5最小代价生成树

9.6最短路径

《数据结构（C++版）》叶核亚

图的基本知识

-JI----

■9L1图的定义

•9.L2结点的度

■9.L3子图

・9.L4路径、回路及连通性

《数据结构（C++版）》叶核亚

9.1.1图的定义

•图（graph）是由结点集合及结点间的关系集合组成

的一种数据结构。图中的结点又称为顶点，结点之

间的关系称为边（edge）。一个图6己作

•其中，呢结点确有限集合，£是边的有限集合。即

V=｛x\x^某个数据元素集合｝

昆｛（“外区片4或良｛〈XV〉因广。

•其中，（”必表示从结点姓11小勺一条双向通路，即（“外

没有方向；〈xM表示从结点加勺一条单向通路，

即〈xM是有方向的。

《数据结构（C++版）》叶核亚

图结构

(a)哥尼斯堡七桥，无向图G](c)有向图G3

《数据结构（C++版）》叶核亚

1.无向图Gi

«&)={/,B,CQ

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

(3)}

2.有向图G3

g)={4BfG

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

《数据结构（C++版）》叶核亚

3.完全图

(a)有向完全图占

《数据结构(C++版)》叶核亚

4.带权图

5.相邻结点

(a)带权的无向图q

《数据结构(C++版)》叶核亚

9.1.2结点的度

1.度、入度、出度

①图中与结点环目关联的边的数目称为结点的

度(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

《数据结构(C++版)》叶核亚

、.9.L3子图

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

i.子图、真子图

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

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

2.生成子图

①如果G是曲子图，且％%称图G是设勺生成子

图。

《数据结构(C++版)》叶核亚

9.1.4路径、回路及连通性

1.路径、路径长度、回路

2.有根的图、图的根

3.连通图

4.强连通图

(b)强连通的有向图

《数据结构(C++版)》叶核亚

9.2图的存储结构

•921邻接矩阵

■9.2.2邻接表

《数据结构（C++版）》叶核亚

、9.2,1邻接矩阵

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

i.邻接矩阵的定义

2.邻接矩阵与结点的[1若（匕,I）eE或<匕#/>eE

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

（a）无向图1010100

0110011

二

10120000

11101010

《数据结构（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

《数据结构（C++版）》叶核亚

9.2,2邻接表

i.无向图的邻接表

datanext

datanext

1A

匕也V4

2也匕»V3---------AV4A

3匕»旷4A

4V4

V1AV2---------V3A

《数据结构（C++版）》叶核亚

2.有向图的邻接表

V4A

(a)出边表(b)入边表

《数据结构(C++版)》叶核亚

9.3图的遍历

•9.31深度优先遍历

■9.3.2广度优先遍历

《数据结构（C++版）》叶核亚

49・3.1深度优先遍历

(a)从顶点为出发，一种可能的访问序列为：｛匕，也，立，匕｝(b)从顶点v出发，一种可能的访问序列为｛为，0，匕，叱｝

《数据结构(C++版)》叶核亚

49・3.2广度优先遍历

①

V

v

(a)从顶点叫出发，一种可能的访问序列为：｛»，为，匕，4)(b)从顶点］，4出发，一种可能的访问序列为｛h，Vl，V3,V2｝

《数据结构(C++版)》叶核亚

9.4邻接矩阵图类

1.声明带权值的边为结构体

structEdgeNodel〃带权值的边

intinit;〃边的起点

intend;〃边的终点

intweight;〃边的权值

）；

《数据结构（C++版）》叶核亚

2.声明邻接矩阵图类

#include<iostream.h>

classGraphl〃邻接矩阵图类

(

private:

intvisited[IVIaxSize];〃访问标记数组

voidunvisited();〃设置未访问标记

voiddepthfs(intk);〃从结点k开始的深度优先遍历

voidbreadthfs(intk);〃从结点k开始的广度优先遍历

public:

charvertex[MaxSize];〃图的结点集合，MaxSize为最大结点数

intmat[MaxSize][IVIaxSize];〃图的邻接矩阵

intvertCount;〃图的结点数

intedgeCount;〃图的边数

《数据结构（C++版）》叶核亚

3,构造函数，初始化一个图

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;〃数据元素权值为0

else

mat[i][j]=IVIaxWeight;〃权值为无穷大

vertCount=0;〃当前结点数为0

edgeCount=0;〃当前边数为0

《数据结构（C++版）》叶核亚

4.以结点集和边集构造一个图

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

〃以结点集合和边集合构造一个图

vertCount=n;〃图的结点个数

inti,j,k;

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

vertex[i]=vert[i];

edgeCount=m;〃图的边数

for(k=0;k<m;k++)〃初始边值加入邻接矩阵

(

i=edge[k].init;〃边的起点

j=edge[k].end;〃边的终点

mat[i][j]=edge[k].weight;〃边的权值

《数据结构（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;

《数据结构（C++版）》叶核亚

6.图的深度优先遍历

voidGraphl::unvisited()〃设置未访问标记

(

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

visited[i]=O;

voidGraphl::depthfs(intk)〃从结点k开始的深度优先遍历

(

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);〃递归

《数据结构（C++版）》叶核亚

7.图的广度优先遍历

typedefintdataType;〃抽象数据类型dataType定义为int

#include"Queuel.h"〃顺序循环队列类

图的广度优先遍历算法中，同样需要使用成员变量visited数组。算法实现如下:

voidGraph1::breadthfs(intk)〃从结点k开始的广度优先遍历

〃卜为起始结点下标

Queuelq1(vertCount);〃设置空队列

inti=k;

cout<<vertex[i]<<"〃访问起始结点

visited[i]=1;〃设置访问标记

q1.enQueue(i);〃访问过的结点k入队

while(!q1.isEmpty())〃队列不空时

(

i=q1.deQueue();〃出队,i是结点K的数组下标

intj=0;

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

《数据结构(C++版)》叶核亚

例9-1创建邻接矩阵图类对象

」L并遍历图

constintMaxSize=10;〃定义最大结点数

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百午

《数据结构（C++版）》叶核亚

9.5最小代价生成树

•9・51树与图

•9.5.2生成树

■9.5.3最小代价生成树

《数据结构（C++版）》叶核亚

4951树与图

（a）树（b）去掉一边成森林，非连通图（c）加上一边就不是树，而是有回路的图

图9-11树、森林与图

《数据结构（C++版）》叶核亚

例9-2以树结构描述测试假币的称

重策略。

《数据结构（C++版）》叶核亚

952生成树

i.生成树的定义

①如果图说无向图G的生成子图且说树，则图厂

称为图G的生成树。

(a)无向图Gf(b)从D出发的深度优先生成树(c)从C出发的广度优先生成树

《数据结构(C++版)》叶核亚

2.生成森林

3.带权图的生成树

（C）广度优先生成树

《数据结构（C++版）》叶核亚

9.5.3最小代价生成树

设G是一个连通的带权图，叱3为边e上的

权，何丽生成树，那么加各边权之

和为

例7)=Z例＞)

e^T

上式称为生成树阴勺权，也称为生成树的代

价(cost)o权最小的生成树称为最小

生成树或最小代价生成树。

《数据结构(C++版)》叶核亚

⑴最小代价生成树

《数据结构（C++版）》叶核亚

2.普里姆算法

(e)选择与/关联的权值最小的边加入⑴最小代价生成树

《数据结构(C++版)》叶核亚

£・6最短路径

1.单源最短路径

源点一约、占八、、路径路径长度最短路径

（匕，匕）2/

匕

31，匕，畛）12

（匕