ACM数据结构与算法课件

《ACM数据结构与算法课件》由会员分享，可在线阅读，更多相关《ACM数据结构与算法课件（73页珍藏版）》请在金锄头文库上搜索。

1、 数据结构数据结构 (DATA STRUCTURE)计算机科学与工程系计算机科学与工程系1ACM数据结构与算法课程代码：第七章 图图的基本概念图的基本概念 图的存储表示图的存储表示 图的遍历与连通性图的遍历与连通性 最小生成树最小生成树 最短路径最短路径 活动网络活动网络2ACM数据结构与算法课程代码：7.1 图的基本概念图的定义图的定义 图是由顶点集合图是由顶点集合(vertex)及顶点间及顶点间的关系集合组成的一种数据结构的关系集合组成的一种数据结构： Graph( V, E ) 其中其中 V = x | x 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合； E =

2、(x, y) | x, y V 或或 E = | x, y V & Path (x, y) 是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)集合。集合。Path (x, y)表示从表示从 x 到到 y 的一条的一条通路。通路。3ACM数据结构与算法课程代码： 有向图与无向图有向图与无向图完全图完全图4ACM数据结构与算法课程代码： 邻接顶点邻接顶点 如果如果 (u, v) 是是 E(G) 中的一条边，中的一条边，则称则称 u 与与 v 互为邻接顶点互为邻接顶点。子子图图 设设有有两两个个图图G(V, E)和和G(V, E), 若若 V V 且且 E E, 则则称

3、称 图图G 是是图图G 的的子子图。图。5ACM数据结构与算法课程代码：顶顶点点的的度度 一一一一个个个个顶顶顶顶点点点点v v 的的的的度度度度是是是是与与与与它它它它相相相相关关关关联联联联的的的的边边边边的的的的条条条条数，记作数，记作数，记作数，记作TD(TD(v v) )。顶点顶点 v 的入度的入度 是以是以是以是以 v v 为终点为终点为终点为终点( (弧头弧头弧头弧头) )的有向边的条的有向边的条的有向边的条的有向边的条数数数数, , 记作记作记作记作 ID(ID(v v) ); ; 顶点顶点顶点顶点 v v 的出度的出度的出度的出度是以是以是以是以 v v 为始点为始点为始点为

4、始点( (弧尾弧尾弧尾弧尾) )的有向边的条数的有向边的条数的有向边的条数的有向边的条数, , 记作记作记作记作 OD(OD(v v) )。路径路径 在图在图在图在图 GG( (V V, , E E) ) 中中中中, , 若从顶点若从顶点若从顶点若从顶点 v vi i 出发出发出发出发, , 沿一些沿一些沿一些沿一些边经过一些顶点边经过一些顶点边经过一些顶点边经过一些顶点 v vp p1 1, , v vp p2 2, , , , v vpmpm，到达顶点，到达顶点，到达顶点，到达顶点v vj j。则称。则称。则称。则称顶点序列顶点序列顶点序列顶点序列 ( ( v vi i v vp p1 1

5、 v vp p2 2 . . v vpm pm v vj j ) ) 为从顶点为从顶点为从顶点为从顶点v vi i 到顶点到顶点到顶点到顶点 v vj j 的路径的路径的路径的路径。它经过的边。它经过的边。它经过的边。它经过的边( (v vi i, , v vp p1 1) )、( (v vp p1 1, , v vp p2 2) )、. .、( (v vpmpm, , v vj j) )应是属于应是属于应是属于应是属于E E 的边。的边。的边。的边。6ACM数据结构与算法课程代码：路径长度路径长度 非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。非带权图的路径

6、长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。简单路径简单路径 若路径上各顶点若路径上各顶点若路径上各顶点若路径上各顶点 v v1 1, ,v v2 2,.,.,v vm m 均不互相均不互相均不互相均不互相重复重复重复重复, , 则称这样的路径为简单路径。则称这样的路径为简单路径。则称这样的路径为简单路径。则称这样的路径为简单路径。回路回路 若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点

7、 v v1 1 与最后一个顶点与最后一个顶点与最后一个顶点与最后一个顶点v vm m 重合重合重合重合, , 则称这样的路径为回路或环。则称这样的路径为回路或环。则称这样的路径为回路或环。则称这样的路径为回路或环。简单回路简单回路 除了第一个顶点和最后一个顶点外，除了第一个顶点和最后一个顶点外，除了第一个顶点和最后一个顶点外，除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路其余顶点不重复出现的回路叫简单回路其余顶点不重复出现的回路叫简单回路其余顶点不重复出现的回路叫简单回路 7ACM数据结构与算法课程代码：例例157324G26例例245136G1路径：路径：1，2，3，5，

8、6，3路径长度：路径长度：5简单路径：简单路径：1，2，3，5回路：回路：1，2，3，5，6，3，1简单回路：简单回路：3，5，6，3路径：路径：1，2，5，7，6，5，2，3路径长度：路径长度：7简单路径：简单路径：1，2，5，7，6回路：回路：1，2，5，7，6，5，2，1简单回路：简单回路：1，2，3，18ACM数据结构与算法课程代码：7.2 图的存储结构1 1）存储特点）存储特点在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个记录各个顶点记录各个顶点记录各个顶点记录各个顶点信息信息信息信息的的的的顶点表；顶点表；顶点表；顶

9、点表；还有一个还有一个还有一个还有一个表示各个顶点之间关系表示各个顶点之间关系表示各个顶点之间关系表示各个顶点之间关系的的的的邻接矩阵邻接矩阵邻接矩阵邻接矩阵。2 2）邻接矩阵）邻接矩阵 设图设图设图设图 A = (A = (V V, , E E) )是一个有是一个有是一个有是一个有 n n 个顶点的图，则图个顶点的图，则图个顶点的图，则图个顶点的图，则图的的的的邻接矩阵邻接矩阵邻接矩阵邻接矩阵是一个二维数组是一个二维数组是一个二维数组是一个二维数组 AAn n n n ，定义：，定义：，定义：，定义：7.2.1 邻接矩阵邻接矩阵(Adjacency Matrix)表示法表示法9ACM数据结构

10、与算法课程代码：10ACM数据结构与算法课程代码： 网络的邻接矩阵11ACM数据结构与算法课程代码：3）数据类型描述#define MaxVNum 100 #define MaxVNum 100 /*/*最大顶点数设为最大顶点数设为最大顶点数设为最大顶点数设为100*/100*/typedef XXX VertexType; typedef XXX VertexType; /*/*顶点类型顶点类型顶点类型顶点类型* */ /邻接矩阵类型：邻接矩阵类型：邻接矩阵类型：邻接矩阵类型： typedef int EdgeType; typedef int EdgeType; /*/*边的权值设为整型边

11、的权值设为整型边的权值设为整型边的权值设为整型* */ / typedef struct ArcCell typedef struct ArcCell VertexType adj; VertexType adj; InfoType *Info; InfoType *Info; / / 存弧相关信息存弧相关信息存弧相关信息存弧相关信息 ArcCell,AdjMatrixMaxVNumMaxVNum ArcCell,AdjMatrixMaxVNumMaxVNum 图类型：图类型：图类型：图类型： typedef structtypedef struct VertexType vexsMaxVNu

