第7章图(5.11)

1、第第7章章 图图 第第7章章 图图 图图 7.1 图的定义与基本术语图的定义与基本术语 7.2 图的存储结构图的存储结构 7.3 图的遍历图的遍历 7.4 图的连通性问题图的连通性问题 7.5 有向无环图的应用有向无环图的应用 7.6 最短路径最短路径 第第7章章 图图 1. 图的定义G1=G1=V1=vV1=v0 0 ,v ,v1 1,v,v2 2,v,v3 3,v,v4 4 E1=(vE1=(v0 0,v,v1 1),(v),(v0 0,v,v3 3),(v),(v1 1,v,v2 2),(v),(v1 1,v,v4 4),(v),(v2 2,v,v3 3)(v)(v2 2,v,v4 4)

2、 图图G由两个集合构成，记作由两个集合构成，记作G= 其中其中: V（vertex）是顶点的非空有限集合）是顶点的非空有限集合 E（edge）是边的有限集合，）是边的有限集合， 而边是顶点对而边是顶点对的集合。的集合。 V0V0 V4V4 V3V3 V1V1 V2V27.1 图的定义与基本术语图的定义与基本术语 第第7章章 图图 例例1 1 交通图（公路、铁路）交通图（公路、铁路） 顶点顶点：地点：地点 边边：连接地点的公路：连接地点的公路 交通图中的有单行道双行道，分别用交通图中的有单行道双行道，分别用有向边有向边、无向边无向边表示；表示；例例2 2 电路图电路图 顶点顶点：元件：元件 边边

3、：连接元件之间的线路：连接元件之间的线路例例3 3 通讯线路图通讯线路图 顶点顶点：地点：地点 边边：地点间的连线：地点间的连线例例4 4 各种流程图，如产品的生产流程图各种流程图，如产品的生产流程图 顶点顶点：工序：工序 边边：各道工序之间的顺序关系：各道工序之间的顺序关系 图的应用举例：7.1 图的定义与基本术语图的定义与基本术语 第第7章章 图图 第第7章章 图图 例例5 田径赛的时间安排问题（图的着色问题）田径赛的时间安排问题（图的着色问题） ： 设设有六个比赛项目，规定每个选手至多可参加三个项目，有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛

4、日程表，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。使得在尽可能短的时间内完成比赛。姓 名项 目 1项 目 2项 目 3丁 一跳 高跳 远100 米马 二标 枪铅 球张 三标 抢100 米200 米李 四铅 球200 米跳 高王 五跳 远200 米7.1 图的定义与基本术语图的定义与基本术语 第第7章章 图图 （1）设用如下六个不同的代号代表不同的项目：）设用如下六个不同的代号代表不同的项目： 跳高跳高 跳远跳远 标枪标枪 铅球铅球 100米米 200米米 A B C D E F （2）用顶点代表比赛项目）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一

5、条边。不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目必定有边相连（不能同）某选手比赛的项目必定有边相连（不能同时比赛）。时比赛）。 -田径赛的时间安排问题解法田径赛的时间安排问题解法7.1 图的定义与基本术语图的定义与基本术语 第第7章章 图图 姓名项目1 项目2 项目3丁一 A B E马二 C D 张三 C E F李四 D F A王五 B FAEBFDC比赛时间比赛项目1A，C2B，D3E4F田径赛赛程安排问题田径赛赛程安排问题图的顶点着色问题图的顶点着色问题 用用4种颜色即可为所有顶点着色，使种颜色即可为所有顶点着色，使得相邻顶点不同色，即只需安排四个得相邻顶点不同色，即只

6、需安排四个单位时间进行比赛单位时间进行比赛第第7章章 图图 邻接点：边的两个顶点邻接点：边的两个顶点关联边：若边关联边：若边e= (v, u), e= (v, u), 则称顶点则称顶点v v、u u 关联边关联边顶点的度顶点的度 在无向图中在无向图中, ,顶点顶点V V的度的度 = = 与与V V相关联的边的数相关联的边的数目，记作目，记作TD(V)TD(V) 在有向图中在有向图中, ,顶点顶点V V的度的度= V= V的出度的出度+V+V的入度的入度 顶点顶点V V的出度的出度= =以以V V为起点有向边数为起点有向边数 顶点顶点V V的入度的入度= =以以V V为终点有向边数为终点有向边数

7、2. 图的基本术语图的基本术语7.1 图的定义与基本术语图的定义与基本术语 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3第第7章章 图图 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3顶点顶点入度入度 出度出度度度V0123V1101V2112V3112顶点顶点度度V02V13V23V32V42顶点的度顶点的度7.1 图的定义与基本术语图的定义与基本术语 第第7章章 图图 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 完全图完全图：无向完全图：无向完全图：任意两顶点

8、间都有边的图。任意两顶点间都有边的图。 在一个含有在一个含有n n个顶点的无向完全图中，有个顶点的无向完全图中，有n(n-1)/2n(n-1)/2条边。条边。有向完全图有向完全图:任意两顶点之间都有方向互为相反的两任意两顶点之间都有方向互为相反的两条弧相连接的有向图。条弧相连接的有向图。 在一个含有在一个含有n n个顶点的有向完全图中，有个顶点的有向完全图中，有n(n-1)n(n-1)条弧。条弧。2. 图的基本术语图的基本术语7.1 图的定义与基本术语图的定义与基本术语 第第7章章 图图 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3路径路径GG中的中

9、的顶点序列顶点序列v v1 1,v,v2 2, , ,v ,vk k, ,若各边若各边(v(vi i,v,vi+1i+1) ) E, E, 则称该序列是从顶点则称该序列是从顶点v v1 1到顶点到顶点v vk k的路径；的路径；回路回路若路径的顶点和终点相同，则称回路。若路径的顶点和终点相同，则称回路。简单路径简单路径 在一条路径中在一条路径中,若除起点和终点外若除起点和终点外,所有顶点所有顶点各不相同各不相同,则该路径为简单路径；则该路径为简单路径；简单回路简单回路由简单路径组成的回路称为简单回路；由简单路径组成的回路称为简单回路；路径和回路路径和回路7.1 图的定义与基本术语图的定义与基本

10、术语 第第7章章 图图 (a)(a)(b)(b)(c)(c) V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 设有两个图设有两个图G=（V，E）、）、G1=（V1，E1），若），若V1 V，E1 E，E1关联的顶点都在关联的顶点都在V1中，则称中，则称 G1是是G的的子图子图； 例例 (b)、(c) 是是 (a) 的子图的子图子图子图7.1 图的定义与基本术语图的定义与基本术语 第第7章章 图图 非连通图非连通图 连通图连通图 强连通图强连通图 非强连通图非强连通图 V0V0 V1V1 V2V

11、2 V3V3 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4 在无（有）向图在无（有）向图G=中，若中，若对任何两个顶点对任何两个顶点 v、u 都存在从都存在从v 到到 u 的路径的路径，则称，则称G是是连通图连通图对有向图而言，称对有向图而言，称强连通图强连通图连通图、强连通图连通图、强连通图7.1 图的定义与基本术语图的定义与基本术语 第第7章章 图图 连通分量连通分量非连通图非连通图 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4无向图无向图G 的极大连通子图称为的极大连通子

12、图称为G的连通分量的连通分量极大连通子图极大连通子图：该子图是：该子图是 G 连通子图，将连通子图，将G 的任何的任何不在该子图中的顶点加入，子图不再连通；不在该子图中的顶点加入，子图不再连通；7.1 图的定义与基本术语图的定义与基本术语 第第7章章 图图 强连通分量强连通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 有向图有向图D 的极大强连通子图称为的极大强连通子图称为D 的强连通分量的强连通分量 极大强连通子图极大强连通子图：该子图是：该子图是D的强连通子图，将的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强的任何不在该子图中的顶点加入

13、，子图不再是强连通的；连通的；7.1 图的定义与基本术语图的定义与基本术语 第第7章章 图图 连通图连通图 G1G1G1G1的生成树的生成树 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2生成树生成树 包含无向图包含无向图G 所有顶点的的极小连通子图称为所有顶点的的极小连通子图称为G 的的生成树生成树。 极小连通子图极小连通子图：该子图是：该子图是G 的连通子图，在该子图中删除任的连通子图，在该子图中删除任何一条边，子图不再连通。何一条边，子图不再连通。 若若T是是G 的生成树当且仅当的生成树

14、当且仅当T 满足如下条件：满足如下条件： T是是G 的连通子图的连通子图 T包含包含G 的所有顶点的所有顶点 T中无回路中无回路7.1 图的定义与基本术语图的定义与基本术语 第第7章章 图图 边的权：在图的边或弧上表示数字，表示与该边边的权：在图的边或弧上表示数字，表示与该边相关的数据信息，这个数据信息就称该边的权（相关的数据信息，这个数据信息就称该边的权（weightweight）。）。 网（网（networknetwork）：边（或弧）上带权的图称为网。）：边（或弧）上带权的图称为网。 V0V0 V4V4 V3V3 V1V1 V2V28246537.1 图的定义与基本术语图的定义与基本术语

15、 第第7章章 图图 1设无向图的顶点个数为设无向图的顶点个数为n，则该图最多有（，则该图最多有（ ）条边。）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 EN22一个一个n个顶点的连通无向图，其边的个数至少为（个顶点的连通无向图，其边的个数至少为（ ）。）。An-1 Bn Cn+1 Dnlogn；3n个结点的完全有向图含有边的数目（）。个结点的完全有向图含有边的数目（）。An*n n（n） Cn2 Dn*（nl）4一个有一个有n个结点的图，最少有（个结点的图，最少有（ ）个连通分量，最多有）个连通分量，最多有（ ）个连通分量。）个连通分量。A0 B1 Cn-1 Dn5在一个无

16、向图中，所有顶点的度数之和等于所有边数（在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（之和的（ ）倍。）倍。A1/2 B2 C1 D43.3.课堂练习课堂练习7.1 练习题练习题 第第7章章 图图 图的存储结构要保存两类信息：图的存储结构要保存两类信息：1)1)顶点的数据顶点的数据2)2)顶点间的关系顶点间的关系 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3邻接矩阵表示法邻接矩阵表示法邻接表表示法邻接表表示法V0V1V2V3V47

