第7章数据结构 图

1、1第七章第七章 图图F本章主要内容本章主要内容7.1 基本概念和术语基本概念和术语7.2 图的存储结构图的存储结构7.3 图的遍历图的遍历&图的应用图的应用7.4 最小代价生成树最小代价生成树7.5 拓扑排序、关键路径拓扑排序、关键路径7.6 最短路径最短路径27.1 基本术语基本术语 图是顶点集和边集组成的二元组图是顶点集和边集组成的二元组G=,E中每条边是中每条边是V中一对顶点中一对顶点(u,v)间的联系间的联系,如果是无序对，那么称该图如果是无序对，那么称该图为为无向图无向图，否则为，否则为有向图有向图。q完全图、稠密图和稀疏图、子图完全图、稠密图和稀疏图、子图q邻接点邻接点及及

2、关联边关联边邻接点：边的两个顶点互为邻接点邻接点：边的两个顶点互为邻接点关联边：若有边关联边：若有边e= (v, u), e= (v, u), 则称顶点则称顶点v v、u u关联边关联边e ep网网：在图中赋予每条边或弧一定的权值，这种带权的：在图中赋予每条边或弧一定的权值，这种带权的图称为网。图称为网。 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V337.1 基本术语基本术语(续续)q顶点的度、入度和出度顶点的度、入度和出度顶点顶点V V的度的度 = = 与与V V相关联的边的数目相关联的边的数目在有向图中：在有向图中： 顶点顶点V V的出度的出度

3、= = 以以V V为起点有向边数为起点有向边数 顶点顶点V V的入度的入度 = = 以以V V为终点有向边数为终点有向边数 顶点顶点V V的度的度 = V= V的出度的出度+V+V的入度的入度设图设图G G的顶点数为的顶点数为n n，边数为，边数为e e 图的所有顶点的度数之和图的所有顶点的度数之和 = 2= 2* *e e （每条边对图的所有顶点的度数和（每条边对图的所有顶点的度数和“贡献贡献”2 2度度） V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V347.1 基本术语基本术语(续续)q路径、回路路径、回路在图在图G=中，若有中，若有顶点序列顶点序

4、列v v1 1,v,v2 2, , ,v ,vk k, ,且且v E(E(有向图有向图) )或或(v(vi i,v,vi+1i+1) ) E(E(无向图无向图) )，其中其中i=1,2,i=1,2,k-1,v=vk-1,v=v1 1,u=v,u=vk k，则称该序列是从顶，则称该序列是从顶点点v v到顶点到顶点u u的的路径路径；若；若v=uv=u，则称该序列为，则称该序列为回路回路。q简单路径、简单回路简单路径、简单回路在一条路径中在一条路径中, , 除起点和终点外除起点和终点外, ,若其余顶点各若其余顶点各不相同不相同, ,则称该路径为则称该路径为简单路径简单路径。由简单路径组成的回路称为

5、由简单路径组成的回路称为简单回路简单回路。例如在上面的无向图中，例如在上面的无向图中，V0,V1,V2,V3V0,V1,V2,V3是简单路径是简单路径V0,V1,V2,V4,V1V0,V1,V2,V4,V1不是简单路径；在上面的有向图中，不是简单路径；在上面的有向图中，V0,V2,V3,V0V0,V2,V3,V0是简单回路。是简单回路。 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V357.1 基本术语基本术语(续续)q连通图、强连通图连通图、强连通图 在无（有）向图在无（有）向图G=G=中，若对任何两个顶点中，若对任何两个顶点u、v都存都存在从在从u到

6、到v的路径，则称的路径，则称G G是连通图是连通图( (强连通图强连通图) )。(b)(b)非连通图非连通图 V0V0 V1V1 V2V2 V3V3(c)(c)强连通图强连通图(a)(a)连通图连通图V0V0V3V3V2V2V1V1V4V4V5V5(d)(d)非强连通图非强连通图 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V367.1 基本术语基本术语(续续)q连通分量、强连通图分量连通分量、强连通图分量 在无（有）向图在无（有）向图G=G=中，若对任何两个顶点中，若对任何两个顶点u、v都存都存在从在从u到到v的路径，则称的路径，则称G G是连通图是连

7、通图( (强连通图强连通图) )。无（有）向。无（有）向图的极大连通子图称为图的连通分量（强连通分量）图的极大连通子图称为图的连通分量（强连通分量）非连通图，有两个连通分量非连通图，有两个连通分量 V0V0 V1V1 V2V2 V3V3非强连通图非强连通图 V0V0 V1V1 V2V2 V3V3有两个强连通分量有两个强连通分量V0V0V3V3V2V2V1V1V4V4V5V577.1 基本术语基本术语(续续)q生成树生成树一个连通图的生成树是一个一个连通图的生成树是一个极小极小连通子图，它含有图中全连通子图，它含有图中全部顶点，但只有足以构成一棵树的部顶点，但只有足以构成一棵树的n-1n-1条边