12、m; VertexType vexsMaxVNum; /*/*顶点表顶点表顶点表顶点表* */ / AdjMatrix arcs; AdjMatrix arcs; /*/*邻接矩阵，即边表邻接矩阵，即边表邻接矩阵，即边表邻接矩阵，即边表* */ / int vexnum,arcnum; int vexnum,arcnum; /*/*图的顶点数和边数图的顶点数和边数图的顶点数和边数图的顶点数和边数* */ / Mgragh; Mgragh; /*Maragh/*Maragh是以邻接矩阵存储的图是以邻接矩阵存储的图是以邻接矩阵存储的图是以邻接矩阵存储的图* */ /12ACM数据结构与算法课程代码

13、：4）图的创建 思路：思路：思路：思路：13ACM数据结构与算法课程代码：7.2.2 邻接表 (Adjacency List)1) 1) 存储特点存储特点 对于图对于图对于图对于图GG中的每个顶点中的每个顶点中的每个顶点中的每个顶点vivi，把所有邻接于，把所有邻接于，把所有邻接于，把所有邻接于vivi的顶点的顶点的顶点的顶点vjvj链成一链成一链成一链成一个单链表，这个单链表称为顶点个单链表，这个单链表称为顶点个单链表，这个单链表称为顶点个单链表，这个单链表称为顶点vivi的邻接表；的邻接表；的邻接表；的邻接表； 将所有点的邻接表表头放到数组中，就构成了图的邻接表将所有点的邻接表表头放到数组

14、中，就构成了图的邻接表将所有点的邻接表表头放到数组中，就构成了图的邻接表将所有点的邻接表表头放到数组中，就构成了图的邻接表 14ACM数据结构与算法课程代码：特点特点无向图中顶点无向图中顶点ViVi的度为第的度为第i i个单链表中的结点数个单链表中的结点数有向图中有向图中 顶点顶点ViVi的出度为第的出度为第i i个单链表中的结点个数个单链表中的结点个数 顶点顶点ViVi的入度为整个的入度为整个单链表中邻接点域值是单链表中邻接点域值是i i的结点个数的结点个数逆邻接表：有向图中对每个结点建立以逆邻接表：有向图中对每个结点建立以ViVi为头的弧的单为头的弧的单链表链表例例G1bdac1234ac

15、dbvexdatafirstarc 4 1 1 3adjvexnext15ACM数据结构与算法课程代码：16ACM数据结构与算法课程代码：2）数据类型描述define MaxVerNum 100 /*define MaxVerNum 100 /*最大顶点数为最大顶点数为最大顶点数为最大顶点数为100*/100*/邻接表类型邻接表类型邻接表类型邻接表类型 ： typedef struct ArcNodetypedef struct ArcNode int adjvex; /* int adjvex; /*邻接点域邻接点域邻接点域邻接点域* */ / InfoType *Info; /* Info

16、Type *Info; /*表示边上信息的域表示边上信息的域表示边上信息的域表示边上信息的域info*/info*/ struct ArcNode * next; /* struct ArcNode * next; /*指向下一个邻接点的指针域指向下一个邻接点的指针域指向下一个邻接点的指针域指向下一个邻接点的指针域* */ / ArcNode ; ArcNode ; 表头结点类型表头结点类型表头结点类型表头结点类型 ： typedef struct Vnodetypedef struct Vnode VertexType vertex; /* VertexType vertex; /*顶点域顶

17、点域顶点域顶点域* */ / ArcNode * firstedge; /* ArcNode * firstedge; /*边表头指针边表头指针边表头指针边表头指针* */ / Vnode,AdjList MaxVertexNum; Vnode,AdjList MaxVertexNum; 图的类型图的类型图的类型图的类型 ： typedef structtypedef struct AdjList vertices; /* AdjList vertices; /*邻接表邻接表邻接表邻接表* */ / int vexnum,arcnum; /* int vexnum,arcnum; /*顶点数和

18、边数顶点数和边数顶点数和边数顶点数和边数* */ / ALGraph; /*ALGraph ALGraph; /*ALGraph是以邻接表方式存储的图类型是以邻接表方式存储的图类型是以邻接表方式存储的图类型是以邻接表方式存储的图类型* */ /17ACM数据结构与算法课程代码：7.2.3 十字链表 (Orthogonal List) 十字链表是十字链表是十字链表是十字链表是有向图有向图有向图有向图的另一种链式存储结构，它实际的另一种链式存储结构，它实际的另一种链式存储结构，它实际的另一种链式存储结构，它实际上是上是上是上是邻接表邻接表邻接表邻接表与与与与逆邻接表逆邻接表逆邻接表逆邻接表的结合的

19、结合的结合的结合1) 1) 存储特点存储特点图中每一条弧有一个结点，把弧头相同的弧连图中每一条弧有一个结点，把弧头相同的弧连图中每一条弧有一个结点，把弧头相同的弧连图中每一条弧有一个结点，把弧头相同的弧连在同一链表上在同一链表上在同一链表上在同一链表上, , , ,弧尾相同的弧也连在同一链表上。弧尾相同的弧也连在同一链表上。弧尾相同的弧也连在同一链表上。弧尾相同的弧也连在同一链表上。结点结构为：结点结构为：结点结构为：结点结构为：顶点结点为链表头结点，其结构为：顶点结点为链表头结点，其结构为：顶点结点为链表头结点，其结构为：顶点结点为链表头结点，其结构为：18ACM数据结构与算法课程代码：7.

20、2.4 邻接多重表(Adjacency Multilist) 邻接多重表是邻接多重表是无向图无向图的另一种链式存储结构的另一种链式存储结构1) 1) 存储特点存储特点 图中每一条边用一个边结点表示，其结构为：图中每一条边用一个边结点表示，其结构为：图中每一条边用一个边结点表示，其结构为：图中每一条边用一个边结点表示，其结构为：每个顶点用一个结点表示，其结构为：每个顶点用一个结点表示，其结构为：每个顶点用一个结点表示，其结构为：每个顶点用一个结点表示，其结构为：mark ivex ilink jvex jlinkdata firstedge19ACM数据结构与算法课程代码： 在邻接多重表中在邻接

21、多重表中在邻接多重表中在邻接多重表中, , 所有依附于同一个顶点的边都所有依附于同一个顶点的边都所有依附于同一个顶点的边都所有依附于同一个顶点的边都链接在同一个单链表中。链接在同一个单链表中。链接在同一个单链表中。链接在同一个单链表中。 邻接多重表的结构邻接多重表的结构邻接多重表的结构邻接多重表的结构例例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 220ACM数据结构与算法课程代码：7.3 图的遍历与连通性从图中某一顶点出发，沿着一些边访遍图中从图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，所有的顶点，且使每个顶点仅被访问一次，叫做叫

22、做图的遍历图的遍历 ( Graph Traversal )。为了避免重复访问，可设置一个标志顶点是为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组否被访问过的辅助数组 visited ，它的初始，它的初始状态为状态为 0，在图的遍历过程中，一旦某一个，在图的遍历过程中，一旦某一个顶点顶点 i 被访问，就立即让被访问，就立即让 visited i 为为 1，防，防止它被多次访问。止它被多次访问。21ACM数据结构与算法课程代码：7.3.1 深度优先搜索DFS1）基本思想：）基本思想：任选图中一个顶点任选图中一个顶点任选图中一个顶点任选图中一个顶点 v v , , 访问此顶点访问此顶点访