17、.2 图的存储结构图的存储结构第第7章章 图图 Aij=Aij=1 1 若若(v(vi i,v,vi+1i+1) ) E E 或或 v E E0 0 否则否则0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 0 00 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 0 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 图图G的邻接矩阵是满足如下条件：的邻接矩阵是满足如下条件：V0

18、V1 V2 V3 V4V0 V1 V2 V3邻接矩阵邻接矩阵第第7章章 图图 0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 0 0邻接矩阵表示法的空间代价邻接矩阵表示法的空间代价只与图的顶点数有关只与图的顶点数有关 V0V0 V4V4 V3V3 V1V1 V2V21）无向图邻接矩阵是）无向图邻接矩阵是对称矩阵对称矩阵，可考虑矩阵的压缩存储，可考虑矩阵的压缩存储2）G占用存储空间只与它的顶点数有关，与边数无关；占用存储空间只与它的顶点数有关，与边数无关； 适用于边稠密的图适

19、用于边稠密的图V0 V1 V2 V3 V4邻接矩阵表示的特点邻接矩阵表示的特点第第7章章 图图 邻接矩阵下图的有关操作邻接矩阵下图的有关操作1）求顶点）求顶点v的度：的度：2）判断两顶点是否邻接：）判断两顶点是否邻接：3）在图中增加、删除边：）在图中增加、删除边：4）检测图中的总边数：）检测图中的总边数： V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V30 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 0 00 1 1 00 1 1 0