8、。条边。(a)(a)连通图连通图G1G1 V0V0 V4V4 V3V3 V1V1 V2V2(b)(b)连通图连通图G1G1的一个生成树的一个生成树 V0V0 V4V4 V3V3 V1V1 V2V287.1 基本术语基本术语(续续)：无向图及其生成树：无向图及其生成树V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5无向图G97.1 基本术语基本术语(续续)：赋权图：赋权图54613241510215203041010107.1 基本术语基本术语(续续)：有向图的强连通子图：有向图的强连通子图5461324151021520304101013241522054611 例例1

9、 1 交通图（公路、铁路）交通图（公路、铁路） 顶点：地点顶点：地点 边：连接地点的公路边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示交通图中的有单行道双行道，分别用有向边、无向边表示；图的应用示例图的应用示例 例例2 2 电路图电路图 顶点：元件顶点：元件 边：连接元件之间的线路边：连接元件之间的线路 例例3 3 通讯线路图通讯线路图 顶点：地点顶点：地点 边：地点间的连线边：地点间的连线 例例4 4 各种流程图各种流程图 如如产品的生产流程图产品的生产流程图 顶点：工序顶点：工序 边：各道工序之间的顺序关系边：各道工序之间的顺序关系 V0V0 V4V4 V3V3 V

10、1V1 V2V2 V0V0 V1V1 V2V2 V3V3127.2 7.2 图的存储结构图的存储结构图的存储结构图的存储结构至少要保存两类信息：至少要保存两类信息： 1)1)顶点的数据顶点的数据 2)2)顶点间的关系顶点间的关系约定约定: : G= G=是图是图, , V= V=v v0 0,v,v1 1,v,v2 2, , v vn-1n-1 , ,设顶点的设顶点的 角标角标为它的编号为它的编号 如何表示顶点间的关系？如何表示顶点间的关系？ V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3137.2.1 7.2.1 图的数组表示法图的数组表示法在数组表

11、示法中，在数组表示法中，用邻接矩阵表示顶点间的关系用邻接矩阵表示顶点间的关系Aij=Aij=1 1 顶点顶点v vi i与与v vj j间有边间有边( (弧弧) )0 0 顶点顶点v vi i与与v vj j间无边间无边( (弧弧) )0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 12 20 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 V2V

12、2 V3V3147.2.1(7.2.1(续续) )数组表示法的类型定义数组表示法的类型定义#define MaxVnum 50typedef double AdjMatrixMaxVnumMaxVnum; typedef struct VertexType vexsMaxVnum; /顶点向量顶点向量 AdjMatrix arcs; /邻接矩阵邻接矩阵 int vexnum,arcnum; /图的当前顶点数和边数图的当前顶点数和边数Graph;Graph G;151 1）无向图的邻接矩阵是无向图的邻接矩阵是对称矩阵对称矩阵，同一条边表示了两次；，同一条边表示了两次；2）顶点顶点v的度：等于二维

13、数组对应行（或列）中值为的度：等于二维数组对应行（或列）中值为1的元素个数；的元素个数；3 3）判断两顶点判断两顶点v v、u u是否为邻接点：只需判二维数组对应分量是否为是否为邻接点：只需判二维数组对应分量是否为1 14 4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1 1或清或清0 0；5 5）设图的顶点数为设图的顶点数为 n ,n ,用有用有n n个元素的一维数组存储图的顶点个元素的一维数组存储图的顶点, ,用邻接用邻接矩阵表示边矩阵表示边, ,则则G G占用的存储空间为：占用的存储空间为：n+nn+n2 2；图的图的

14、存储空间占用量只与存储空间占用量只与它的顶点数有关它的顶点数有关，与边数无关；适用于边稠密的图；，与边数无关；适用于边稠密的图；0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 12 20 1 0 00 1 0 00 1 1 0 00 1 1 0 07.2.1(7.2.1(续续) )数组表示法的特点数组表示法的特点 V0V0 V4V4 V3V3 V1V1 V2V2160) 0) 有向图的邻接矩阵不一定是对称的；有向图的邻接矩阵不一定是对称的；1) 顶点顶点v的出度：等于二维数组对应行中值为的出度：等于二维数组对应行中值为1的元素个数；的元素

15、个数；2）顶点顶点v的入度：等于二维数组对应列中值为的入度：等于二维数组对应列中值为1的元素个数；的元素个数；7.2.1(7.2.1(续续) )数组表示法的特点数组表示法的特点0 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 0 V0V0 V1V1 V2V2 V3V3177.2.1(7.2.1(续续) ) 网的数组表示法网的数组表示法8273496221V32V2V4V1V6V5 8 7 4 9 8 2 1 2 3 2 7 1 3 2 4 2 6 9 2 2 6 1234561 2 3 4 5 6187.2.2 7.2.2 图的邻接表存