23、问此顶点访问此顶点, , 并作访问标记。并作访问标记。并作访问标记。并作访问标记。从从从从 v v 出发，访问它的任一未被访问过的邻接顶点出发，访问它的任一未被访问过的邻接顶点出发，访问它的任一未被访问过的邻接顶点出发，访问它的任一未被访问过的邻接顶点 w w ，作访问标记，并以，作访问标记，并以，作访问标记，并以，作访问标记，并以 w w 为新的出发点，继续进为新的出发点，继续进为新的出发点，继续进为新的出发点，继续进行深度优先搜索。行深度优先搜索。行深度优先搜索。行深度优先搜索。当某个顶点的所有邻接顶点都被访问过后，则退当某个顶点的所有邻接顶点都被访问过后，则退当某个顶点的所有邻接顶点都被

24、访问过后，则退当某个顶点的所有邻接顶点都被访问过后，则退回到前一次刚访问过的顶点回到前一次刚访问过的顶点回到前一次刚访问过的顶点回到前一次刚访问过的顶点k k，从，从，从，从k k的另一个没有的另一个没有的另一个没有的另一个没有被访问的邻接顶点出发进行深度优先搜索。被访问的邻接顶点出发进行深度优先搜索。被访问的邻接顶点出发进行深度优先搜索。被访问的邻接顶点出发进行深度优先搜索。重复上述过程重复上述过程重复上述过程重复上述过程, , 直到图中所有顶点都被访问过为止直到图中所有顶点都被访问过为止直到图中所有顶点都被访问过为止直到图中所有顶点都被访问过为止22ACM数据结构与算法课程代码：n n深度

25、优先搜索的示例深度优先搜索的示例例例V1V2V4V5V3V7V6V8深度遍历：深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V3 V6 V7 V523ACM数据结构与算法课程代码：n n深度优先搜索的示例深度优先搜索的示例遍历结果：遍历结果：A A、B B、D D、C C例例24ACM数据结构与算法课程代码：2）算法实现难点：难点：如何标记已访问结点如何标记已访问结点如何标记已访问结点如何标记已访问结点v ?v ?如何查找如何查找如何查找如何查找 v v 的的的的所有邻接点？所有邻接点？所有邻接点？所有邻

26、接点？解决办法：解决办法：设置一个布尔向量数组设置一个布尔向量数组设置一个布尔向量数组设置一个布尔向量数组visitednvisitedn，初值为，初值为，初值为，初值为0 0。若序号为若序号为若序号为若序号为 i i 的结点已被访问过，则的结点已被访问过，则的结点已被访问过，则的结点已被访问过，则visitedi=1visitedi=1。根据图的存储方式不同，采取相应方法查找：根据图的存储方式不同，采取相应方法查找：根据图的存储方式不同，采取相应方法查找：根据图的存储方式不同，采取相应方法查找： 邻接矩阵：邻接矩阵：邻接矩阵：邻接矩阵：v vi i 的邻接点是邻接矩阵中第的邻接点是邻接矩阵中

27、第的邻接点是邻接矩阵中第的邻接点是邻接矩阵中第i i 行上非行上非行上非行上非0 0元素对应的列值，若元素对应的列值，若元素对应的列值，若元素对应的列值，若Aij0Aij0，则，则，则，则v vj j为为为为v vi i邻接点。邻接点。邻接点。邻接点。 邻接表：是以邻接表：是以邻接表：是以邻接表：是以G.verticesiG.verticesi为表头结点的单链表上为表头结点的单链表上为表头结点的单链表上为表头结点的单链表上的所有结点。的所有结点。的所有结点。的所有结点。25ACM数据结构与算法课程代码：V1V2V4V5V3V7V6V8例例1234V1V3V4V2vexdatafirstarc

28、2 7 8 3adjvexnext5V5 6 4 8 2V6V7V8678 7深度遍历：深度遍历：V1 V3 V7 V6 V2 V4 V8 V526ACM数据结构与算法课程代码：3）算法分析图中有图中有 n 个顶点，个顶点，e 条边。条边。由于总共有由于总共有 2e 个边结点，所以扫描边的时个边结点，所以扫描边的时间为间为O(e)。而且对所有顶点递归访问。而且对所有顶点递归访问1次，次，所以遍历图的时间复杂性为所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为的所有的边，所需时间为O(n)，则遍历图中，则遍历

29、图中所有的顶点所需的时间为所有的顶点所需的时间为O(n2)。27ACM数据结构与算法课程代码：7.3.2 广度优先搜索 BFS1 1）基本思想：）基本思想：任选图中一个顶点任选图中一个顶点任选图中一个顶点任选图中一个顶点 v v ，访问此顶点，并作访问，访问此顶点，并作访问，访问此顶点，并作访问，访问此顶点，并作访问标记。标记。标记。标记。从从从从 v v 出发，依次访问出发，依次访问出发，依次访问出发，依次访问 v v 的各个未曾被访问过的的各个未曾被访问过的的各个未曾被访问过的的各个未曾被访问过的邻接顶点邻接顶点邻接顶点邻接顶点 w w1 1, , w w2 2, , , , w wt t

30、，并作访问标记。，并作访问标记。，并作访问标记。，并作访问标记。然后再顺序访问然后再顺序访问然后再顺序访问然后再顺序访问 w w1 1, , w w2 2, , , , w wt t 的所有还未被访的所有还未被访的所有还未被访的所有还未被访问过的邻接顶点，并作访问标记。问过的邻接顶点，并作访问标记。问过的邻接顶点，并作访问标记。问过的邻接顶点，并作访问标记。 如此做下去如此做下去如此做下去如此做下去, ,直到图中所有顶点都被访问到直到图中所有顶点都被访问到直到图中所有顶点都被访问到直到图中所有顶点都被访问到为止为止为止为止28ACM数据结构与算法课程代码：n n广度优先搜索的示例广度优先搜索的

31、示例例例V1V2V4V5V3V7V6V8例例广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V6 V7 V8 V529ACM数据结构与算法课程代码：n n广度优先搜索的示例广度优先搜索的示例遍历结果：遍历结果：A A、B B、C C、D D例例30ACM数据结构与算法课程代码： 为了实现逐层访问，算法中使用了一个队列，以记忆为了实现逐层访问，算法中使用了一个队列，以记忆为了实现逐层访问，算法中使用了一个队列，以记忆为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下

32、一层正在访问的这一层和上一层的顶点，以便于向下一层正在访问的这一层和上一层的顶点，以便于向下一层正在访问的这一层和上一层的顶点，以便于向下一层访问。访问。访问。访问。2）算法实现开始开始标志数组初始化标志数组初始化Vi=1Vi访问过访问过BFSVi=Vi+1Vi=Vexnums结束结束NNYY31ACM数据结构与算法课程代码： BFSBFS开始开始访问访问Vi,置置标志标志求求V邻接点邻接点WW存在吗存在吗V下一邻接点下一邻接点WW访问过访问过结束结束NYNY初始化队列初始化队列Vi入队入队队列空吗队列空吗队头队头V出队出队访问访问W,置置标志标志W入队入队NaaY32ACM数据结构与算法课程

33、代码：如果使用邻接表表示图，则循环的总时间如果使用邻接表表示图，则循环的总时间代价为代价为 d1 + d2 + + dn = O(e)，其中的，其中的 di 是顶点是顶点 i 的度。的度。如果使用邻接矩阵，则对于每一个被访问如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的过的顶点，循环要检测矩阵中的 n 个元素，个元素，总的时间代价为总的时间代价为O(n2)。3 3）算法分析）算法分析33ACM数据结构与算法课程代码：7.4 图的连通性与生成树7.4.1 图的连通性问题图的连通性问题连通图与连通分量连通图与连通分量 在在无向图无向图中中, 若从顶点若从顶点v1到顶点到顶点v2有