20、0 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 0V0 V1 V2 V3 V4V0 V1 V2 V3等于二维数组对应行（或列）中等于二维数组对应行（或列）中1的个数；的个数；只需判二维数组对应分量是否为只需判二维数组对应分量是否为1；只需对二维数组对应分量赋值只需对二维数组对应分量赋值1或清或清0；扫描整个数组扫描整个数组A，统计出数组中非，统计出数组中非0元素元素的个数。的个数。第第7章章 图图 邻接矩阵的邻接矩阵的C语言描述语言描述#define N 10 /*最多顶点数最多顶点数*/typedef char vextype; /*顶点类型顶点类型*/typ

21、edef sturct vextype vexsN; /*存顶点的数组存顶点的数组*/ adjtype edgeNN;/*存边信息的矩阵存边信息的矩阵*/ int n; /顶点数顶点数 int e; /边数边数matrix_graph0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 0 0 V0V0 V4V4 V3V3 V1V1 V2V2V0 V1 V2 V3 V4第第7章章 图图 建立无向图的邻接矩阵建立无向图的邻接矩阵 算法思想：算法思想：1）给存顶点的一维数组赋值；）给

22、存顶点的一维数组赋值；2）初始化存边的二维数组；）初始化存边的二维数组；3）依次读入顶点对，给二维数组相关的元素）依次读入顶点对，给二维数组相关的元素赋值。赋值。第第7章章 图图 V0V0 V4V4 V3V3 V1V1 V2V22 2 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 13 34 42 22 21 11 10 00 03 34 4下标下标 编号编号 指针指针邻接表表示邻接表表示1. 无向图的邻接表无向图的邻接表 顶点：通常按编号顺序将顶点数据存储在一维数组中；顶点：通常按编号顺序将顶点数据存储在一维数组中； 关联同一顶点的边：用关联同

23、一顶点的边：用线性链表线性链表存储存储表头数据表头数据指向邻接表的指向邻接表的指针指针邻接结点邻接结点数据数据指向下一邻接指向下一邻接点的指针点的指针第第7章章 图图 1 1）有向图的邻接表（出边表）有向图的邻接表（出边表）顶点：用一维数组存储（按编号顺序）顶点：用一维数组存储（按编号顺序）以同一顶点为以同一顶点为起点起点的弧：用线性链表存储的弧：用线性链表存储下标下标 编号编号 指针指针 V0V0V1V1V2V2V3V31 12 23 30 0 0 1 2 3m-1 V0V0 V1V1 V2V2 V3V3有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表第第7章章 图图 2 2）有向图的逆邻接