16、储结构图的邻接表存储结构例例 V0V0 V4V4 V3V3 V1V1 V2V2下标下标v01v1v2v3v43 024 134 02 12 01234v在邻接表表示法中在邻接表表示法中顶点顶点：通常按编号顺序将顶点数据存储在一维数组中：通常按编号顺序将顶点数据存储在一维数组中关联同一顶点的关联同一顶点的边边：用线性链表存储：用线性链表存储该结点表示边（该结点表示边（V0,V1V0,V1）, ,其中的其中的1 1是是V1V1的序号，即的序号，即一维数组中的下标。一维数组中的下标。197.2.2(7.2.2(续续) ) 网的邻接链表表示网的邻接链表表示8273496221V32V2V4V1V6V5

17、表头顶点的表头顶点的邻接顶点编号邻接顶点编号和边相关和边相关的信息的信息指向下一个指向下一个邻接顶点的指针邻接顶点的指针(a) 表结点结构表结点结构(c) 邻接链表邻接链表12345628546947183241225262431721336214663219425632V1V2V3V4V5V6顶点数据顶点数据指向第一个指向第一个邻接顶点的指针邻接顶点的指针(b) 头结点结构头结点结构207.2.2(7.2.2(续续) ) 邻接表的类型定义邻接表的类型定义typedef struct VertexType data; ArcNode *firstarc;AdjListMaxVnum; ;typ

18、edef struct ArcNode int adjvex; double weight; struct ArcNode *nextarc;ArcNode;表头顶点的表头顶点的邻接顶点编号邻接顶点编号和边相关和边相关的信息的信息指向下一个指向下一个邻接顶点的指针邻接顶点的指针(a) 表结点结构表结点结构顶点数据顶点数据指向第一个指向第一个邻接顶点的指针邻接顶点的指针(b) 头结点结构头结点结构217.2.2(7.2.2(续续) ) 图的邻接表表示图的邻接表表示typedef struct VertexType data; ArcNode *firstarc;AdjListMaxVnum; ;

19、 typedef struct ArcNode int adjvex; double weight; struct ArcNode *nextarc;ArcNode;表头顶点的表头顶点的邻接顶点编号邻接顶点编号和边相关和边相关的信息的信息指向下一个指向下一个邻接顶点的指针邻接顶点的指针(a) 表结点结构表结点结构顶点数据顶点数据指向第一个指向第一个邻接顶点的指针邻接顶点的指针(b) 头结点结构头结点结构typedef struct int vexnum,arcnum; AdjList vertices;AGraph; AGraph G; 227.2.2(7.2.2(续续) ) 有向图的邻接表表

20、示有向图的邻接表表示例例下标下标v01v1v2v32 3 0 0123v在邻接表表示中在邻接表表示中顶点顶点：通常按编号顺序将顶点数据存储在一维数组中：通常按编号顺序将顶点数据存储在一维数组中以同一顶点为以同一顶点为起点起点的弧的弧：用线性链表存储：用线性链表存储 V0V0 V1V1 V2V2 V3V3237.2.2(7.2.2(续续) )有向图的逆邻接表表示有向图的逆邻接表表示例例v在逆邻接表表示中在逆邻接表表示中顶点顶点：通常按编号顺序将顶点数据存储在一维数组中：通常按编号顺序将顶点数据存储在一维数组中以同一顶点为以同一顶点为终点终点的弧的弧：用线性链表存储：用线性链表存储 V0V0 V1

21、V1 V2V2 V3V3下标下标v0v1v2v33 0 2 01230 247.2.3 7.2.3 有向图的十字链表表示有向图的十字链表表示v将有向图的邻接表和逆邻接表结合起来得到的链表。将有向图的邻接表和逆邻接表结合起来得到的链表。v在十字链表中，在十字链表中，顶点结点顶点结点存储数据元素，存储数据元素，弧结点弧结点存储弧及其上的信息。存储弧及其上的信息。 V0V0 V1V1 V2V2 V3V3v0v1v2v30012310 22 030313223邻接链表邻接链表tailvex headvexhlinktlinkinfo弧结点弧结点datafirstinfirstout顶点结点顶点结点25

22、7.2.3(7.2.3(续续) )有向图的十字链表表示有向图的十字链表表示v0v1v2v30012310 22 030313223逆邻接链表逆邻接链表 V0V0 V1V1 V2V2 V3V3v将有向图的邻接表和逆邻接表结合起来得到的链表。将有向图的邻接表和逆邻接表结合起来得到的链表。v在十字链表中，在十字链表中，顶点结点顶点结点存储数据元素，存储数据元素，弧结点弧结点存储弧及其上的信息。存储弧及其上的信息。267.2.3(7.2.3(续续) )有向图的十字链表表示有向图的十字链表表示v0v1v2v30012310 22 030313223十字链表十字链表 V0V0 V1V1 V2V2 V3V3