34、路径有路径, 则称顶点则称顶点v1与与v2是连通的。是连通的。如果图中如果图中任意一对顶点任意一对顶点都是连通的都是连通的, 则称此则称此图是图是连通图连通图。非连通图的极大连通子图叫做。非连通图的极大连通子图叫做连通分量连通分量。强连通图与强连通分量强连通图与强连通分量 在在有向图有向图中中, 若对若对于于每一对顶点每一对顶点vi和和vj, 都存在一条都存在一条从从vi到到vj和和从从vj到到vi的路径的路径, 则称此图是则称此图是强连通图强连通图。非强连。非强连通图的极大强连通子图叫做通图的极大强连通子图叫做强连通分量强连通分量。34ACM数据结构与算法课程代码：连通图连通图例例24513

35、6强连通图强连通图356例例非连通图非连通图连通分量连通分量例例24513635ACM数据结构与算法课程代码：7.4.2 最小生成树 1）图的生成树）图的生成树连通图连通图连通图连通图GG的一个的一个的一个的一个子图子图子图子图如果是一棵包含如果是一棵包含如果是一棵包含如果是一棵包含GG的所有顶点的所有顶点的所有顶点的所有顶点的树（所有顶点均由边连接在一起，但不存在回的树（所有顶点均由边连接在一起，但不存在回的树（所有顶点均由边连接在一起，但不存在回的树（所有顶点均由边连接在一起，但不存在回路路路路, ,有有有有n-1n-1条边），则该子图称为条边），则该子图称为条边），则该子图称为条边），则

36、该子图称为GG的的的的生成树生成树生成树生成树。生成树生成树生成树生成树是连通图的是连通图的是连通图的是连通图的极小连通子图极小连通子图极小连通子图极小连通子图。所谓极小是指：。所谓极小是指：。所谓极小是指：。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若在树中任意增加一条边，则将出现一个回路；若在树中任意增加一条边，则将出现一个回路；若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。若去掉一条边，将会使之变成非连通图。若去掉一条边，将会使之变成非连通图。若去掉一条边，将会使之变成非连通图。 使用不同的遍历图的方法，可以得到不同的生成树使用不同的遍历图的

37、方法，可以得到不同的生成树使用不同的遍历图的方法，可以得到不同的生成树使用不同的遍历图的方法，可以得到不同的生成树36ACM数据结构与算法课程代码：说明说明一个图可以有许多棵不同的生成树一个图可以有许多棵不同的生成树一个图可以有许多棵不同的生成树一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：所有生成树具有以下共同特点：所有生成树具有以下共同特点：所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图生成树是图的极小连通子图生成树是图的极小连通子图

38、生成树是图的极小连通子图 一个有一个有一个有一个有n n个顶点的连通图的生成树有个顶点的连通图的生成树有个顶点的连通图的生成树有个顶点的连通图的生成树有n-1n-1条边条边条边条边 生成树中任意两个顶点间的路径是唯一的生成树中任意两个顶点间的路径是唯一的生成树中任意两个顶点间的路径是唯一的生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路含含含含n n个顶点个顶点个顶点个顶点n-1n-1条边的图不一定是生成树条边的图不一定是生成树条边的图不一定是生成树条边的图不一定是生成树GHK

39、I37ACM数据结构与算法V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V838ACM数据结构与算法课程代码：例例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林深度优先生成森林39ACM数据结构与算法课程代码：n n 问题提出问题提出 要在要在要在要在n n个城市间建立通信联

40、络网，个城市间建立通信联络网，个城市间建立通信联络网，个城市间建立通信联络网， 顶点顶点顶点顶点 城市城市城市城市 权权权权 城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价 生成树各边的权值总和称为生成树各边的权值总和称为生成树的权生成树的权。权。权最小的生成树称为最小的生成树称为最小生成树。最小生成树。2) 构造最小生成树 n n 问题分析问题分析问题分析问题分析uu n n个城市间个城市间个城市间个城市间, , 最多可设置最多可设置最多可设置最多可设置n(n-1)/2n(n-1)/2条线路条线路条线路条线路uu n

41、n个城市间建立通信网个城市间建立通信网个城市间建立通信网个城市间建立通信网, , 只需只需只需只需n-1n-1条线路条线路条线路条线路uu 问题转化为：如何在可能的线路中选问题转化为：如何在可能的线路中选问题转化为：如何在可能的线路中选问题转化为：如何在可能的线路中选择择择择n-1n-1条，能把所有城市（顶点）均连起条，能把所有城市（顶点）均连起条，能把所有城市（顶点）均连起条，能把所有城市（顶点）均连起来，且总耗费各边权值之和）最小来，且总耗费各边权值之和）最小来，且总耗费各边权值之和）最小来，且总耗费各边权值之和）最小165432713179181275241040ACM数据结构与算法课程

42、代码：最小生成树的重要性质：最小生成树的重要性质： 设设 G =G =（V V，E E）是一个连通网络，）是一个连通网络，U U是顶点集是顶点集V V的一个真子集。若（的一个真子集。若（u u，v v）是）是G G中所有的一个顶点在中所有的一个顶点在U,U,另一个顶点不在另一个顶点不在 U U 的边中，的边中，具有最小权值具有最小权值的一条的一条边，则一定存在边，则一定存在 G G 的一棵最小生成树包括此边。的一棵最小生成树包括此边。uvUVU41ACM数据结构与算法课程代码： 普里姆(Prim)算法普里姆算法的基本思想：普里姆算法的基本思想：普里姆算法的基本思想：普里姆算法的基本思想： 假设

43、图假设图假设图假设图G G = = V V, , E E ，所求最小生成树所求最小生成树所求最小生成树所求最小生成树T=(U,TE), T=(U,TE), 其中其中其中其中U=V, TE U=V, TE E E 从连通网络从连通网络从连通网络从连通网络 G G = = V V, , E E 中的某一顶点中的某一顶点中的某一顶点中的某一顶点 u u0 0 出发，选择与出发，选择与出发，选择与出发，选择与它关联的它关联的它关联的它关联的具有最小权值具有最小权值具有最小权值具有最小权值的边的边的边的边( (u u0 0, , v v) )，将其顶点加入到生成，将其顶点加入到生成，将其顶点加入到生成，

44、将其顶点加入到生成树的顶点集合树的顶点集合树的顶点集合树的顶点集合U U中。中。中。中。 以后每一步从以后每一步从以后每一步从以后每一步从一个顶点在一个顶点在一个顶点在一个顶点在U U中中中中，而，而，而，而另一个顶点不在另一个顶点不在另一个顶点不在另一个顶点不在U U中中中中的的的的各条边中选择各条边中选择各条边中选择各条边中选择权值最小的边权值最小的边权值最小的边权值最小的边( (u u, , v v) ), ,把它的顶点加入到把它的顶点加入到把它的顶点加入到把它的顶点加入到集集集集合合合合U U中。中。中。中。 如此继续下去，直到网络中的所有顶点都加入到生成树如此继续下去，直到网络中的所

45、有顶点都加入到生成树如此继续下去，直到网络中的所有顶点都加入到生成树如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合顶点集合顶点集合顶点集合U U中为止。中为止。中为止。中为止。42ACM数据结构与算法课程代码： 算法实现算法实现: (略略) 算法分析：算法分析： 上述算法的初始化时间是上述算法的初始化时间是O(1)O(1)，k k循环中有两循环中有两个循环语句，其时间大致为：个循环语句，其时间大致为： 令令O(1)O(1)为某一正常数为某一正常数C C，展开上述求和公式可，展开上述求和公式可知其数量级仍是知其数量级仍是 n n 的平方。所以，整个算法的时的平方。所以，整个算法的时间复