24、表（入边表）有向图的逆邻接表（入边表）顶点：用一维数组存储（按编号顺序）顶点：用一维数组存储（按编号顺序）以同一顶点为以同一顶点为终点终点的弧：用线性链表存储的弧：用线性链表存储V0V0V1V1V2V2V3V3 0 1 2 3m-10 00 02 23 3 V0V0 V1V1 V2V2 V3V3有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表第第7章章 图图 1）求顶点）求顶点v的度：的度：2）判断两顶点是否邻接：）判断两顶点是否邻接：3）在图中增加、删除边：）在图中增加、删除边：4）检测图中的总边数：）检测图中的总边数：邻接表存储下图的有关操作邻接表存储下图的有关操作等于等于v对应线性链表的

25、长度；对应线性链表的长度；要看要看v对应线性链表中有无对应结点对应线性链表中有无对应结点在相应的顶点的链表中插入、删在相应的顶点的链表中插入、删除结点除结点求每条线性链表的长度和求每条线性链表的长度和第第7章章 图图 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 13 34 42 22 21 11 10 00 04 43 3邻接表的空间代价邻接表的空间代价与图的边及顶点数均有关与图的边及顶点数均有关 V0V0 V4V4 V3V3 V1V1 V2V22 2 1）在）在G邻接表中，同一条边对应两个结点；邻接表中，同一条边对应两个结点； 2）设存储顶点

26、的一维数组大小为）设存储顶点的一维数组大小为m(m 图的顶点数图的顶点数n), 图的边图的边数为数为e，G占用存储空间为：占用存储空间为：m+2*e。G占用存储空间与占用存储空间与 G 的的顶点数、边数均有关；适用于边稀疏的图顶点数、边数均有关；适用于边稀疏的图无向图的邻接表的特点无向图的邻接表的特点第第7章章 图图 typedef struct Arcnode /定义定义 边结点的类型边结点的类型 int adjver; /边的邻接点的数据边的邻接点的数据 struct Arcnode *nextarc; /指向下一邻接点的指针指向下一邻接点的指针 Arcnode; typedef stru

27、ct VNode VertexType data; /顶点数据顶点数据 ArcNode *firstarc; /指向该顶点第一条弧的指针指向该顶点第一条弧的指针*/ Vnode,AdjListMAX_VERTEX_NUM ; typedef struct AdjList vertices; int vexnum, arcnum; /图的顶点数和弧数图的顶点数和弧数 int kind; /图的种类标志图的种类标志ALGraph; 邻接表在邻接表在C语言中的类型定义语言中的类型定义第第7章章 图图 建立无向图的邻接表建立无向图的邻接表 V0V0 V4V4 V3V3 V1V1 V2V2将图转换为线性

28、输入信息：将图转换为线性输入信息：顶点数为：顶点数为：n=5边数为边数为:e=6边集：边集：0 10 31 21 42 32 4第第7章章 图图 思想：如何给存储结构赋值思想：如何给存储结构赋值1. 建立顶点数组。读入各顶点数据建立顶点数组。读入各顶点数据data，将，将firstarc域赋域赋NULL。2. 建立各顶点的邻接表。读入顶点对建立各顶点的邻接表。读入顶点对, 生成两个结点，分生成两个结点，分别插入顶点别插入顶点v, u的邻接表的头部。直至处理完所有的边。的邻接表的头部。直至处理完所有的边。 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V4

29、1 13 31 10 01 12 22 20 03 34 42 24 40 10 31 21 42 32 4建立无向图的邻接表建立无向图的邻接表第第7章章 图图 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 1加入边加入边(u, v): 设设u=0, v=10 0建立无向图的邻接表建立无向图的邻接表第第7章章 图图 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 10 0插入边插入边 (v0,v3):u=0,v=33 3建立无向图的邻接表建立无向图的邻接表第第7章章 图图 在不同的存储结构下，实现各种

30、操作的效率可能在不同的存储结构下，实现各种操作的效率可能是不同的。所以在求解实际问题时，要根据求解问题是不同的。所以在求解实际问题时，要根据求解问题所需操作，选择合适的存储结构。所需操作，选择合适的存储结构。存储结构的选择存储结构的选择第第7章章 图图 课堂练习课堂练习1、已知有向图G，V（G）=1，2，3，4，E（G）=，试画出G的邻接矩阵，并说明，若已知点i，如何根据邻接矩阵找到与i相邻的点j？ 2、已知无向图G，V（G）=1，2，3，4，E（G）= （1，2），（1，3），（2，3），（2，4），（3，4）试画出G的邻接表，并说明，若已知点i，如何根据邻接表找到与i相邻的点j第第7章章