23、v将有向图的邻接表和逆邻接表结合起来得到的链表。将有向图的邻接表和逆邻接表结合起来得到的链表。v在十字链表中，在十字链表中，顶点结点顶点结点存储数据元素，存储数据元素，弧结点弧结点存储弧及其上的信息。存储弧及其上的信息。277.2.4 7.2.4 无向图的邻接多重表表示无向图的邻接多重表表示v无向图的邻接多重表表示中，无向图的邻接多重表表示中，每条边只表示一次每条边只表示一次。v0v1v2v30123010 3 （v0,v1）（v0,v3） V0V0 V4V4 V3V3 V1V1 V2V221v442341 42 markivexilinkjvexjlink(vi,vj)287.2.4(7.2

24、.4(续续) ) 无向图的邻接多重表表示无向图的邻接多重表表示v无向图的邻接多重表表示中，每条边只表示一次。无向图的邻接多重表表示中，每条边只表示一次。v0v1v2v30123010 3 （v0,v1）（v0,v3） V0V0 V4V4 V3V3 V1V1 V2V221v442341 42 markivexilinkjvexjlink(vi,vj)297.3 图的遍历图的遍历q从图的某个顶点出发，访问图中的所有顶点，且从图的某个顶点出发，访问图中的所有顶点，且使每个顶点仅被访问一次。这一过程叫做图的遍使每个顶点仅被访问一次。这一过程叫做图的遍历。历。q图的遍历操作是求解图的连通性问题、拓扑排序

25、图的遍历操作是求解图的连通性问题、拓扑排序等问题的基础。等问题的基础。q遍历方法遍历方法: :深度优先遍历和广度优先遍历深度优先遍历和广度优先遍历307.3.1 深度优先搜索深度优先搜索(DFS)从顶点从顶点v1出发进行出发进行DFS遍历遍历V3V2V4V1V6V5V8V7V1V2V4V5V8V3V6V7317.3.1(续续) 深度优先搜索深度优先搜索(DFS)q深度优先遍历图的方法是，从图中某顶点深度优先遍历图的方法是，从图中某顶点v v出发：出发： (1)(1)访问顶点访问顶点v v；(2)(2)依次从依次从v v的未被访问的邻接点出发，对图进行的未被访问的邻接点出发，对图进行深度优先遍历

26、；直至图中和深度优先遍历；直至图中和v v有路径相通的顶点有路径相通的顶点都被访问；都被访问；(3)(3)若此时图中尚有顶点未被访问，则从一个未被若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。到图中所有顶点均被访问过为止。327.3.1(续续) 深度优先搜索深度优先搜索(DFS)q深度优先遍历过程是递归的，在遍历过程中，若深度优先遍历过程是递归的，在遍历过程中，若某个顶点的所有邻接顶点均被访问过，则需要回某个顶点的所有邻接顶点均被访问过，则需要回溯。溯。V1V2V4V5V8V3V6V7V1V

27、5V2V4V2V8V1V7V3V3V6337.3.1(续续) 深度优先搜索深度优先搜索(DFS)int visitedMAX; /访问标志数组访问标志数组void DFSTraverse(Graph G) for(v=0;vG.vexnum;+v) visitedv = false; for(v=0;vadjvex=0) DFS(G, p-adjvex); /*若若p-adjvex顶点未访问顶点未访问,递归访问它递归访问它*/ p=p-nextarc; /*p指向顶点指向顶点v的下一条弧的弧头结点的下一条弧的弧头结点*/ 7.3.1(续续) 深度优先搜索深度优先搜索(DFS)357.3.2 广

28、度优先搜索广度优先搜索BFSV3V2V4V1V6V5广度优先遍历广度优先遍历V3V2V4V1V6V5367.3.2(续续) 广度优先搜索广度优先搜索(BFS)从顶点从顶点v1出发进行出发进行BFS遍历遍历V3V2V4V1V6V5V8V7V1V2V4V8V5V3V6V7377.3.2(续续) 广度优先搜索广度优先搜索(BFS)q从图中某顶点从图中某顶点v vi i出发：出发： 访问顶点访问顶点v vi i ； 访问访问v vi i 的所有未被访问的邻接点的所有未被访问的邻接点w w1 1 ,w ,w2 2 , , w wk k ； 依次从这些邻接点（在步骤依次从这些邻接点（在步骤中访问的顶点）出

29、发，中访问的顶点）出发，访问它们的所有未被访问的邻接点访问它们的所有未被访问的邻接点; ; 依此类推，直到依此类推，直到图中所有访问过的顶点的邻接点都被访问；图中所有访问过的顶点的邻接点都被访问；q为实现为实现，需要保存在步骤，需要保存在步骤中访问的顶点，而且中访问的顶点，而且访问这访问这些顶点的些顶点的邻接点邻接点的顺序为：先保存的顶点，其邻接点先被的顺序为：先保存的顶点，其邻接点先被访问。访问。38Void BFSTraverse(ALGraph G) for (v=0; vG.vexnum; +v) visitedv = FALSE ; InitQueue(Q); for(v=0; va

30、djvex) visitedp-adjvex=1; printf(%d , p-adjvex); EnQueue(Q, p-adjvex); /if p=p-nextarc; /while(p) /while(!Queue) /if(!visite) /for V3V2V4V1V6V5V8V739算法分析算法分析n图中每个顶点至多入队一次，因此外循环次数为图中每个顶点至多入队一次，因此外循环次数为n。n当图当图G采用邻接表方式存储，则当结点采用邻接表方式存储，则当结点v出队后，内循环出队后，内循环次数等于结点次数等于结点v的度。由于访问所有顶点的邻接点的总的的度。由于访问所有顶点的邻接点的总的