46、杂性是间复杂性是O(nO(n2 2) )43ACM数据结构与算法课程代码： 克鲁斯卡尔 (Kruskal) 算法克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：设有一个有设有一个有设有一个有设有一个有 n n 个顶点的连通网络个顶点的连通网络个顶点的连通网络个顶点的连通网络 G G = = V V, , E E ，最初先构造一个只有最初先构造一个只有最初先构造一个只有最初先构造一个只有 n n 个顶点，没有边的非连个顶点，没有边的非连个顶点，没有边的非连个顶点，没有边的非连通图通图通图通图 T T = = V V, , , , 图中每个顶点自成一个连通图中每个顶点自成一个连通图中每个顶点自

47、成一个连通图中每个顶点自成一个连通分量。分量。分量。分量。在在在在 E E 中选取一条具有中选取一条具有中选取一条具有中选取一条具有最小权值的边最小权值的边最小权值的边最小权值的边(u,v)(u,v)，若该，若该，若该，若该边的两个顶点边的两个顶点边的两个顶点边的两个顶点落在两个不同的连通分量落在两个不同的连通分量落在两个不同的连通分量落在两个不同的连通分量上，则上，则上，则上，则将此边将此边将此边将此边加入到加入到加入到加入到 T T 中中中中；否则将此边舍去，重新选；否则将此边舍去，重新选；否则将此边舍去，重新选；否则将此边舍去，重新选择一条权值最小的边。择一条权值最小的边。择一条权值最小

48、的边。择一条权值最小的边。如此上步，直到如此上步，直到如此上步，直到如此上步，直到 T T 中所有顶点在同一个连通分中所有顶点在同一个连通分中所有顶点在同一个连通分中所有顶点在同一个连通分量上为止。量上为止。量上为止。量上为止。44ACM数据结构与算法课程代码：应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程例例16543265135664251654321234545ACM数据结构与算法课程代码：7.5 有向无环图及其应用计划、施工过程、生产流程、程序流程等计划、施工过程、生产流程、程序流程等都是都是“工程工程”。除了很小的工程外，一般。除了很小的工程外，一般都把

49、工程分为若干个叫做都把工程分为若干个叫做“活动活动”的子工的子工程。程。例如，计算机专业学生的学习就是一个工例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些活动。其中有些课程要求先修课程，有些则不要求。些则不要求。7.5.1 活动网络活动网络(Activity Network) 用用顶点顶点表示活动的网络表示活动的网络 (AOV(AOV网络网络) )46ACM数据结构与算法课程代码： C C1 1 高等数学高等数学高等数学高等数学 C C2 2 程序设计基础程序设计基础程序设计基础程序设计基础 C

50、 C3 3 离散数学离散数学离散数学离散数学 C C1 1, C, C2 2 C C4 4 数据结构数据结构数据结构数据结构 C C3 3, C, C2 2 C C5 5 高级语言程序设计高级语言程序设计高级语言程序设计高级语言程序设计 C C2 2 C C6 6 编译方法编译方法编译方法编译方法 C C5 5, C, C4 4 C C7 7 操作系统操作系统操作系统操作系统 C C4 4, C, C9 9 C C8 8 普通物理普通物理普通物理普通物理 C C1 1 C C9 9 计算机原理计算机原理计算机原理计算机原理 C C8 8 47ACM数据结构与算法课程代码：学生课程学习工程图学生

51、课程学习工程图48ACM数据结构与算法课程代码：可以用可以用可以用可以用有向图有向图有向图有向图表示一个工程。在这种有向图中，表示一个工程。在这种有向图中，表示一个工程。在这种有向图中，表示一个工程。在这种有向图中，用顶点表示活动用顶点表示活动用顶点表示活动用顶点表示活动，用有向边用有向边用有向边用有向边 表示活动间表示活动间表示活动间表示活动间的优先关系，的优先关系，的优先关系，的优先关系，V Vi i 必须先于活动必须先于活动必须先于活动必须先于活动V Vj j 进行。这种有进行。这种有进行。这种有进行。这种有向图叫做向图叫做向图叫做向图叫做顶点表示活动的顶点表示活动的顶点表示活动的顶点表

52、示活动的AOVAOV网络网络网络网络(Activity (Activity On Vertices)On Vertices)。 在在在在AOVAOV网络中，如果活动网络中，如果活动网络中，如果活动网络中，如果活动V Vi i 必须在活动必须在活动必须在活动必须在活动V Vj j 之前之前之前之前进行，则存在有向边进行，则存在有向边进行，则存在有向边进行，则存在有向边 ， AOVAOV网络中不网络中不网络中不网络中不能出现有向回路，即有向环。在能出现有向回路，即有向环。在能出现有向回路，即有向环。在能出现有向回路，即有向环。在AOVAOV网络中如网络中如网络中如网络中如果出现了有向环，则意味着某

53、项活动应以自己果出现了有向环，则意味着某项活动应以自己果出现了有向环，则意味着某项活动应以自己果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的作为先决条件。因此，对给定的作为先决条件。因此，对给定的作为先决条件。因此，对给定的AOVAOV网络，必网络，必网络，必网络，必须先判断它须先判断它须先判断它须先判断它是否存在有向环。是否存在有向环。是否存在有向环。是否存在有向环。49ACM数据结构与算法课程代码：检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构网络构造它的拓扑有序序列。即将各个顶点造它的拓扑有序序列。即将各个顶点 (代表各个活动代表各个活动)排列成一个线

54、性有序的排列成一个线性有序的序列，使得序列，使得AOV网络中所有应存在的前网络中所有应存在的前驱和后继关系都能得到满足。驱和后继关系都能得到满足。拓扑排序：拓扑排序：从某个集合上的一个从某个集合上的一个偏序偏序得得到该集合上的一个到该集合上的一个全序全序，这个操作称为，这个操作称为拓扑排序。拓扑排序。1） 拓扑排序50ACM数据结构与算法课程代码：例如，对学生选课工程图进行拓扑排序，得到的例如，对学生选课工程图进行拓扑排序，得到的例如，对学生选课工程图进行拓扑排序，得到的例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为拓扑有序序列为拓扑有序序列为拓扑有序序列为 C C1 1 , C ,

55、 C2 2 , C , C3 3 , C , C4 4 , C , C5 5 , C , C6 6 , C , C8 8 , C , C9 9 , C , C7 7或或或或 C C1 1 , C , C8 8 , C , C9 9 , C , C2 2 , C, C5 5 , C , C3 3 , C, C4 4 , C , C7 7 , C , C6 651ACM数据结构与算法课程代码：2）进行拓扑排序的方法 输入输入输入输入AOVAOVAOVAOV网络，令网络，令网络，令网络，令 n n n n 为顶点个数为顶点个数为顶点个数为顶点个数在在在在AOVAOVAOVAOV网络中选一个网络中选一

56、个网络中选一个网络中选一个没有直接前驱没有直接前驱没有直接前驱没有直接前驱的顶点（即此顶点的顶点（即此顶点的顶点（即此顶点的顶点（即此顶点入度为入度为入度为入度为0 0 0 0）, , , , 并输出之；并输出之；并输出之；并输出之；从图中从图中从图中从图中删删删删去该去该去该去该顶点顶点顶点顶点, , , ,同时同时同时同时删删删删去所有它发出的去所有它发出的去所有它发出的去所有它发出的有向边有向边有向边有向边; ; ; ;重复以上两步重复以上两步重复以上两步重复以上两步, , , , 直到直到直到直到 全部顶点均已输出，拓扑有序序列形成，拓扑排序完全部顶点均已输出，拓扑有序序列形成，拓扑排