31、图图 复习复习1、有头结点的单链表4，2，6，5，3，1（1）单链表的建立（头部插入新结点和尾部插入新结点两种方法）（2）输出并删除第i个结点（3）在第i个位置插入新元素x (4) 对所有元素排序2、重做约瑟夫环猴子选猴王（无头结点的循环链表）第第7章章 图图 采用怎样的策略进行图的遍历采用怎样的策略进行图的遍历 有两种遍历方法有两种遍历方法： 深度优先遍历（深度优先遍历（DFSDFS：Depth First SearchDepth First Search） 广度优先遍历（广度优先遍历（BFSBFS：Breadth First SearchBreadth First Search）7.3图的

32、遍历图的遍历 图的遍历：从图的某顶点出发，访问图中所有顶图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。点，并且每个顶点仅访问一次。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4第第7章章 图图 一一 、深度优先遍历（、深度优先遍历（DFS）1 1）从图中某顶点）从图中某顶点v v出发，访问顶点出发，访问顶点v v；2 2）依次从）依次从v v的未被访问的邻接点出发，继续对图进行深度优先的未被访问的邻接点出发，继续对图进行深度优先遍历；遍历； V0,V1,V3

33、,V7,V4,V2,V5,V6 V0,V1,V3,V7,V4,V2,V5,V6 由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，DFSDFS序列不唯一序列不唯一例例求图求图G G以以V0V0起点的深度优先序列起点的深度优先序列：V0,V1,V4,V7,V3,V2,V5,V6V0,V1,V4,V7,V3,V2,V5,V6 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V47.3.1 两种遍历思想两种遍历思想第第7章章 图图 图中某未访问过的顶点图中某未访问过的顶点vivi出发：

34、出发：1 1）访问顶点）访问顶点vi vi ；2 2）访问）访问 vi vi 的所有未被访问的邻接点的所有未被访问的邻接点w w1 1 ,w ,w2 2 , , w wk k ；3 3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; ; 直到图中所有访问过的顶点的邻接点都被访问；直到图中所有访问过的顶点的邻接点都被访问；二、广度优先遍历（二、广度优先遍历（BFSBFS） V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4由于没有

35、规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，BFSBFS序列不唯一序列不唯一例例求图求图G G 的以的以V0V0起点的的广度优先序列起点的的广度优先序列: :V0,V1,V2,V3,V4,V5,V6,V7 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4第第7章章 图图 写出下图的深度优先遍历序列和广度优先遍历序列25476831( a )深度优先：深度优先：1 2 5 8 6 7 3 4深度优先：深度优先：1 3 5 8 6 7 3 4广度优先：广度优先：1 2 3 4 5

36、6 7 8小练习小练习第第7章章 图图 在图中，访问部分顶点后，可能又沿着其他边在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，可用一个辅助数组问一次，必须对顶点进行标记，可用一个辅助数组 visitedMAX作为对顶点的标记。作为对顶点的标记。7.3.2 图的遍历算法图的遍历算法辅助数组辅助数组 int visitedMAX; /顶点标志数组顶点标志数组,全局变量全局变量 若若visitedi=0，顶点，顶点vi未被访问未被访问 若若visitedi=1，当，当vi已被访问。已被访问。

