数据结构——第7章图和广义表1ppt课件

1、数据结构的内容数据结构的内容图的特点图的特点 顶点的前驱和后继个数无限制顶点的前驱和后继个数无限制 图的应用图的应用顶点之间的关系是任意的顶点之间的关系是任意的 图中任意两个顶点之间都可能相关图中任意两个顶点之间都可能相关 图图Graph是一种非线性结构。是一种非线性结构。 语语 言言 学学逻逻 辑辑 学学物物 理理化化 学学电信工程电信工程 数数 学学 北京北京 西安西安 南京南京 杭州杭州 开封开封 洛阳洛阳 7.1 7.1 基本术语基本术语7.2 7.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 连通网的最小生成树连通网的最小生成树7.5 7.5 单源最短路径单源最

2、短路径7.6 7.6 拓朴排序拓朴排序7.7 7.7 关键路径关键路径7.8 7.8 广义表广义表图：记为图：记为 G G( V, E ) ( V, E ) 其中：其中：V V 是是G G的顶点集合，是有穷非空集；的顶点集合，是有穷非空集；E E 是是G G的边集合，是有穷集。的边集合，是有穷集。问：当问：当E(G)E(G)为空时，图为空时，图G G存在否？存在否？答：还存在！但此时图答：还存在！但此时图G G只有顶点而没有边。只有顶点而没有边。有向图：有向图：无向图：无向图：完全图：完全图：图图G G中的每条边都是有方向的；中的每条边都是有方向的；图图G G中的每条边都是无方向的；中的每条边

3、都是无方向的；图图G G任意两个顶点都有一条边相连接；任意两个顶点都有一条边相连接；V=vertex E=edge例：判断下列例：判断下列4种图形各属什么类型？种图形各属什么类型？无向图无向图 无向图无向图(树树)有向图有向图有向图有向图 完全图完全图 完全图完全图设有两个图设有两个图 G(V, E) 和和 G(V, E)。假设。假设 V V 且且 E E, 则称则称 图图G 是是 图图G 的子图。的子图。子子 图：图：带权图：带权图：即边上带权的图。其中权是指每条边可以标上即边上带权的图。其中权是指每条边可以标上具有某种含义的数值即与边相关的数）。具有某种含义的数值即与边相关的数）。带权图带

4、权的有向图与无向图） 网网 络：络：顶点顶点v v的度是与它相关联的边的条数。记作的度是与它相关联的边的条数。记作TD(v)TD(v)。在有向图中在有向图中, , 顶点的度等于该顶点的入度与出度之和。顶点的度等于该顶点的入度与出度之和。顶点顶点 v v 的入度是以的入度是以 v v 为终点的有向边的条数为终点的有向边的条数, , 记作记作 ID(v);ID(v); 顶点顶点 v v 的出度是以的出度是以 v v 为始点的有向边的条数为始点的有向边的条数, , 记作记作 OD(v)OD(v)。问：当有向图中仅问：当有向图中仅1 1个顶点的入度为个顶点的入度为0,0,其余顶点的其余顶点的入度均为入

5、度均为1 1，此时是何形状？，此时是何形状？答：是树！而且是一棵有向树！答：是树！而且是一棵有向树！ 度度入度入度出度出度简单路径：路径上各顶点路径上各顶点 v1,v2,.,vm v1,v2,.,vm 均不互相重复。均不互相重复。回 路：例：例：若路径上第一个顶点若路径上第一个顶点 v1 v1 与最后一个顶点与最后一个顶点vm vm 重合，重合，则称这样的路径为回路或环。则称这样的路径为回路或环。途径：路径长度：强连通图：连通图：生成树：生成树：生成森生成森林：林：图的特点：非线性结构图的特点：非线性结构m :n m :n ） 邻接表邻接表 邻接多重表邻接多重表 十字链表十字链表设计为邻接矩阵