57、序完全部顶点均已输出，拓扑有序序列形成，拓扑排序完全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或成；或成；或成；或 图中还有未输出的顶点，但已跳出处理循环。这说明图中还有未输出的顶点，但已跳出处理循环。这说明图中还有未输出的顶点，但已跳出处理循环。这说明图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不图中还剩下一些顶点，它们都有直接前驱，再也找不图中还剩下一些顶点，它们都有直接前驱，再也找不图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时到没有前驱的顶点了。这时到没有前驱的顶点了。这时到没有前驱的顶点了。这时AOVAOVA

58、OVAOV网络中必定存在有向网络中必定存在有向网络中必定存在有向网络中必定存在有向环。环。环。环。52ACM数据结构与算法课程代码：C0C1C2C3C4C5例：拓扑排序的过程例：拓扑排序的过程(a) 有向无环图有向无环图(b) 输出顶点输出顶点C4(c) 输出顶点输出顶点C0C2C5C1C0C3C4C1C2C5C3C0C2C5C1C3(d) 输出顶点输出顶点C353ACM数据结构与算法课程代码：C1C2C5(e) 输出顶点输出顶点C2C5C1(f) 输出顶点输出顶点C1C5(g) 输出顶点输出顶点C5(h) 拓扑排序完成拓扑排序完成54ACM数据结构与算法课程代码：AOV网络及其邻接表表示网络

59、及其邻接表表示C0C1C2C3C4C5 dest next C0 C1 C2 C3 0 C4 C5 0012345count data adj 130103 1 3 0 5 1 5 0 0 1 5 0在邻接表中增设了一个在邻接表中增设了一个在邻接表中增设了一个在邻接表中增设了一个countcount域，记录各个顶点域，记录各个顶点域，记录各个顶点域，记录各个顶点入度。入度为零的顶点即入度。入度为零的顶点即入度。入度为零的顶点即入度。入度为零的顶点即无前驱的顶点。无前驱的顶点。无前驱的顶点。无前驱的顶点。55ACM数据结构与算法课程代码：3）拓扑排序算法入度为入度为0的顶点即为没有前驱的顶点。的

60、顶点即为没有前驱的顶点。删除顶点及相应弧的操作可转换为弧头顶点入删除顶点及相应弧的操作可转换为弧头顶点入度减度减1。为避免重复检查入度为为避免重复检查入度为0 的顶点，在算法中使用的顶点，在算法中使用一个链式栈将入度为一个链式栈将入度为 0 的顶点链接在一起，供的顶点链接在一起，供选择和输出无前驱的顶点。只要出现入度为零选择和输出无前驱的顶点。只要出现入度为零的顶点，就将它加入栈中。的顶点，就将它加入栈中。56ACM数据结构与算法课程代码：算法描述使用这种栈的拓扑排序算法可以描述如下：使用这种栈的拓扑排序算法可以描述如下： (1) 建立入度为零的顶点栈建立入度为零的顶点栈;输出顶点计数器输出顶

61、点计数器=0 (2) 当入度为零的顶点栈不空时当入度为零的顶点栈不空时, 重复执行重复执行 从栈中取出顶点元素从栈中取出顶点元素从栈中取出顶点元素从栈中取出顶点元素, , 并输出之并输出之并输出之并输出之; ;计数器计数器计数器计数器+1+1从从从从AOVAOV网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边, , 边的边的边的边的终顶点入度减终顶点入度减终顶点入度减终顶点入度减 1;1;如果边的终顶点入度减至如果边的终顶点入度减至如果边的终顶点入度减至如果边的终顶点入度减至0, 0, 则该顶点进入度为零则该顶点进入度为零

62、则该顶点进入度为零则该顶点进入度为零的顶点栈的顶点栈的顶点栈的顶点栈; ; (3) 如果输出顶点个数少于如果输出顶点个数少于AOV网络的顶点个数网络的顶点个数, 则报告网络中存在有向环。则报告网络中存在有向环。57ACM数据结构与算法课程代码：分分分分析析析析此此此此拓拓拓拓扑扑扑扑排排排排序序序序算算算算法法法法可可可可知知知知，如如如如果果果果AOVAOV网网网网络络络络有有有有n n 个个个个顶顶顶顶点点点点，e e 条条条条边边边边，在在在在拓拓拓拓扑扑扑扑排排排排序序序序的的的的过过过过程程程程中中中中，搜搜搜搜索索索索入入入入度度度度为为为为零零零零的的的的顶顶顶顶点点点点，建建建

63、建立立立立链链链链式式式式栈栈栈栈所所所所需需需需要要要要的的的的时时时时间间间间是是是是O(O(n n) )。在在在在正正正正常常常常的的的的情情情情况况况况下下下下，有有有有向向向向图图图图有有有有 n n 个个个个顶顶顶顶点点点点，每每每每个个个个顶顶顶顶点点点点进进进进一一一一次次次次栈栈栈栈，出出出出一一一一次次次次栈栈栈栈，共共共共输输输输出出出出 n n 次次次次。顶顶顶顶点点点点入入入入度度度度减减减减一一一一的的的的运运运运算算算算共共共共执执执执行行行行了了了了 e e 次次次次。所所所所以以以以总总总总的的的的时时时时间间间间复复复复杂杂杂杂度为度为度为度为O(O(n n

64、+ +e e) )。4 4）算法分析）算法分析58ACM数据结构与算法课程代码：7.5.2 用边表示活动的网络(AOE网络)如果在如果在如果在如果在无环的带权有向图无环的带权有向图无环的带权有向图无环的带权有向图中中中中 用用用用有向边有向边有向边有向边表示一个工程中的表示一个工程中的表示一个工程中的表示一个工程中的活动活动活动活动(Activity)(Activity) 用边上用边上用边上用边上权值权值权值权值表示活动表示活动表示活动表示活动持续时间持续时间持续时间持续时间(Duration)(Duration) 用用用用顶点顶点顶点顶点表示表示表示表示事件事件事件事件 (Event)(Ev

65、ent) 则这样的有向图叫做用边表示活动的网络，则这样的有向图叫做用边表示活动的网络，则这样的有向图叫做用边表示活动的网络，则这样的有向图叫做用边表示活动的网络，简称简称简称简称 AOE (Activity On Edges) AOE (Activity On Edges) 网络网络网络网络。AOEAOEAOEAOE网络在某些工程估算方面非常有用。例如，可网络在某些工程估算方面非常有用。例如，可网络在某些工程估算方面非常有用。例如，可网络在某些工程估算方面非常有用。例如，可以使人们了解：以使人们了解：以使人们了解：以使人们了解： (1) (1) 完成整个工程至少需要多少时间完成整个工程至少需要

66、多少时间完成整个工程至少需要多少时间完成整个工程至少需要多少时间( (假设没有环假设没有环假设没有环假设没有环)? )? (2) (2) 为缩短完成工程所需的时间为缩短完成工程所需的时间为缩短完成工程所需的时间为缩短完成工程所需的时间, , 应当加快哪些活动应当加快哪些活动应当加快哪些活动应当加快哪些活动? ?59ACM数据结构与算法课程代码：在在AOE网络中网络中, 有些活动有些活动顺序进行顺序进行，有些活动，有些活动并并行进行行进行。从源点到各个顶点，以至从源点到汇点。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可的有向路径可能不止一条。这些路径的长度也可能不