37、visitvisit0 01 12 23 34 4m-1m-10 00 00 00 00 0第第7章章 图图 void DFSTraverse (Graph G,Status (*visit)(int v)/*对图对图G进行深度优先搜索，进行深度优先搜索，Graph 表示图的一种存储结构表示图的一种存储结构*/ VisitFunc = Visit; for (v=0; vG.vexnum; v+) visitedv=False ; /*访问标志数组初访问标志数组初始化始化*/ for( v=0; v=0; w=NextAdjVex(G, v, w) if(! visitedw) DFS(G,

38、w); /*递归调用递归调用DFS*/ /*DFS*/第第7章章 图图 递归过程分析递归过程分析 3 1 2 4 5 7 6 8 -无向图无向图 DFS(1)DFS(2)DFS(4)DFS(8)DFS(5)DFS(6)DFS(3)DFS(7)邻接矩阵深度优先搜索示意图邻接矩阵深度优先搜索示意图第第7章章 图图 基于邻接表的基于邻接表的DFS算法算法:DFSl() 核心问题：如何在邻接表中沿深度进行遍历 时间复杂度：O(n+e)第第7章章 图图 思想：思想：图中某未访问过的顶点图中某未访问过的顶点vi出发：出发：1）访问顶点）访问顶点vi ；2）访问）访问 vi 的所有未被访问的邻接点的所有未被

39、访问的邻接点w1 ,w2 , wk ；3）依次从这些邻接点出发，访问它们的所有未被）依次从这些邻接点出发，访问它们的所有未被访问的邻接点访问的邻接点; 依此类推，直到图中所有访问过依此类推，直到图中所有访问过的顶点的邻接点都被访问；的顶点的邻接点都被访问；2.广度优先遍历算法广度优先遍历算法第第7章章 图图 问题：如何保证邻接点的访问顺序？问题：如何保证邻接点的访问顺序？25476831( a )要借助队列：要借助队列：访问顺序：访问顺序： 3 5 6 8 7输出下图从输出下图从1出发的广度优先遍历序列出发的广度优先遍历序列第第7章章 图图 解决：利用队列解决：利用队列1）从图中某未访问过的顶

40、点）从图中某未访问过的顶点vi出发：出发：2）访问顶点）访问顶点vi ；3）访问）访问 vi 的所有未被访问的邻接点的所有未被访问的邻接点w1 ,w2 , wk ；4）将）将w1 ,w2 , wk 入队；入队；5）取队头顶点，从该顶点出发，访问它的所有）取队头顶点，从该顶点出发，访问它的所有未被访问的邻接点；即重复未被访问的邻接点；即重复25，直到图中所，直到图中所有访问过的顶点的邻接点都被访问有访问过的顶点的邻接点都被访问第第7章章 图图 BFS算法算法: /设从V0开始； (1) 访问V0 (2)将V0加入队列Q（3）当队列Q非空 (4) 取队头元素存入i (5) 对i的所有邻接点j, 做

41、如下处理： 如果j 未被访问过，则访问j并让j入队列 第第7章章 图图 BFS算法算法:void BFSTraverse(Graph G, Statis (*Visit)(int v) for(v=0;vG.vexnum;+v) visitedv =FALSE; InitQueue(Q); /*初始化空队*/ for(v = 0;v =0; w=NextAdjVex(G, u, w) if (!visitedw) Visit(w); visitedw=True; EnQueue(Q, w); /if /while /if /BFSTraverse第第7章章 图图 课堂练习课堂练习1无向图无向图

42、G=(V,E),其中：其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行，对该图进行深度优先遍历，得到的顶点序列正确的是（深度优先遍历，得到的顶点序列正确的是（ ）。）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b第第7章章 图图 2、设下图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ）a e b d f c a c f d e b a e d f c b a e f d c b a e f d b cA5个 B4个 C3个 D2个 a

43、bedcf第第7章章 图图 3 下面的邻接表表示一个给定的无向图 （1）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列；（2）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。第第7章章 图图 7.4 图的连通性问题图的连通性问题7.4.1 无向图的连通分量无向图的连通分量 对于连通图，无论是广度优先搜索还是深度优先搜对于连通图，无论是广度优先搜索还是深度优先搜索，仅需要调用索，仅需要调用一次一次搜索过程，便可以遍历图中的各搜索过程，便可以遍历图中的各个顶点。个顶点。 对于非连通图，则需要对于非连通图，则需要多次多次调用搜索过程，而每次调用搜索过程，而每次调用得到

44、的顶点访问序列恰为各连通分量中的顶点集。调用得到的顶点访问序列恰为各连通分量中的顶点集。第第7章章 图图 图图7.17 图及其连通分量图及其连通分量 15671082349123456789102112655102834437499(a) 无向图G5(b) G5的邻接表图7.1734129108567(c) 无向图G5的三个连通分量第第7章章 图图 设设E(G)E(G)为连通图为连通图G G中所有边的集合，则从图中任一顶点出发遍中所有边的集合，则从图中任一顶点出发遍历图时，将历图时，将E(G)E(G)分成两个集合分成两个集合T(G)T(G)和和B(G)B(G)。T(G)T(G)为遍历时的边的为

45、遍历时的边的集合，集合，B(G)B(G)是剩余边的集合。显然，是剩余边的集合。显然，T(G)T(G)和和G G中所有顶点一起构成中所有顶点一起构成连通图连通图G G的极小连通子图，且为一棵生成树，分别称为深度优先生的极小连通子图，且为一棵生成树，分别称为深度优先生成树和广度优先生成树。成树和广度优先生成树。 对于非连通图，每个连通分量的顶点集和走过的边集一起构对于非连通图，每个连通分量的顶点集和走过的边集一起构成若干生成树，称为生成森林。成若干生成树，称为生成森林。 第第7章章 图图 7.4.2 7.4.2 最小生成树最小生成树(prim(prim算法）算法） 设G =(V,E)是无向连通带权

46、图，即一个网络网络。 E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树生成树。 生成树上各边权的总和称为该生成树的耗费耗费。 在G的所有生成树中，耗费最小的生成树称为G的最小生成树最小生成树。第第7章章 图图 网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。 最小生成树的应用最小生成树的应用第第7章章 图图 设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)是一条具有最小代价的边，且uU，

47、vV-U，则必存在一棵包含边(u,v)的最小生成树。这个性质简称为MSTMST性质性质。 本节介绍的本节介绍的PrimPrim算法和算法和KruskalKruskal算法都算法都可以看作是应用贪心算法设计策略的例子。可以看作是应用贪心算法设计策略的例子。尽管这尽管这2 2个算法做贪心选择的方式不同，它个算法做贪心选择的方式不同，它们都利用了上面的最小生成树性质。们都利用了上面的最小生成树性质。1 1、最小生成树性质、最小生成树性质第第7章章 图图 设G=(V,E)是连通带权图，V=1,2,n。 Prim算法的基本思想基本思想是： （1）首先置S=1，生成树边集T= ； （2）然后，只要S是V的

48、真子集，就作如下的贪心选择：贪心选择：选取满足条件选取满足条件i i S S，j j V-SV-S，且，且cijcij最小的边，将顶点最小的边，将顶点j j添加到添加到S S中中, ,将边（将边（i,j)i,j)加入加入T T。 这个过程一直进行到S=V时为止。 在这个过程中选取到的所有边恰好构成G的一棵最小生成树最小生成树。 2 2、PrimPrim算法算法第第7章章 图图 点到集合的距离点到集合的距离 集合外一点u，到集合S=v1,v2,vn的距离定义为点u到结合s中所有点间的最小距离。即： D(u,S)=mind(u,vi), vi属于S第第7章章 图图 PrimPrim算法的基本思想算

49、法的基本思想 有了点到集合的距离，Prim算法的基本思想基本思想可这样描述： （1）首先置S=1，生成树边集T= ； （2）然后，只要S是V的真子集，就作如下的贪贪心选择：心选择：在在S S外的点中选取离集合外的点中选取离集合S S最近的点加入最近的点加入S.S. 这个过程一直进行到S=V时为止。 这个过程中选取到的所有边恰好构成G的一棵最最小生成树小生成树。第第7章章 图图 例如例如，对于下图中的带权图，按PrimPrim算法算法选取边的过程如图所示。62111965432174133L=0 1 2 10 6 11 26 0 9 11 11 9 0 7 3 13 7 0 4 3 4 0 第第

50、7章章 图图 62111965432174133(1)初始状态：任选一点加入初始状态：任选一点加入S, S=1，T=；第第7章章 图图 62111965432174133（2）选顶点）选顶点2(d(1,2)=1)加入加入S： S=1，2将边（将边（1，2）加入）加入T，T=（1，2）；2第第7章章 图图 62111965432174133 (3)选顶点选顶点3(d(1,3)=2)加入加入S： S=1，2，3将边（将边（1，3）加入）加入T，T=(1,2)，(1,3)；3第第7章章 图图 62111965432174133 (4)选顶点选顶点4(d(3,4)=9)加入加入S： S=1，2，3，4

51、将边（将边（3，4）加入）加入T，T=(1,2),(1,3),(3,4)；4第第7章章 图图 62111965432174133(5)选顶点选顶点6(d(4,6)=3)加入加入S： S=1，2，3，4，6将边（将边（4，6）加入）加入T，T=(1,2),(1,3),(3,4),(4,6)；6第第7章章 图图 62111965432174133（6）选顶点）选顶点5(d(6,5)=4)加入加入S： S=1，2，3，4，6将边（将边（6，5）加入）加入T，T=(1,2),(1,3),(3,4),(4,6),(6,5)；5第第7章章 图图 为了实现这个算法需要设置一个为了实现这个算法需要设置一个辅助

52、数组辅助数组closedge，以，以记录从记录从U到到V-U具有最小代价的边。对每个顶点具有最小代价的边。对每个顶点vV-U，在辅，在辅助数组中存在一个分量助数组中存在一个分量closedgev，它包括两个域，它包括两个域adjvex和和lowcost，其中，其中lowcost存储该边上的权，存储该边上的权， 显然有显然有 closedgev.lowcost=Min(cost(u, v) | uU)struct VertexType adjvex; VRType lowcost; closedgeMAX_VERTEX_NUM; /* 求最小生成树时的求最小生成树时的辅助数组辅助数组*/ 第第7

53、章章 图图 -100-1-1-101 12lowcost:adjvex:Closedgei.lowcost:记录顶点记录顶点i 到到S的最短距离；的最短距离；Closedgei. adjvex:记录顶点记录顶点i到集合中哪个顶点最近到集合中哪个顶点最近第第7章章 图图 62111965432174133(1)初始状态：初始状态：任选一点加入任选一点加入S, S=1，T=； 以上选择过程计算机如何实现？以上选择过程计算机如何实现？-100-1-1-101 12lowcost:adjvex:第第7章章 图图 62111965432174133(2) 在在S 外的顶点中选择顶点外的顶点中选择顶点2加

54、入加入S。-100-1-1-101 120更新更新s外的点到外的点到s的距离及最近顶的距离及最近顶点点111lowcost:adjvex:第第7章章 图图 (3) 选择离集合选择离集合S最近的顶点最近的顶点3加入加入S62111965432174133-1002-1-100 0211更新更新s外的点到外的点到s的距离及最近顶的距离及最近顶点点092132lowcost:adjvex:第第7章章 图图 (4) 选择离集合选择离集合S最近的顶点最近的顶点4加入加入S62111965432174133-1002-1-100 00913更新更新s外的点到外的点到s的距离及最近顶的距离及最近顶点点033

55、37lowcost:adjvex:第第7章章 图图 (5) 选顶点选顶点6加入加入S62111965432174133-10024300 00073更新更新s外的点到外的点到s的距离及最近顶的距离及最近顶点点045lowcost:adjvex:第第7章章 图图 (6) 选顶点选顶点5加入加入S：62111965432174133-10025300 00040lowcost:adjvex:0第第7章章 图图 void Prim(int GN, int n) /用普里姆方法建立网G的最小生成树minSTree/初始化/从序号为0的顶点出发构造最小生成树/寻找当前最小权值的边的顶点/修改其他顶点的边

56、的权值Prim算法的实现算法的实现第第7章章 图图 在Prim算法执行过程中，先找出数组closedge中lowcost值最小的顶点k, 将k添加到S中，并对lowcost和adjvex作必要的修改。 用这个办法实现的Prim算法所需的计算时计算时间间为)(2nO第第7章章 图图 void MiniSpanTree_Prim(MGraph G, VertexType u)/*从顶点从顶点u出发，出发， 按普里姆算法构造连通网按普里姆算法构造连通网G 的最小生的最小生成树，成树， 并输出生成树的每条边并输出生成树的每条边*/ k=LocateVertex(G, u); for (j=0; jG.

57、vexnum; j+) if ( j! =k) closedgej=u, G.arcskj.adj; closedgek.lowcost=0; 第第7章章 图图 for (i=1; iG.vexnum; i+) k=Minium(closedge); printf(closedgek.adjvex, G.vexsk); /*输出生成树的当输出生成树的当前最小边前最小边*/ closedgek.lowcost=0; /*将顶点将顶点k纳入纳入U集合集合*/ for ( j=0 ; jG.vexnum; j+) /*在顶点在顶点v0并入并入U之后，之后， 更更新新closedgej */ if (

58、 G.arcskj.adj closedgej.lowcost) closedgej=G.vexsk, G.arcskj.adj; /for /minispantree_prim第第7章章 图图 3.Kruskal3.Kruskal算法算法贪心策略：总是选择最小代价连通两个不同的连通分贪心策略：总是选择最小代价连通两个不同的连通分支。支。基本思想基本思想：（1）首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。（2）然后从第一条边开始，依边权递增的顺序查看每一条边(v,w) ： （a)如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就保留边(v,w) (b)

59、如果端点v和w在当前的同一个连通分支中，就直接丢弃边(v,w)。 这个过程一直进行到只剩下一个连通分支时为止。第第7章章 图图 例如，例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。62111965432174133第第7章章 图图 365421边集合排序：边集合排序：(1,2)=1, (1,3)=2, (4,6)=3, (5,6)=4, (2,3)=6, (4,5)=7 (3,4)=9, (2,4)=11, (3,5)=13第第7章章 图图 365421最小生成树的边：最小生成树的边：(1,2)=1, (1,3)=2, (4,6)=3, (5,6)=4,

60、(3,4)=9第第7章章 图图 KruskalKruskal算法（1）按非降序把E中的边排序（2）最小生成树的边集合T置为空（3）当T中边的数量小于n-1 ,做 a.在E 中取下一条边（x,y)； b.若顶点x到y无路径：则将（x,y） 加入T第第7章章 图图 算法实现算法实现 顶点x到y无路径这一问题如何判断？ 解决办法：用并查集（见第用并查集（见第6章章 等价关系求解）等价关系求解）第第7章章 图图 这是一个有6棵树的森林，6个顶点各属一个集合，可用如下并查集表示365421123456123456(1,2)=1, (1,3)=2, (4,6)=3, (5,6)=4, (2,3)=6, (