31、时间复杂度为时间复杂度为O(d0+d1+d2+dn-1)=O(e)， 因此图因此图采用邻接表方式存储，广度优先搜索算法的时间复杂度为采用邻接表方式存储，广度优先搜索算法的时间复杂度为O(n+e)；n当图当图G采用邻接矩阵方式存储，由于找每个顶点的邻接点采用邻接矩阵方式存储，由于找每个顶点的邻接点时，内循环次数等于时，内循环次数等于n，因此广度优先搜索算法的时间复，因此广度优先搜索算法的时间复杂度为杂度为O(n2)。 407.4 图的连通性图的连通性q利用图的遍历运算求解图的连通性问题利用图的遍历运算求解图的连通性问题F无向图是否连通、有几个连通分量，求解无向无向图是否连通、有几个连通分量，求解

32、无向图的所有连通分量图的所有连通分量深度优先生成树、生成森林深度优先生成树、生成森林广度优先生成树、生成森林广度优先生成树、生成森林F有向图是否是强连通、求解其强连通分量有向图是否是强连通、求解其强连通分量q求无向网的最小代价生成树求无向网的最小代价生成树41回顾：无向图及其生成树回顾：无向图及其生成树V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5无向图G427.4.3 最小代价生成树最小代价生成树q生成树的代价等于其边上的权值之和。生成树的代价等于其边上的权值之和。V4V1V3V2V6V56512665534V4V1V3V2V6V561654V4V1V3V2V6V5

33、1253443普里姆普里姆(Prim)算法算法q假设假设N=(VN=(V，E)E)是连通网，是连通网，TETE是是N N上最小生成树中边的集上最小生成树中边的集合。合。q算法从算法从U=uU=u0 0(u(u0 0V)V)，TE=TE=开始，重复执行下述操开始，重复执行下述操作：作：F在所有在所有uUuU，vV-UvV-U的边的边(u(u，v)v)中找一条代价最小中找一条代价最小的边的边(u(u0 0 ,v,v0 0),),将其并入集合将其并入集合TETE，同时将，同时将v v0 0并入并入U U集合集合F当当U=VU=V则结束，此时则结束，此时TETE中必有中必有n-1n-1条边，则条边，则

34、T=(VT=(V，TE)TE)为为N的最小生成树。的最小生成树。q普里姆算法构造最小生成树的过程是从一个顶点普里姆算法构造最小生成树的过程是从一个顶点U=uU=u0 0 作初态，不断寻找与作初态，不断寻找与U U中顶点相邻且代价最小的边的另中顶点相邻且代价最小的边的另一个顶点，扩充到一个顶点，扩充到U U集合直至集合直至U=VU=V为止。为止。44最小代价生成树最小代价生成树q普里姆算法求最小生成树普里姆算法求最小生成树V4V1V3V2V6V56512665534V4V1V3V2V6V512534UV-UV1 V2 ,V3 ,V4 , V5 ,V6 步骤步骤(0)V1 ,V3 V2 ,V4 ,

35、 V5 ,V6 (1)V1 ,V3 ,V6 V2 ,V4 , V5 (2)V1 ,V3 ,V6 ,V4 V2, V5 (3)V1 ,V3 ,V6 ,V4 ,V2 V5 (4)V1 ,V3 ,V6 ,V4 ,V2 ,V5 (5)45V4V1V3V2V6V5165V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步骤步骤(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5UV-U最小代价生成树最小代价生成树q普里姆算法求最小生成树普里姆算法求最小生成树46V4V1V3V2V6V565V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步骤步骤(0)V1 ,V3

36、V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)46554UV-U最小代价生成树最小代价生成树q普里姆算法求最小生成树普里姆算法求最小生成树47V4V1V3V2V6V565V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步骤步骤(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)4655V1 ,V3 ,V6 ,V4 V2, V5 (3)262UV-U最小代价生成树最小代价生成树q普里姆算法求最小生成树普里姆算法求最小生成树48V4V1V3V2V6V56V4V1

37、V31V1 V2 ,V3 ,V4 , V5 ,V6 步骤步骤(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)465V1 ,V3 ,V6 ,V4 V2, V5 (3)62V1 ,V3 ,V6 ,V4 ,V2 V5 (4)5UV-U最小代价生成树最小代价生成树q普里姆算法求最小生成树普里姆算法求最小生成树49V4V1V3V2V6V5V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步骤步骤(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)46V