67、同。完成不同路径的活动所需的时间虽然不能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个同，但只有各条路径上所有活动都完成了，整个工程才算完成。工程才算完成。因此，因此，完成整个工程所需的时间取决于从源点到完成整个工程所需的时间取决于从源点到汇点的最长路径长度汇点的最长路径长度，即在这条路径上所有活动，即在这条路径上所有活动的持续时间之和。的持续时间之和。这条路径长度最长的路径就叫这条路径长度最长的路径就叫做关键路径做关键路径(Critical Path)。1）关键路径60ACM数据结构与算法课程代码：1324a1=8a2=125678a10=12a9=6a8

68、=18a5=28a6=8a7=6a3=14a4=10要找出关键路径，必须找出要找出关键路径，必须找出关键活动关键活动，即不按期，即不按期完成就会影响整个工程完成的活动。完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动。关键路径上的所有活动都是关键活动。因此，只因此，只要找到了关键活动，就可以找到关键路径要找到了关键活动，就可以找到关键路径. 例如，下图就是一个例如，下图就是一个AOE网。网。61ACM数据结构与算法课程代码：2）如何求关键路径定义几个与计算关键活动有关的量：定义几个与计算关键活动有关的量：事事事事件件件件V Vi i 的的的的最最最最早早早早发发发发生生生生时时

69、时时间间间间VeVe( (i i) )是是是是从从从从源源源源点点点点V V0 0 到到到到顶顶顶顶点点点点V Vi i 的的的的最最最最长长长长路径长度。路径长度。路径长度。路径长度。事事事事件件件件V Vi i 的的的的最最最最迟迟迟迟发发发发生生生生时时时时间间间间VlVl i i 是是是是在在在在保保保保证证证证汇汇汇汇点点点点V Vn n 在在在在VeVe n n 时刻完成的前提下，事件时刻完成的前提下，事件时刻完成的前提下，事件时刻完成的前提下，事件V Vi i 的允许的最迟开始时间。的允许的最迟开始时间。的允许的最迟开始时间。的允许的最迟开始时间。活活活活动动动动a ak k 的

70、的的的最最最最早早早早开开开开始始始始时时时时间间间间e e k k ：设设设设活活活活动动动动a ak k 在在在在边边边边 上上上上，则则则则e e k k 是是是是从从从从源源源源点点点点V V0 0到到到到顶顶顶顶点点点点V Vi i 的的的的最最最最长长长长路路路路径径径径长长长长度度度度。因因因因此此此此, , e e k k = = VeVe i i 。活活活活动动动动a ak k 的的的的最最最最迟迟迟迟开开开开始始始始时时时时间间间间l l k k 是是是是在在在在不不不不会会会会引引引引起起起起时时时时间间间间延延延延误误误误的的的的前提下前提下前提下前提下, ,该活动允许

71、的最迟开始时间。该活动允许的最迟开始时间。该活动允许的最迟开始时间。该活动允许的最迟开始时间。 l l k k = = Vl Vl j j - - durdur() ) 其中其中其中其中, ,durdur()是完成是完成是完成是完成 a ak k 所需的时间。所需的时间。所需的时间。所需的时间。62ACM数据结构与算法课程代码：时间余量时间余量 lk - ek表示活动表示活动 ak 的最早开始时间的最早开始时间和最迟开始时间的时间余量。和最迟开始时间的时间余量。lk = ek 表示表示活动活动 ak 是没有时间余量的关键活动。是没有时间余量的关键活动。 为找出关键活动为找出关键活动, 需要求各

72、个活动的需要求各个活动的 ek 与与 lk，以判别是否，以判别是否 lk = ek. 为求得为求得 ek与与 lk，需要先求得从源点，需要先求得从源点 V0 到各到各个顶点个顶点 Vi 的的 Vei 和和 Vli。63ACM数据结构与算法课程代码： 求求Vei的递推公式的递推公式 从从从从 VeVe1 = 01 = 0开始，向前递推开始，向前递推开始，向前递推开始，向前递推 S S2, 2, j j = 2, = 2, , , n n 其中其中其中其中 S S2 2是所有指向顶点是所有指向顶点是所有指向顶点是所有指向顶点V Vi i 的有向边的有向边的有向边的有向边 的集合的集合的集合的集合

73、从从从从VlVl n n = = VeVe n n 开始，反向递推开始，反向递推开始，反向递推开始，反向递推 S S1, 1, j j= = n n-1, -1, n n-2, -2, ,1 ,1 其中其中其中其中 S S1 1是所有从顶点是所有从顶点是所有从顶点是所有从顶点V Vi i 发出的有向边发出的有向边发出的有向边发出的有向边 的集合的集合的集合的集合这两个递推公式的计算必须分别在拓扑有序及逆这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。拓扑有序的前提下进行。64ACM数据结构与算法课程代码： 算法分析算法分析 在拓扑排序求在拓扑排序求Vei和逆拓扑有序求和逆拓扑有

74、序求Vli时时, 所需时间为所需时间为O(n+e), 求各个活动的求各个活动的ek和和lk时所需时间为时所需时间为O(e), 总共花费时总共花费时间仍然是间仍然是O(n+e)。65ACM数据结构与算法课程代码：7.6 最短路径 (Shortest Path)问题提出问题提出问题提出问题提出: : 用带权的有向图表示一个交通运输网，图中：用带权的有向图表示一个交通运输网，图中：用带权的有向图表示一个交通运输网，图中：用带权的有向图表示一个交通运输网，图中： 顶点顶点顶点顶点表示城市表示城市表示城市表示城市 边边边边表示城市间的交通联系表示城市间的交通联系表示城市间的交通联系表示城市间的交通联系

75、权权权权表示沿此线路运输所花的时间或费用等表示沿此线路运输所花的时间或费用等表示沿此线路运输所花的时间或费用等表示沿此线路运输所花的时间或费用等 问题：问题：问题：问题：从某顶点出发，沿图到达另一顶点所经过的路径中，各边从某顶点出发，沿图到达另一顶点所经过的路径中，各边从某顶点出发，沿图到达另一顶点所经过的路径中，各边从某顶点出发，沿图到达另一顶点所经过的路径中，各边上权值之和最小的一条路径上权值之和最小的一条路径上权值之和最小的一条路径上权值之和最小的一条路径最短路径最短路径最短路径最短路径最短路径：最短路径：最短路径：最短路径： 如果从图中某一顶点如果从图中某一顶点如果从图中某一顶点如果从

76、图中某一顶点( (称为源点称为源点称为源点称为源点) )到达另一顶点到达另一顶点到达另一顶点到达另一顶点( (称为终点称为终点称为终点称为终点) )的路径可的路径可的路径可的路径可能不止一条，如何找到一条路径，使得沿此路径各边上的权值总能不止一条，如何找到一条路径，使得沿此路径各边上的权值总能不止一条，如何找到一条路径，使得沿此路径各边上的权值总能不止一条，如何找到一条路径，使得沿此路径各边上的权值总和达到最小。和达到最小。和达到最小。和达到最小。问题解法问题解法问题解法问题解法 单源最短路径单源最短路径单源最短路径单源最短路径 Dijkstra Dijkstra算法算法算法算法 任意顶点对之