6、设计为邻接矩阵链式存储结构：链式存储结构：顺序存储结构：顺序存储结构： 无！无！（多个顶点，无序可言）（多个顶点，无序可言）但可用数组描述元素间关系。但可用数组描述元素间关系。可用多重链表可用多重链表重点介绍：重点介绍： , ),( , ,否否则则或或者者如如果果01AEjiEjijiv1v2v3v5v4v4G邻接矩阵：A =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 1

7、0 1 0 1 11 0 1 0 10 1 1 1 0顶点表：例例2 ：有向图的邻接矩阵：有向图的邻接矩阵素之和素之和, ,即：即：TD(Vi)=OD( Vi ) + ID( Vi )TD(Vi)=OD( Vi ) + ID( Vi )v1v2v3v4邻接矩阵：A=( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：在有向图的邻接矩阵中，注：在有向图的邻接矩阵中， 第第i i行含义：以结点行含义：以结点vivi为尾的弧为尾的弧( (即出度边）；即出度边）； 第第i i列含义：以结点列含义：以结点vivi为头的弧为头的弧( (即入度边）

8、。即入度边）。顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 容易实现图的操作，如：求某顶点的度、判断容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边弧）、顶点的邻接点等等。顶点之间是否有边弧）、顶点的邻接点等等。 n n个顶点需要个顶点需要n n* *n n个单元存储边个单元存储边( (弧弧););空间效率空间效率为为O(n2)O(n2)。 对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。特别讨论特别讨论 ： 网即有权图的邻接矩阵网即有权图的邻接矩阵定义为：定义为： A i j =Wij 或或vi

9、, vj）VR 无边弧）无边弧）v1v2v3v4Nv5v65489755613以有向网为例：以有向网为例：邻接矩阵： N =( v1 v2 v3 v4 v5 v6 )邻接矩阵法优点：邻接矩阵法优点：邻接矩阵法缺点：邻接矩阵法缺点：顶点表： 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 数据结构数据结构 第七章第七章 图和广义表图和广义表韶关学院数信学院韶关学院数信学院图的数组邻接矩阵存储表示：图的数组邻接矩阵存储表示： #define INFINITY INT_MAX / 最大值最大值 #define MAX_VERTEX_NUM 20 / 最大顶点个数最大顶

10、点个数 typedef enum DG, DN, AG, AN GraphKind; /有向图有向图,有向网有向网,无向图无向图,无向网无向网 typedef struct ArcCell VRType adj; / VRType是顶点关系类型。对无权图用是顶点关系类型。对无权图用1或或0表示相邻否；表示相邻否； / 对带权图，则为权值类型。对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vexs

11、MAX_VERTEX_NUM; / 顶点向量顶点向量 AdjMatrix arcs; / 邻接矩阵邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧图的当前顶点数和弧(边边)数数 GraphKind kind; / 图的种类标志图的种类标志 MGraph; 数据结构数据结构 第七章第七章 图和广义表图和广义表韶关学院数信学院韶关学院数信学院7.2.2 图的邻接表存储表示法（图的邻接表存储表示法（ 链式存储链式存储 ） 头结点头结点 data firstarc 表结点表结点 adjvex nextarc info v2 v1 v3 v4 v5 G2 v1 v3 v4 v2

12、v5 0 1 2 3 4 3 1 4 2 0 4 3 1 2 0 2 1 特点：特点： 若无向图中有若无向图中有 n 个顶点、个顶点、e 条边，则其邻接表需条边，则其邻接表需 n 个头个头 结点和结点和 2e 个表结点。适宜存储稀疏图。个表结点。适宜存储稀疏图。 无向图中顶点无向图中顶点 vi 的度为第的度为第 i 个单链表中的结点数。个单链表中的结点数。 数据结构数据结构 第七章第七章 图和广义表图和广义表韶关学院数信学院韶关学院数信学院v2 v1 v3 v4 G1 0 1 2 3 2 1 3 0 v1 v3 v4 v2 0 1 2 3 3 0 2 v1 v3 v4 v2 0 邻接表邻接表

13、逆邻接表逆邻接表 顶点顶点 vi 的出度为第的出度为第 i 个个 单链表中的结点个数。单链表中的结点个数。 特点：特点： 顶点顶点 vi 的入度为整个单的入度为整个单 链表中邻接点域值是链表中邻接点域值是 i-1 的结点个数。的结点个数。 找出度易，找出度易， 找入度难。找入度难。 找入度易，找入度易， 找出度难。找出度难。 顶点顶点 vi 的入度为第的入度为第 i 个个 单链表中的结点个数。单链表中的结点个数。 顶点顶点 vi 的出度为整个单的出度为整个单 链表中邻接点域值是链表中邻接点域值是 i-1 的结点个数。的结点个数。 数据结构数据结构 第七章第七章 图和广义表图和广义表韶关学院数信

14、学院韶关学院数信学院图的邻接表存储表示：图的邻接表存储表示： #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针该弧相关信息的指针 ArcNode; typedef struct VNode VertexType data; / 顶点信息顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧指向第一条依附该顶

15、点的弧 VNode, AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数图的当前顶点数和弧数 int kind; / 图的种类标志图的种类标志 ALGraph; v1v2v3v5v4v4v1v2v3v4V4V3V2V12301邻接表邻接表(出边出边)V4V3V2V13020逆邻接表逆邻接表(入边入边)邻接表邻接表4321013341420v5v4v3v2v1231420当邻接表的存储当邻接表的存储结构形成后，图结构形成后，图便唯一确定！便唯一确定！分析分析1: 对于对于

16、n个顶点个顶点e条边的无向图，邻接表中除了条边的无向图，邻接表中除了n个头结点外，个头结点外，只有只有2e个表结点个表结点,空间效率为空间效率为O(n+2e)。若是稀疏图若是稀疏图(en2)，则比邻接矩阵表示法，则比邻接矩阵表示法O(n2)省空间。省空间。邻接表存储法的特点：邻接表存储法的特点：分析分析2:在有向图中，邻接表中除了在有向图中，邻接表中除了n个头结点外，只有个头结点外，只有e个表结点个表结点,空间效率为空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。若是稀疏图，则比邻接矩阵表示法合适。它其实是对邻接矩阵法的一种改进它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？

17、怎样计算无向图顶点的度？邻接表的缺点：邻接表的缺点：怎样计算有向图顶点的出度？怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点的入度？怎样计算有向图顶点怎样计算有向图顶点Vi的度：的度：需遍历全表需遍历全表邻接表的优点：邻接表的优点：TD(Vi)=TD(Vi)=单链表中链接的结点个数单链表中链接的结点个数OD(Vi)单链出边表中链接的结点数单链出边表中链接的结点数I D( Vi ) 邻接点为邻接点为Vi的弧个数的弧个数TD(Vi) = OD( Vi ) + I D( Vi )空间效率高；容易寻找顶点的邻接点；空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜

18、索两结判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。点对应的单链表，没有邻接矩阵方便。讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？【联络】【联络】 邻接表中每个链表对应于邻接矩阵中的一行，链表中邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。结点个数等于一行中非零元素的个数。【区别】【区别】 对于任一确定的无向图，邻接矩阵是唯一的行列对于任一确定的无向图，邻接矩阵是唯一的行列号与顶点编号一致），但邻接表不唯一链接次序号与顶点编号一致），但邻接表不唯一链接次序与顶点编号无关）。与顶点编号无关）。 邻接矩阵的空

19、间复杂度为邻接矩阵的空间复杂度为O(n2),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)。【用途】【用途】 邻接矩阵多用于稠密图的存储邻接矩阵多用于稠密图的存储e接近接近n(n-1)/2)；而；而邻接表多用于稀疏图的存储邻接表多用于稀疏图的存储en2)数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中选择题选择题 1. 在一个图中，所有顶点的度数之和等于所有边数的在一个图中，所有顶点的度数之和等于所有边数的 ( ) 倍。倍。 （A1/2 （B1 （C2 （D4 2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的在一个有向图中，所有顶点的入度之

20、和等于所有顶点的出度之和的 ( ) 倍。倍。 （A1/2 （B1 （C2 （D4 3. 一个有一个有 n 个顶点的无向图最多有个顶点的无向图最多有 ( ) 条边。条边。 （An （Bn(n -1) （Cn(n-1)/2 （D2n 4. 具有具有 4 个顶点的无向完全图有个顶点的无向完全图有 ( ) 条边。条边。 （A6 （B12 （C16 （D20 5. 具有具有 6 个顶点的无向图至少应有个顶点的无向图至少应有 ( ) 条边才能确保是一个连通图。条边才能确保是一个连通图。 （A5 （B6 （C7 （D86. 在一个具有在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要个顶点的无向图中，

21、要连通全部顶点至少需要 ( ) 条边。条边。 （An （Bn + 1 （Cn 1 （Dn/2 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中对于一个具有对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小矩阵的大小 为为 ( )。 （An （B）(n-1)2 （Cn -1 （Dn2 对于一个具有对于一个具有 n 个顶点和个顶点和 e 条边的无向图，若采用邻接表表示，条边的无向图，若采用邻接表表示，则表头数则表头数 组的大小为组的大小为 ( )，所有邻接表中的结点总数是，所有邻接表中的结点总数是 ( )。 （A

22、n （Bn+1 （Cn-1 （Dn+e （Ae/2 （Be （C2e （Dn+e 图的深度优先遍历算法类似于树的（图的深度优先遍历算法类似于树的（ ）。）。（A先根遍历先根遍历 （B后根遍历后根遍历 （C按层遍历按层遍历图的广度优先遍历算法类似于树的（图的广度优先遍历算法类似于树的（ ）。）。（A先根遍历先根遍历 （B后根遍历后根遍历 （C按层遍历按层遍历一、深度优先搜索二、广度优先搜索 7.3 图的遍历图的遍历遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图图中所有的顶点，且使每个顶

23、点仅被访问一次，就叫做图的遍历，它是图的基本运算。的遍历，它是图的基本运算。遍历实质：找每个顶点的邻接点的过程。遍历实质：找每个顶点的邻接点的过程。图的特点：图中可能存在回路，且图的任一顶点都可能与其它图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。到了曾经访问过的顶点。解决思路：可设置一个辅助数组解决思路：可设置一个辅助数组 visited n ，用来标记每个被，用来标记每个被访问过的顶点。它的初始状态为访问过的顶点。它的初始状态为0，在图的遍历过程中，在图的遍历过

24、程中，一旦某一个顶点一旦某一个顶点i 被访问，就立即改被访问，就立即改 visited i为为1，防止，防止它被多次访问。它被多次访问。图常用的遍历：图常用的遍历：怎样避免重复访问？怎样避免重复访问？7.3.1 深度优先遍历深度优先遍历DFS）（类似树的先根遍历）（类似树的先根遍历） 例：例： V1 V1V2V4V5V3V7V6V8顶点访问次序：顶点访问次序： V2 V4 V8 V5 V3 V6 V7 V1 V2 V5 V8 V4 V3 V6 V7 V1 V2 V4 V8 V5 V3 V7 V6 V1 V2 V5 V8 V4 V3 V7 V6 V1 V3 V6 V7 V2 V4 V8 V5 连

25、通图的深度优先遍历类似于树的先根遍历连通图的深度优先遍历类似于树的先根遍历 abchdekfga c h dfke b g顶点访问次序顶点访问次序: :例：例： a c h dfke g ba c h fked b g解决办法：为每个顶点设立一个解决办法：为每个顶点设立一个“访问标志访问标志”。 如何判别如何判别V的邻接点是否被访问？的邻接点是否被访问？ 首先将图中每个顶点的访问标志设为首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图之后搜索图 中每个顶点，如果未被访问，则以该顶点为起始点，进行深度中每个顶点，如果未被访问，则以该顶点为起始点，进行深度 优先遍历，否则继续检查下一顶点

26、。优先遍历，否则继续检查下一顶点。 1 3 7 0 V1 V2 V4 V8 V5 V3 0 1 2 3 4 5 6 7 V1 V2 V3 V4 V5 V6 V7 V8 2 1 3 1 5 6 7 7 6 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 2 V6 5 V7 6 V1V2V4V5V3V7V6V84 1 1 1 1 1 1 1 1 7.3.2 广度优先遍历广度优先遍历BFS）（类似于树的按层遍历）（类似于树的按层遍历） 方法：从图的某一结点出发，首先依次访问该结点的所有邻方法：从图的某一结点出发，首先依次访问该结点的所有邻 接顶点接顶点 Vi1, Vi2, , Vin

27、 再按这些顶点被访问的先后次序依次访问再按这些顶点被访问的先后次序依次访问 与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶 点均被访问为止。点均被访问为止。 例：例： V1V2V4V5V3V7V6V8广度优先遍历：广度优先遍历： V1 V2 V3 V4 V5 V6 V7 V8 V1 V3 V2 V7 V6 V5 V4 V8 V1 V2 V3 V5 V4 V7 V6 V8 abchdekfga c d e fh k bg顶点访问次序顶点访问次序: :例：例： a c d e fh k gb 1 3 4 0 V1 V2 V3 V4

28、V5 V6 实现：实现： V1V2V4V5V3V7V6V80 1 2 3 4 5 6 7 V1 V2 V3 V4 V5 V6 V7 V8 2 1 0 1 0 1 2 2 3 3 5 4 6 7 7 6 5 4 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 2 V7 5 V8 F R R F R R F R R F 6 7 F F F F F R R R 1 1 1 1 1 1 1 1 7.4 7.4 连通网的最小生成树连通网的最小生成树1.概念概念生成树：是一个极小连通子图，它含有图中全部顶点，但只有生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1n-1条边。条边

29、。生成森林：由若干棵生成树组成，含全部顶点，但构成这些树生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。的边是最少的。思考1：对连通图进行遍历，得到的是什么？ 得到的将是一个极小连通子图，即图的生成树！由深度优先搜索得到的生成树，称为深度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。思考2：对非连通图进行遍历，得到的是什么？ 得到的将是各连通分量的生成树，即图的生成森林！例例1 ：画出下图的生成树：画出下图的生成树DFS生生成成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成

30、树树v0v1v3v2v4无向连通图无向连通图DEGHIK子图子图(或连通分或连通分量量)ABCFJLMABCFJLMDEGHIK生生成成森森林林DEABCFJLMV1V6V5V4V3V26513566425V1V6V5V4V3V265134V1V6V5V4V3V26513219 17 2 构造最小生成树构造最小生成树 最小生成树：给定一个无向网络，在该网的所有生成最小生成树：给定一个无向网络，在该网的所有生成 树中，使得各边权数之和最小的那棵生成树称为该网的最树中，使得各边权数之和最小的那棵生成树称为该网的最 小生成树，也叫最小代价生成树。小生成树，也叫最小代价生成树。 要在要在 n 个城市间

31、建立通信联络网。顶点：表示城市，个城市间建立通信联络网。顶点：表示城市， 权：城市间通信线路的花费代价。希望此通信网花费代价最小。权：城市间通信线路的花费代价。希望此通信网花费代价最小。 答案只能从生成树中找，因为要做到任何两个城市之答案只能从生成树中找，因为要做到任何两个城市之 间有线路可达，通信网必须是连通的；但对长度最小的要求可以间有线路可达，通信网必须是连通的；但对长度最小的要求可以 知道网中显然不能有圈，如果有圈，去掉一条边后，并不破坏连知道网中显然不能有圈，如果有圈，去掉一条边后，并不破坏连 通性，但总代价显然减少了，这与总代价最小的假设是矛盾的。通性，但总代价显然减少了，这与总代

32、价最小的假设是矛盾的。 希望找到一棵生成树，它的每条边上的权值之和即建立希望找到一棵生成树，它的每条边上的权值之和即建立 该通信网所需花费的总代价最小该通信网所需花费的总代价最小 最小代价生成树。最小代价生成树。 讨论：如何求得最小生成树？讨论：如何求得最小生成树？有多种算法，但最常用的是以下两种：有多种算法，但最常用的是以下两种：v Prim普里姆算法普里姆算法 v Kruskal克鲁斯卡尔算法克鲁斯卡尔算法PrimePrime算法特点算法特点: : 将顶点归并，与边数无关，适于稠密网。将顶点归并，与边数无关，适于稠密网。 KruskalKruskal算法特点：将边归并，适于求稀疏网的最小生

33、成树。算法特点：将边归并，适于求稀疏网的最小生成树。这两个算法，都是利用这两个算法，都是利用MST MST 性质来构造最小生成树的。性质来构造最小生成树的。若若U集是集是V的一个非空子集，假设的一个非空子集，假设(u0, v0)是一条最小权值的边，是一条最小权值的边，其中其中u0U，v0V-U；那么：；那么：(u0, v0)必在最小生成树上。必在最小生成树上。 构造最小生成树方法：构造最小生成树方法： 方法一：普里姆方法一：普里姆 (Prim) 算法。算法。 V1V6V5V4V3V26513566425 设设 N=(V, E) 是连通网，是连通网，TE 是是 N 上最小生成树中边的集合。上最小

34、生成树中边的集合。 初始令初始令 U=u0, (u0V ), TE= 。 在所有在所有 u U, v V-U 的边的边 (u, v) E 中，中， 找一条代价最小的边找一条代价最小的边 (u0, v0)。 将将 (u0, v0) 并入集合并入集合 TE，同时，同时 v0 并入并入 U。 重复上述操作直至重复上述操作直至 U=V 为止，那么为止，那么 T=(V, TE) 为为 N 的最的最 小生成树。小生成树。 V1V3V6V4V2V5例：例： 注注 ：在最小生成树的生成过程中，所选的边都是：在最小生成树的生成过程中，所选的边都是 一端在一端在V-UV-U中，另一端在中，另一端在U U中。中。方

35、法二：克鲁斯卡尔方法二：克鲁斯卡尔 (Kruskal) 算法。算法。 V1V6V5V4V3V26513566425 设连通网设连通网 N = (V, E )，令最小生成树初，令最小生成树初始状态为只有始状态为只有 n 个顶点而无边的非连通图个顶点而无边的非连通图 T=(V, )，每个顶点自成一个连通分量。，每个顶点自成一个连通分量。 在在 E 中选取代价最小的边，若该边依附中选取代价最小的边，若该边依附 的顶点落在的顶点落在 T 中不同的连通分量上即：中不同的连通分量上即： 不能形成环），则将此边加入到不能形成环），则将此边加入到 T 中；否中；否 那么，舍去此边，选取下一条代价最小的边。那么

36、，舍去此边，选取下一条代价最小的边。 依此类推，直至依此类推，直至 T 中所有顶点都在同一中所有顶点都在同一 连通分量上为止。连通分量上为止。 V1V6V5V4V3V212345N T 最小生成树最小生成树 可能不惟一可能不惟一 例例 ：例：应用克鲁斯卡尔算法构造最小生成树的过程例：应用克鲁斯卡尔算法构造最小生成树的过程一顶点到其余各顶点一顶点到其余各顶点7.5. 7.5. 单源最短路径单源最短路径两种常见的最短路径问题：两种常见的最短路径问题：一、一、 单源最短路径单源最短路径用用Dijkstra迪杰斯特拉算法迪杰斯特拉算法二、所有顶点间的最短路径二、所有顶点间的最短路径用用Floyd弗洛伊

37、德算法弗洛伊德算法典型用途：交通问题。如：城市典型用途：交通问题。如：城市A A到城市到城市B B有多条线路，但每条有多条线路，但每条线路的交通费或所需时间不同，那么，如何选择一条线路，线路的交通费或所需时间不同，那么，如何选择一条线路，使总费用或总时间最少？使总费用或总时间最少？问题抽象：在带权有向图中问题抽象：在带权有向图中A A点源点到达点源点到达B B点终点的多点终点的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。条路径中，寻找一条各边权值之和最小的路径，即最短路径。（注：最短路径与最小生成树不同，路径上不一定包含（注：最短路径与最小生成树不同，路径上不一定包含n n个顶点）

38、个顶点）任意两顶点之间任意两顶点之间求单源最短路径求单源最短路径 (Dijkstra(Dijkstra算法算法) )目的：目的： 设一有向图设一有向图G=G=（V, EV, E），已知各边的权值，以某），已知各边的权值，以某指定点指定点v0v0为源点，求从为源点，求从v0v0到图的其余各点的最短路径。限到图的其余各点的最短路径。限定各边上的权值大于或等于定各边上的权值大于或等于0 0。例例1 1：源点源点从从FAFA的路径有的路径有4 4条：条： FA FA： 2424 FBA FBA： 5 518=2318=23 FBCA FBCA：5+7+9=215+7+9=21 FDCA FDCA：25

39、+12+9=3625+12+9=36又：又：从从FBFB的最短路径是哪条？的最短路径是哪条？从从FCFC的最短路径是哪条？的最短路径是哪条？例：例：讨论：计算机如何自动求出这些最短路径？讨论：计算机如何自动求出这些最短路径？v0(v0, v1)10源点源点终点终点最最短短路路 径径路径长度路径长度(v0, v1, v2) (v0, v3, v2)(v0, v4)30 v1 v2 v3 v4100(v0, v3, v4)(v0, v3, v2, v4) 60 5090 70(v0, v1, v2, v4)60(v0, v3)01234迪杰斯特拉迪杰斯特拉 (Dijkstra) 算法：按路径长度递

40、增次序产生最短路径算法：按路径长度递增次序产生最短路径1、把、把 V 分成两组：分成两组： (1) S：已求出最短路径的顶点的集合。：已求出最短路径的顶点的集合。 (2) V - S = T：尚未确定最短路径的顶点集合。：尚未确定最短路径的顶点集合。 2、将、将 T 中顶点按最短路径递增的次序加入到中顶点按最短路径递增的次序加入到 S 中，中， 保证：保证： (1) 从源点从源点 v0 到到 S 中各顶点的最短路径长度都不大于中各顶点的最短路径长度都不大于 从从 v0 到到 T 中任何顶点的最短路径长度。中任何顶点的最短路径长度。 (2) 每个顶点对应一个距离值：每个顶点对应一个距离值： S

41、中顶点：从中顶点：从 v0 到此顶点的最短路到此顶点的最短路 径长度。径长度。 T 中顶点：从中顶点：从 v0 到此顶点的只包括到此顶点的只包括 S 中顶点作中间顶点的中顶点作中间顶点的 最短路径长度。最短路径长度。 v5v1v6v4v3v2v0856230 13717329Dijkstra 算法步骤：算法步骤： T 中顶点对应的距离值用辅助数组中顶点对应的距离值用辅助数组 D 存放。存放。 Di 初值：假设初值：假设 存在，则为其权值；否则为存在，则为其权值；否则为。 终终点点从从 v0 到各终点的最短路径及长度到各终点的最短路径及长度i =1i =2i =3i =4i =5i =6v1v2

42、v3v4v5v6vj Sv5v1v6v4v3v2v0856230 13717329| MinTviDjDiiv21383032v2813133032v3v1v11313302220v38+5 192220v4v48+5+6 2120v6v513+7 21v5v6初始时令初始时令 S=v0, T=其余顶点其余顶点。 v0从从 T 中选取一个其距离值最小的顶点中选取一个其距离值最小的顶点 vj，参与，参与 S。 对对 T 中顶点的距离值进行修改：若加进中顶点的距离值进行修改：若加进 vj 作中间顶点，从作中间顶点，从 v0 到到 vi 的距离值比的距离值比 不加不加 vj 的路径要短，则修改此距离

43、值。的路径要短，则修改此距离值。 重复上述步骤，直到重复上述步骤，直到 S = V 为止。为止。 8+5 +6+2 7.6 拓朴排序拓朴排序 AOV网网(Activity On Vertices)用顶点表示活动的网络用顶点表示活动的网络AOV网定义：若用有向图表示一个工程，在图中用顶点表示网定义：若用有向图表示一个工程，在图中用顶点表示活动，用弧表示活动间的优先关系。活动，用弧表示活动间的优先关系。Vi 必须先于活动必须先于活动Vj 进展。进展。则这样的有向图叫做用顶点表示活动的网络，简称则这样的有向图叫做用顶点表示活动的网络，简称 AOV。 AOE网网(Activity On Edges)用

44、边表示活动的网络用边表示活动的网络AOE网定义：如果在无环的带权有向图中，网定义：如果在无环的带权有向图中， 用有向边表示一用有向边表示一个工程中的活动，用边上权值表示活动持续时间，用顶点表个工程中的活动，用边上权值表示活动持续时间，用顶点表示事件，则这样的有向图叫做用边表示活动的网络，简称示事件，则这样的有向图叫做用边表示活动的网络，简称 AOE。有两种常用的活动网络（有两种常用的活动网络（ Activity Network）：）：我们经常用有向图来描述一个工程或系统的进行过程。一我们经常用有向图来描述一个工程或系统的进行过程。一般来说，一个工程可以分为若干个子工程，只要完成了这般来说，一个

45、工程可以分为若干个子工程，只要完成了这些子工程，就可以导致整个工程的完成。些子工程，就可以导致整个工程的完成。AOV网络若用于教学计划的制定，可以解决：网络若用于教学计划的制定，可以解决：哪些课程是必须先修的，哪些课程是可以并行学习的。哪些课程是必须先修的，哪些课程是可以并行学习的。预备知识：拓扑排序预备知识：拓扑排序什么叫拓扑排序？什么叫拓扑排序？对一个有向无环图中的顶点排成一个具有前后次序的对一个有向无环图中的顶点排成一个具有前后次序的线性序列。线性序列。例：排课表。例：排课表。 课程代号课程代号 课程名称课程名称 先修课先修课 C1C2C3C4C5C6C7C8C9C10C11C12无无C

46、1C1,C2C1C3,C4C11C3,C5C3,C6无无C9C9C1,C9,C10 程序设计基础程序设计基础离散数学离散数学数据结构数据结构汇编语言汇编语言语言的设计和分析语言的设计和分析计算机原理计算机原理编译原理编译原理操作系统操作系统高等数学高等数学线性代数线性代数普通物理普通物理数值分析数值分析C1C2C3C4C5C6C7C8C9C10C11C12 假设假设 是网中有向边，那么是网中有向边，那么 i 是是 j 的直接前驱；的直接前驱； j 是是 i 的直接后继。的直接后继。 AOV 网中不允许有回路，因为如网中不允许有回路，因为如 果有回路存在，则表明某项活动以果有回路存在，则表明某项

47、活动以 自己为先决条件，显然这是荒谬的。自己为先决条件，显然这是荒谬的。 C1C2C3C4C5C6C7C8C9C10C11C12AOV 网的特点：网的特点： 若从若从 i 到到 j 有一条有向路径，那么有一条有向路径，那么 i 是是 j 的前驱；的前驱；j 是是 i 的后继。的后继。 拓扑排序：拓扑排序： 检测检测 AOV 网中是否存在环方法：网中是否存在环方法： 对有向图构造其顶对有向图构造其顶 点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序 列中，则该列中，则该 AOV 网必定不存在环。网必定不存在环。 在在 AOV 网没有回路的前提下

48、，我们将全部网没有回路的前提下，我们将全部 活动排列成一个线性序列，使得若活动排列成一个线性序列，使得若 AOV 网中有网中有 弧弧 存在，则在这个序列中，存在，则在这个序列中， i 一定排在一定排在 j 的前面，具有这种性质的线性序列称为拓扑有序的前面，具有这种性质的线性序列称为拓扑有序 序列，相应的拓扑有序排序的算法称为拓扑排序。序列，相应的拓扑有序排序的算法称为拓扑排序。 C1C2C3C4C5C6C7C8C9C10C11C12 在有向图中选一个没有前驱的顶点且输出之。在有向图中选一个没有前驱的顶点且输出之。 从图中删除该顶点和所有以它为起点的弧。从图中删除该顶点和所有以它为起点的弧。 重

49、复上述两步，直至全部顶点均已输出；或者当图中重复上述两步，直至全部顶点均已输出；或者当图中 不存在无前驱的顶点为止。不存在无前驱的顶点为止。 C9, C10, C11, C6, C1, C12, C4, C2, C3, C5, C7, C8 拓扑序列：拓扑序列：C1, C2, C3, C4, C5, C7, C9, C10, C11, C6, C12, C8 C1C2C3C4C5C6C7C8C9C10C11C12 一个一个AOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的 例：设一个工程有例：设一个工程有 11 11 项活项活 动，动， 9 9 个事件。个事件。 事件事件 v1 v1 表示整个工程表示整个工程 开场源点）开场源点） 事件事件 v9 v9 表示整个工程表示整个工程 终了汇点）终了汇点）7.7 关键路径关键路径 把工程计划表示为有向图，用顶点表示事件，弧表示把工程计划表示为有向图，用顶点表示事件，弧表示 活动，弧的权表示活动持续时间。每个事件表示在它之前活动，弧的权表示活动持续时间。每个事件表示在它之前 的活动已经完成，在它之后的活动可以开始。称这种有向的活动已经完成，在它之后的活动可以开始。称这种有向 图为边表示活动的网，简称为图