38、1 ,V3 ,V6 ,V4 V2, V5 (3)62V1 ,V3 ,V6 ,V4 ,V2 V5 (4)5V1 ,V3 ,V6 ,V4 ,V2 ,V5 (5)33UV-U最小代价生成树最小代价生成树q普里姆算法求最小生成树普里姆算法求最小生成树50V4V1V3V2V6V5V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步骤步骤(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)4V1 ,V3 ,V6 ,V4 V2, V5 (3)2V1 ,V3 ,V6 ,V4 ,V2 V5 (4)5V1 ,V3 ,V6 ,V4 ,V

39、2 ,V5 (5)3UV-U最小代价生成树最小代价生成树q普里姆算法求最小生成树普里姆算法求最小生成树51Prim算法的实现算法的实现q顶点集合如何表示？顶点集合如何表示？q最小边如何选择？最小边如何选择？q一个顶点加入一个顶点加入U U集合如何表示？集合如何表示？structstruct int adjvex int adjvex; ; double lowcost double lowcost; ;closedgeMAX_VERTEX_NUMclosedgeMAX_VERTEX_NUM;closedgei.adjvex=kclosedgei.lowcost=0顶点顶点i与顶点与顶点k邻接邻

40、接顶点顶点k已经在已经在U集合中集合中顶点顶点i加入加入U集合时集合时52adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v6323456UV-Uk 顶点顶点iclosedgeclosedge2.adjvex=1 closedge2. lowcost=6closedge3.adjvex=1closedge3. lowcost=1closedge4.adjvex=1closedge4. lowcost=5V4V1V3V2V6V5165U集合的成员集合的成员：V-U集合的成员：集合的成员：q当当U集合中加入一个新顶点时，集合中加入一个新顶点时，V-U集合集合中的顶点到中的

41、顶点到U的最小代价边可能会更新的最小代价边可能会更新53adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v6623456UV-Uk 顶点顶点iclosedgeV4V1V3V2V6V55564U集合的成员集合的成员：V-U集合的成员：集合的成员：q当当U集合中加入一个新顶点时，集合中加入一个新顶点时，V-U集合集合中的顶点到中的顶点到U的最小代价边可能会更新的最小代价边可能会更新54adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v63adjvexlowcos

42、tv350v15v36v34v1,v3v2,v4,v5,v66adjvexlowcostv350v62v360v1,v3,v6v2,v4,v5 423456UV-Uk 顶点顶点iclosedgeV4V1V3V2V6V5562U集合的成员集合的成员：V-U集合的成员：集合的成员：q当当U集合中加入一个新顶点时，集合中加入一个新顶点时，V-U集合集合中的顶点到中的顶点到U的最小代价边可能会更新的最小代价边可能会更新55adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66adjvexlo

43、wcostv350v62v360v1,v3,v6v2,v4,v5 4adjvexlowcostv3500v360v1,v3,v6,v4v2,v5 23456UV-Uk 顶点顶点iclosedge2V4V1V3V2V6V556U集合的成员集合的成员：V-U集合的成员：集合的成员：q当当U集合中加入一个新顶点时，集合中加入一个新顶点时，V-U集合集合中的顶点到中的顶点到U的最小代价边可能会更新的最小代价边可能会更新56adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66adjvexlo

44、wcostv350v62v360v1,v3,v6v2,v4,v5 4adjvexlowcostv3500v360v1,v3,v6,v4v2,v5 2adjvexlowcost000v230v1,v3,v6,v4,v2v5 23456UV-Uk 顶点顶点iclosedge5V4V1V3V2V6V53U集合的成员集合的成员：V-U集合的成员：集合的成员：q当当U集合中加入一个新顶点时，集合中加入一个新顶点时，V-U集合集合中的顶点到中的顶点到U的最小代价边可能会更新的最小代价边可能会更新57adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v63adjvexlowcostv

45、350v15v36v34v1,v3v2,v4,v5,v66adjvexlowcostv350v62v360v1,v3,v6v2,v4,v5 4adjvexlowcostv3500v360v1,v3,v6,v4v2,v5 223456UV-Uk 顶点顶点iclosedgeV4V1V3V2V6V5adjvexlowcost00000v1,v3,v6,v4,v2,v5 adjvexlowcost000v230v1,v3,v6,v4,v2v5 514253U集合的成员集合的成员：V-U集合的成员：集合的成员：58void MiniSpanTree_PRIM (Graph G, VertexType u

46、) /用普里姆算法从顶点用普里姆算法从顶点u u出发构造出发构造G G的最小生成树的最小生成树 for(j = 0; j G.vexnum; +j) /辅助数组初始化辅助数组初始化 if ( j != u ) closedgej = u, G.arcsuj;struct int adjvex; double lowcost;closedgeMAX_VERTEX_NUM; closedgeu.lowcost = 0; /初始初始,U=u,U=u for(i = 1; i G.vexnum; +i) k = minimum(closedge); /求生成树的下一个顶点求生成树的下一个顶点k k c