77、间的最短路径任意顶点对之间的最短路径任意顶点对之间的最短路径任意顶点对之间的最短路径 Floyd Floyd算法算法算法算法66ACM数据结构与算法课程代码：7.6.1 单源最短路径问题问题的提法：问题的提法： 给定一个带权有向图给定一个带权有向图D与与源点源点v，求从，求从v 到到 D 中其它顶点的最短路中其它顶点的最短路径。限定各边上的权值大于或等于径。限定各边上的权值大于或等于0。为求得这些最短路径，为求得这些最短路径，Dijkstra 提出提出按按路径长度的递增次序，逐步产生最短路路径长度的递增次序，逐步产生最短路径的算法。径的算法。67ACM数据结构与算法课程代码：1) 迪杰斯特拉迪

78、杰斯特拉(Dijkstra)算法算法基本基本思想思想 按路径长度递增次序产生最短路径按路径长度递增次序产生最短路径按路径长度递增次序产生最短路径按路径长度递增次序产生最短路径: : 把把把把V V分成两组：分成两组：分成两组：分成两组： (1) S(1) S：已求出最短路径的顶点的集合已求出最短路径的顶点的集合已求出最短路径的顶点的集合已求出最短路径的顶点的集合 (2) V-S=T (2) V-S=T：尚未确定最短路径的顶点集合尚未确定最短路径的顶点集合尚未确定最短路径的顶点集合尚未确定最短路径的顶点集合 将将将将 T T 中顶点按最短路径递增的次序加入到中顶点按最短路径递增的次序加入到中顶点

79、按最短路径递增的次序加入到中顶点按最短路径递增的次序加入到S S中，中，中，中， 保证保证保证保证: : (1) (1) 从源点从源点从源点从源点V0 V0 到到到到 S S 中各顶点的最短路径长度都中各顶点的最短路径长度都中各顶点的最短路径长度都中各顶点的最短路径长度都 不大于不大于不大于不大于从从从从V0V0到到到到T T中任何顶点的最短路径长度中任何顶点的最短路径长度中任何顶点的最短路径长度中任何顶点的最短路径长度 (2) (2) 每个顶点对应一个距离值每个顶点对应一个距离值每个顶点对应一个距离值每个顶点对应一个距离值 S S中顶点：从中顶点：从中顶点：从中顶点：从V0 V0 到此顶点的

80、最短路径长度到此顶点的最短路径长度到此顶点的最短路径长度到此顶点的最短路径长度 T T中顶点：从中顶点：从中顶点：从中顶点：从V0 V0 到此顶点的只包括到此顶点的只包括到此顶点的只包括到此顶点的只包括 S S 中顶中顶中顶中顶 点作中间顶点的最短路径长度点作中间顶点的最短路径长度点作中间顶点的最短路径长度点作中间顶点的最短路径长度68ACM数据结构与算法课程代码：7.6.2 所有顶点之间的最短路径 问题的提出：问题的提出：问题的提出：问题的提出：已知一个各边权值均大于已知一个各边权值均大于已知一个各边权值均大于已知一个各边权值均大于0 0的带权有向图，的带权有向图，的带权有向图，的带权有向图

81、，对每一对顶点对每一对顶点对每一对顶点对每一对顶点 v vi i v vj j，要求求出，要求求出，要求求出，要求求出v vi i 与与与与v vj j之间的最短路径之间的最短路径之间的最短路径之间的最短路径和最短路径长度。和最短路径长度。和最短路径长度。和最短路径长度。 FloydFloydFloydFloyd算法的基本思想：算法的基本思想：算法的基本思想：算法的基本思想： 定义一个定义一个定义一个定义一个n n阶方阵序列：阶方阵序列：阶方阵序列：阶方阵序列： A A(-1)(-1), , A A(0)(0), , , , A A( (n-n-1)1). . 其中其中其中其中 A A(-1)

82、(-1) i i j j = =EdgeEdge i i j j ； A A( (k k) ) i i j j =min =min A A( (k k-1)-1) i i j j, ,A A( (k k-1)-1) i i k k+A A( (k k-1)-1) k k j j k k = 0,1, = 0,1, n n-1 -1 A A(0) (0) i i j j 是从顶点是从顶点是从顶点是从顶点v vi i 到到到到v vj j , , 中间顶点是中间顶点是中间顶点是中间顶点是v v0 0的最短路径的长度的最短路径的长度的最短路径的长度的最短路径的长度, , A A( (k k) ) i

83、 i j j 是从顶点是从顶点是从顶点是从顶点v vi i 到到到到v vj j , , 中间顶点的序号不大于中间顶点的序号不大于中间顶点的序号不大于中间顶点的序号不大于k k的最短的最短的最短的最短路径的长度路径的长度路径的长度路径的长度, , A A( (n-n-1)1) i i j j 是从顶点是从顶点是从顶点是从顶点v vi i 到到到到v vj j 的最短路径长度。的最短路径长度。的最短路径长度。的最短路径长度。69ACM数据结构与算法课程代码：70ACM数据结构与算法课程代码：本章小结理解：图的基本概念理解：图的基本概念 图的顶点集合是非空有限集合图的顶点集合是非空有限集合图的顶点

84、集合是非空有限集合图的顶点集合是非空有限集合 图的边集合可以是空集合图的边集合可以是空集合图的边集合可以是空集合图的边集合可以是空集合 图的顶点序号不是固有的图的顶点序号不是固有的图的顶点序号不是固有的图的顶点序号不是固有的掌握：图的存储表示掌握：图的存储表示 图的邻接矩阵元素个数与顶点有关，非零元素个数与图的邻接矩阵元素个数与顶点有关，非零元素个数与图的邻接矩阵元素个数与顶点有关，非零元素个数与图的邻接矩阵元素个数与顶点有关，非零元素个数与边有关边有关边有关边有关 图的邻接表既与顶点个数图的邻接表既与顶点个数图的邻接表既与顶点个数图的邻接表既与顶点个数 n n 有关，又与边数有关有关，又与边

85、数有关有关，又与边数有关有关，又与边数有关 连通无向图最多有连通无向图最多有连通无向图最多有连通无向图最多有 n(n-1)/2 n(n-1)/2 条边条边条边条边, ,最少有最少有最少有最少有n-1n-1条边条边条边条边 强连通有向图最多有强连通有向图最多有强连通有向图最多有强连通有向图最多有 n(n-1) n(n-1) 条边，最少有条边，最少有条边，最少有条边，最少有 n n 条边。条边。条边。条边。n n = 1= 1无边。无边。无边。无边。 图中顶点的度有别于树中结点的度。图中顶点的度有别于树中结点的度。图中顶点的度有别于树中结点的度。图中顶点的度有别于树中结点的度。71ACM数据结构与

86、算法课程代码：图的遍历与连通性图的遍历与连通性 深度优先搜索算法深度优先搜索算法深度优先搜索算法深度优先搜索算法 递归或用栈递归或用栈 广度优先搜索算法广度优先搜索算法广度优先搜索算法广度优先搜索算法 用队列用队列 生成树或生成森林生成树或生成森林生成树或生成森林生成树或生成森林( (掌握掌握掌握掌握构造最小生成树的方法构造最小生成树的方法构造最小生成树的方法构造最小生成树的方法) ) Prim Prim 算法算法算法算法 Kruskal Kruskal 算法算法算法算法掌握掌握 : 活动网络的拓扑排序活动网络的拓扑排序掌握掌握 : 求解关键路径的方法求解关键路径的方法理解理解 : 求解最短路径的求解最短路径的Dijkstra方法方法(掌握过程掌握过程)72ACM数据结构与算法课程代码：73ACM数据结构与算法