47、out closedgek.adjvex G.vexsk; closedgek.lowcost = 0; for(j = 0; j G.vexnum; +j) if (G.arcskj.adj 0, vi v-u cout closedgek.adjvex G.vexsk; /输出生成树的边输出生成树的边 closedgek.lowcost = 0; /顶点顶点k k并入并入U U集合集合 for(j = 0; j G.vexnum; +j) if (G.arcskj closedgej.lowcost) closedgej = k, G.arcskj; 算法的时间复杂度为：算法的时间复杂度为

48、：O(nO(n2 2) )59克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法q假设连通网假设连通网N=(VN=(V，E)E)，则令最小生成树的初始状态为只有，则令最小生成树的初始状态为只有n n个顶点而无边的非连通图个顶点而无边的非连通图T=(VT=(V，)，图中每个顶点自成一，图中每个顶点自成一个连通分量。个连通分量。q在在E E中选择代价最小的边，若该边依附的顶点落在中选择代价最小的边，若该边依附的顶点落在T T中不同中不同的连通分量上，则将此边加入到的连通分量上，则将此边加入到T T中，否则舍去此边而选择中，否则舍去此边而选择下一条代价最小的边。依次类推，直至下一条代价最小的边。依次类推

49、，直至T T中所有顶点都在同中所有顶点都在同一连通分量上为止。一连通分量上为止。60最小代价生成树最小代价生成树q克鲁斯卡尔算法求最小生成树克鲁斯卡尔算法求最小生成树V4V1V3V2V6V56512665534V4V1V3V2V6V5123461q克鲁斯卡尔算法求最小生成树克鲁斯卡尔算法求最小生成树V4V1V3V2V6V56512665534V4V1V3V2V6V512345V V3 3、V V4 4依附在同依附在同一个连通分量一个连通分量最小代价生成树最小代价生成树62q克鲁斯卡尔算法求最小生成树克鲁斯卡尔算法求最小生成树V4V1V3V2V6V56512665534V4V1V3V2V6V51

50、234V V1 1、V V4 4依附在同依附在同一个连通分量一个连通分量5最小代价生成树最小代价生成树63q克鲁斯卡尔算法求最小生成树克鲁斯卡尔算法求最小生成树V4V1V3V2V6V56512665534V4V1V3V2V6V512534最小代价生成树最小代价生成树64克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法q从上述过程可知，实现从上述过程可知，实现克鲁斯卡尔克鲁斯卡尔(Kruskal)算法时，算法时，要解决以下两个问题：要解决以下两个问题：如何选择代价最小的边；如何选择代价最小的边；如何判定边所关联的两个顶点是否在同一个连通如何判定边所关联的两个顶点是否在同一个连通分量中分量中657.

51、5 有向无环图有向无环图DAG*a+b+dcdc表达式：表达式：a+b(c+d) (c+d)(a) 表达式树*a+bdc(b) DAG图667.5(续续) 有向无环图及应用有向无环图及应用nAOV网、AOE网n拓扑排序n关键路径67例例 某工程可分为某工程可分为7 7个子工个子工程，若用程，若用顶点表示子工程（顶点表示子工程（也称活动），也称活动）， 用用弧表示子弧表示子工程间的顺序关系，工程间的顺序关系，工程的工程的施工流程可用如右的施工流程可用如右的AOVAOV网网表示。表示。q AOVAOV网网(Activity On Vertex net )(Activity On Vertex ne

52、t )F用顶点表示用顶点表示活动活动，边表示边表示活动的顺序关系活动的顺序关系的有向图称的有向图称为为AOVAOV网网( (顶点表示活动的网顶点表示活动的网).).应用：应用： 工程流程、生产过程中各道工序的流程等工程流程、生产过程中各道工序的流程等 V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V67.5(续续) 有向无环图及应用有向无环图及应用68q 对工程问题，人们至少会关心如下两类问题：对工程问题，人们至少会关心如下两类问题：1)1) 工程能否顺序进行，即工程流程是否工程能否顺序进行，即工程流程是否“合理合理”2)2) 完成整项工程至少需要多少时间，哪些子工程是影响完

53、成整项工程至少需要多少时间，哪些子工程是影响工程进度的关键子工程工程进度的关键子工程q 为求解工程流程是否为求解工程流程是否“合理合理”，通常用，通常用AOVAOV网表示工程流网表示工程流程程 V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V6 某工程可分为某工程可分为7 7个子工程个子工程(V0(V0、V1V1、V2V2、V3V3、V4V4、V5V5、V6)V6)，若用，若用顶点表示子工程（顶点表示子工程（也称活动），也称活动）， 用用弧表示子工弧表示子工程间的顺序关系，程间的顺序关系，工程流程工程流程可用如右的可用如右的AOVAOV网表示。网表示。例例7.5(续续) 有向

54、无环图及应用有向无环图及应用69c4c1c2c3c12c9c10c11c6c7c8c5课程编号课程编号课程名称课程名称先修课程先修课程c1程序设计基础程序设计基础无无c2离散数学离散数学c1c3数据结构数据结构c1, c2c4汇编语言汇编语言c1c5算法设计与分析算法设计与分析c3, c4c6计算机体系结构计算机体系结构c11c7编译原理编译原理c3, c5c8操作系统原理操作系统原理c3, c6c9高等数学高等数学无无c10线性代数线性代数c9c11普通物理普通物理c9c12数值分析数值分析c1 , c9, c107.5(续续) 有向无环图及应用有向无环图及应用如何安排施工计划？如何安排施工

55、计划？如何安排教学计划？如何安排教学计划？70q 一个可行的施工计划：一个可行的施工计划： V0, V1, V2, V4, V3, V6, V5q 一个可行的学习计划为：一个可行的学习计划为：C1, C9, C4, C2, C10, C11, C12, C3, C6, C5, C7, C8q 特点：特点：若在有向图中有弧若在有向图中有弧，则称顶点，则称顶点v是顶点是顶点u 的前趋，那的前趋，那么施工计划中顶点么施工计划中顶点v 也排在也排在u之前。也称之前。也称u是是v的后继。的后继。c4c1c2c3c12c9c10c11c6c7c8c5 V5V5 V3V3 V2V2 V0V0 V1V1 V4

56、V4 V6V671q 特点：特点：若在有向图中有弧若在有向图中有弧，则称顶点，则称顶点v是顶点是顶点u 的前趋，那么的前趋，那么施工计划中顶点施工计划中顶点v 也排在也排在u之前。也之前。也称称u是是v的后继。的后继。q 一个一个AOV网不应该存在环，因为网不应该存在环，因为存在环意味着某项活动的进行应该存在环意味着某项活动的进行应该以本活动的完成作为先决条件，这以本活动的完成作为先决条件，这肯定是荒谬的。肯定是荒谬的。c4c1c2c3c12c9c10c11c6c7c8c57.5.1 7.5.1 拓扑排序拓扑排序72q拓扑排序拓扑排序： 将有向图中的顶点排成将有向图中的顶点排成一个序列。一个序

57、列。q拓扑序列拓扑序列：有向图有向图D的一个顶点序的一个顶点序列称作一个拓扑序列。如果该序列中任列称作一个拓扑序列。如果该序列中任两顶点两顶点v 、u ，若在，若在D中中v是是u前趋，则在前趋，则在序列中序列中v也是也是u前趋前趋。c4c1c2c3c12c9c10c11c6c7c8c57.5.1(续续) 拓扑排序拓扑排序73q 拓扑排序方法：拓扑排序方法：1)在在有向图中选一个无前趋的顶点有向图中选一个无前趋的顶点v，输出之；，输出之；2)从有向图中删除从有向图中删除v及以及以v为尾的弧；为尾的弧；3)重复重复1)、2)，直接全部输出全部顶点或有向图中不存在无前趋的结点，直接全部输出全部顶点或

58、有向图中不存在无前趋的结点时为止。时为止。如何在计算机上实现如何在计算机上实现对有向图的拓扑排序？对有向图的拓扑排序？7.5.1(7.5.1(续续) ) 拓扑排序拓扑排序 V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V674q 拓扑排序方法：拓扑排序方法：1)在有向图中选一个无前趋的顶点在有向图中选一个无前趋的顶点v，输出之；，输出之；2)从有向图中删除从有向图中删除v及以及以v为尾的弧；为尾的弧；3)重复重复1)、2)，直接全部输出全部顶点或有向图中不存在无前趋的结点，直接全部输出全部顶点或有向图中不存在无前趋的结点时为止。时为止。 V5V5 V3V3 V2V2 V0V0

59、 V1V1 V4V4 V6V6V0V07.5.1(续续) 拓扑排序拓扑排序75q 拓扑排序方法：拓扑排序方法：1)在在有向图中选一个无前趋的顶点有向图中选一个无前趋的顶点v，输出之；，输出之；2)从有向图中删除从有向图中删除v及以及以v为尾的弧；为尾的弧；3)重复重复1)、2)，直接全部输出全部顶点或有向图中不存在无前趋的结点，直接全部输出全部顶点或有向图中不存在无前趋的结点时为止。时为止。 V5V5 V3V3 V2V2 V1V1 V4V4 V6V6V0V07.5.1(续续) 拓扑排序拓扑排序76q 拓扑排序方法：拓扑排序方法：1)在有向图中选一个无前趋的顶点在有向图中选一个无前趋的顶点v，输

60、出之；，输出之；2)从有向图中删除从有向图中删除v及以及以v为尾的弧；为尾的弧；3)重复重复1)、2)，直接全部输出全部顶点或有向图中不存在无前趋的结点，直接全部输出全部顶点或有向图中不存在无前趋的结点时为止。时为止。 V5V5 V3V3 V2V2 V1V1 V4V4 V6V6V0V0 V1V17.5.1(续续) 拓扑排序拓扑排序77q 拓扑排序方法：拓扑排序方法：1)在在有向图中选一个无前趋的顶点有向图中选一个无前趋的顶点v，输出之；，输出之；2)从有向图中删除从有向图中删除v及以及以v为尾的弧；为尾的弧；3)重复重复1)、2)，直接全部输出全部顶点或有向图中不存在无前趋的结点，直接全部输出全部顶点