ACM培训资料数据结构与算法教学课件

梦 境ACM培训资料数据结构与算法课件1、不要轻言放弃，否则对不起自己。2、要冒一次险!整个生命就是一场冒险。走得最远的人，常是愿意去做，并愿意去冒险的人。“稳妥”之船，从未能从岸边走远。-戴尔卡耐基。3、人生就像一杯没有加糖的咖啡，喝起来是苦涩的，回味起来却有久久不会退去的余香。4、守业的最好办法就是不断的发展。5、当爱不能完美，我宁愿选择无悔，不管来生多么美丽，我不愿失去今生对你的记忆，我不求天长地久的美景，我只要生生世世的轮回里有你。数据结构数据结构 (DATA STRUCTURE)计算机科学与工程系计算机科学与工程系20课程代码：0600060第七章 图图的基本概念图的基本概念 图的存储表示图的存储表示 图的遍历与连通性图的遍历与连通性 最小生成树最小生成树 最短路径最短路径 活动网络活动网络30课程代码：06000607.1 图的基本概念图的定义图的定义 图是由顶点集合图是由顶点集合(vertex)及顶点间及顶点间的关系集合组成的一种数据结构的关系集合组成的一种数据结构：Graph(V,E)其中其中 V=x|x 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合；E=(x,y)|x,y V 或或 E=|x,y V&Path(x,y)是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)集合。集合。Path(x,y)表示从表示从 x 到到 y 的一条的一条通路。通路。40课程代码：0600060 有向图与无向图有向图与无向图完全图完全图50课程代码：0600060 邻接顶点邻接顶点 如果如果(u,v)是是 E(G)中的一条边，中的一条边，则称则称 u 与与 v 互为邻接顶点互为邻接顶点。子子图图 设设有有两两个个图图G(V,E)和和G(V,E),若若 V V 且且 E E,则则称称 图图G 是是图图G 的的子图。子图。60课程代码：0600060顶顶点点的的度度 一一一一个个个个顶顶顶顶点点点点v v 的的的的度度度度是是是是与与与与它它它它相相相相关关关关联联联联的的的的边边边边的的的的条条条条数，记作数，记作数，记作数，记作TD(TD(v v)。顶点顶点 v 的入度的入度 是以是以是以是以 v v 为终点为终点为终点为终点(弧头弧头弧头弧头)的有向边的条的有向边的条的有向边的条的有向边的条数数数数,记作记作记作记作 ID(ID(v v);顶点顶点顶点顶点 v v 的出度的出度的出度的出度是以是以是以是以 v v 为始点为始点为始点为始点(弧尾弧尾弧尾弧尾)的有向边的条数的有向边的条数的有向边的条数的有向边的条数,记作记作记作记作 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 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 的边。的边。的边。的边。70课程代码：0600060路径长度路径长度 非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。简单路径简单路径 若路径上各顶点若路径上各顶点若路径上各顶点若路径上各顶点 v v1 1,v v2 2,.,.,v vm m 均不互相均不互相均不互相均不互相重复重复重复重复,则称这样的路径为简单路径。则称这样的路径为简单路径。则称这样的路径为简单路径。则称这样的路径为简单路径。回路回路 若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点与最后一个顶点与最后一个顶点v vm m 重合重合重合重合,则称这样的路径为回路或环。则称这样的路径为回路或环。则称这样的路径为回路或环。则称这样的路径为回路或环。简单回路简单回路 除了第一个顶点和最后一个顶点外，除了第一个顶点和最后一个顶点外，除了第一个顶点和最后一个顶点外，除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路其余顶点不重复出现的回路叫简单回路其余顶点不重复出现的回路叫简单回路其余顶点不重复出现的回路叫简单回路 80课程代码：0600060例例157324G26例例245136G1路径：路径：1，2，3，5，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，190课程代码：06000607.2 图的存储结构1 1）存储特点）存储特点在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个记录各个顶点记录各个顶点记录各个顶点记录各个顶点信息信息信息信息的的的的顶点表；顶点表；顶点表；顶点表；还有一个还有一个还有一个还有一个表示各个顶点之间关系表示各个顶点之间关系表示各个顶点之间关系表示各个顶点之间关系的的的的邻接矩阵邻接矩阵邻接矩阵邻接矩阵。2 2）邻接矩阵）邻接矩阵 设图设图设图设图 A=(A=(V V,E E)是一个有是一个有是一个有是一个有 n n 个顶点的图，则图个顶点的图，则图个顶点的图，则图个顶点的图，则图的的的的邻接矩阵邻接矩阵邻接矩阵邻接矩阵是一个二维数组是一个二维数组是一个二维数组是一个二维数组 AAn n n n，定义：，定义：，定义：，定义：7.2.1 邻接矩阵邻接矩阵(Adjacency Matrix)表示法表示法100课程代码：0600060110课程代码：0600060 网络的邻接矩阵120课程代码：06000603）数据类型描述#define MaxVNum 100#define MaxVNum 100 /*/*最大顶点数设为最大顶点数设为最大顶点数设为最大顶点数设为100*/100*/typedef XXX VertexType;typedef XXX VertexType;/*/*顶点类型顶点类型顶点类型顶点类型*/邻接矩阵类型：邻接矩阵类型：邻接矩阵类型：邻接矩阵类型：typedef int EdgeType;typedef int EdgeType;/*/*边的权值设为整型边的权值设为整型边的权值设为整型边的权值设为整型*/typedef struct ArcCell typedef struct ArcCell VertexType adj;VertexType adj;InfoType *Info;InfoType *Info;/存弧相关信息存弧相关信息存弧相关信息存弧相关信息 ArcCell,AdjMatrixMaxVNumMaxVNum ArcCell,AdjMatrixMaxVNumMaxVNum 图类型：图类型：图类型：图类型：typedef structtypedef struct VertexType vexsMaxVNum;VertexType vexsMaxVNum;/*/*顶点表顶点表顶点表顶点表*/AdjMatrix arcs;AdjMatrix arcs;/*/*邻接矩阵，即边表邻接矩阵，即边表邻接矩阵，即边表邻接矩阵，即边表*/int vexnum,arcnum;int vexnum,arcnum;/*/*图的顶点数和边数图的顶点数和边数图的顶点数和边数图的顶点数和边数*/Mgragh;Mgragh;/*Maragh/*Maragh是以邻接矩阵存储的图是以邻接矩阵存储的图是以邻接矩阵存储的图是以邻接矩阵存储的图*/130课程代码：06000604）图的创建 思路：思路：思路：思路：140课程代码：06000607.2.2 邻接表(Adjacency List)1)1)存储特点存储特点 对于图对于图对于图对于图GG中的每个顶点中的每个顶点中的每个顶点中的每个顶点vivi，把所有邻接于，把所有邻接于，把所有邻接于，把所有邻接于vivi的顶点的顶点的顶点的顶点vjvj链成一链成一链成一链成一个单链表，这个单链表称为顶点个单链表，这个单链表称为顶点个单链表，这个单链表称为顶点个单链表，这个单链表称为顶点vivi的邻接表；的邻接表；的邻接表；的邻接表；将所有点的邻接表表头放到数组中，就构成了图的邻接表将所有点的邻接表表头放到数组中，就构成了图的邻接表将所有点的邻接表表头放到数组中，就构成了图的邻接表将所有点的邻接表表头放到数组中，就构成了图的邻接表 150课程代码：0600060特点特点无向图中顶点无向图中顶点ViVi的度为第的度为第i i个单链表中的结点数个单链表中的结点数有向图中有向图中 顶点顶点ViVi的出度为第的出度为第i i个单链表中的结点个数个单链表中的结点个数 顶点顶点ViVi的入度为整个的入度为整个单链表中邻接点域值是单链表中邻接点域值是i i的结点个数的结点个数逆邻接表：有向图中对每个结点建立以逆邻接表：有向图中对每个结点建立以ViVi为头的弧的单为头的弧的单链表链表例例G1bdac1234acdbvexdatafirstarc 4 1 1 3adjvexnext160课程代码：0600060170课程代码：06000602）数据类型描述define MaxVerNum 100 /*define MaxVerNum 100 /*最大顶点数为最大顶点数为最大顶点数为最大顶点数为100*/100*/邻接表类型邻接表类型邻接表类型邻接表类型 ：typedef struct ArcNodetypedef struct ArcNode int adjvex;/*int adjvex;/*邻接点域邻接点域邻接点域邻接点域*/InfoType *Info;/*InfoType *Info;/*表示边上信息的域表示边上信息的域表示边上信息的域表示边上信息的域info*/info*/struct ArcNode*next;/*struct ArcNode*next;/*指向下一个邻接点的指针域指向下一个邻接点的指针域指向下一个邻接点的指针域指向下一个邻接点的指针域*/ArcNode;ArcNode;表头结点类型表头结点类型表头结点类型表头结点类型 ：typedef struct Vnodetypedef struct Vnode VertexType vertex;/*VertexType vertex;/*顶点域顶点域顶点域顶点域*/ArcNode *firstedge;/*ArcNode *firstedge;/*边表头指针边表头指针边表头指针边表头指针*/Vnode,AdjList MaxVertexNum;Vnode,AdjList MaxVertexNum;图的类型图的类型图的类型图的类型 ：typedef structtypedef struct AdjList vertices;/*AdjList vertices;/*邻接表邻接表邻接表邻接表*/int vexnum,arcnum;/*int vexnum,arcnum;/*顶点数和边数顶点数和边数顶点数和边数顶点数和边数*/ALGraph;/*ALGraph ALGraph;/*ALGraph是以邻接表方式存储的图类型是以邻接表方式存储的图类型是以邻接表方式存储的图类型是以邻接表方式存储的图类型*/180课程代码：06000607.2.3 十字链表(Orthogonal List)十字链表是十字链表是十字链表是十字链表是有向图有向图有向图有向图的另一种链式存储结构，它实际的另一种链式存储结构，它实际的另一种链式存储结构，它实际的另一种链式存储结构，它实际上是上是上是上是邻接表邻接表邻接表邻接表与与与与逆邻接表逆邻接表逆邻接表逆邻接表的结合的结合的结合的结合1)1)存储特点存储特点图中每一条弧有一个结点，把弧头相同的弧连图中每一条弧有一个结点，把弧头相同的弧连图中每一条弧有一个结点，把弧头相同的弧连图中每一条弧有一个结点，把弧头相同的弧连在同一链表上在同一链表上在同一链表上在同一链表上,弧尾相同的弧也连在同一链表上。弧尾相同的弧也连在同一链表上。弧尾相同的弧也连在同一链表上。弧尾相同的弧也连在同一链表上。结点结构为：结点结构为：结点结构为：结点结构为：顶点结点为链表头结点，其结构为：顶点结点为链表头结点，其结构为：顶点结点为链表头结点，其结构为：顶点结点为链表头结点，其结构为：190课程代码：06000607.2.4 邻接多重表(Adjacency Multilist)邻接多重表是邻接多重表是无向图无向图的另一种链式存储结构的另一种链式存储结构1)1)存储特点存储特点 图中每一条边用一个边结点表示，其结构为：图中每一条边用一个边结点表示，其结构为：图中每一条边用一个边结点表示，其结构为：图中每一条边用一个边结点表示，其结构为：每个顶点用一个结点表示，其结构为：每个顶点用一个结点表示，其结构为：每个顶点用一个结点表示，其结构为：每个顶点用一个结点表示，其结构为：mark ivex ilink jvex jlinkdata firstedge200课程代码：0600060 在邻接多重表中在邻接多重表中在邻接多重表中在邻接多重表中,所有依附于同一个顶点的边都所有依附于同一个顶点的边都所有依附于同一个顶点的边都所有依附于同一个顶点的边都链接在同一个单链表中。链接在同一个单链表中。链接在同一个单链表中。链接在同一个单链表中。邻接多重表的结构邻接多重表的结构邻接多重表的结构邻接多重表的结构例例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2210课程代码：06000607.3 图的遍历与连通性从图中某一顶点出发，沿着一些边访遍图中从图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，所有的顶点，且使每个顶点仅被访问一次，叫做叫做图的遍历图的遍历(Graph Traversal)。为了避免重复访问，可设置一个标志顶点是为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组否被访问过的辅助数组 visited ，它的初始，它的初始状态为状态为 0，在图的遍历过程中，一旦某一个，在图的遍历过程中，一旦某一个顶点顶点 i 被访问，就立即让被访问，就立即让 visited i 为为 1，防，防止它被多次访问。止它被多次访问。220课程代码：06000607.3.1 深度优先搜索DFS1）基本思想：）基本思想：任选图中一个顶点任选图中一个顶点任选图中一个顶点任选图中一个顶点 v v,访问此顶点访问此顶点访问此顶点访问此顶点,并作访问标记。并作访问标记。并作访问标记。并作访问标记。从从从从 v v 出发，访问它的任一未被访问过的邻接顶点出发，访问它的任一未被访问过的邻接顶点出发，访问它的任一未被访问过的邻接顶点出发，访问它的任一未被访问过的邻接顶点 w w ，作访问标记，并以，作访问标记，并以，作访问标记，并以，作访问标记，并以 w w 为新的出发点，继续进为新的出发点，继续进为新的出发点，继续进为新的出发点，继续进行深度优先搜索。行深度优先搜索。行深度优先搜索。行深度优先搜索。当某个顶点的所有邻接顶点都被访问过后，则退当某个顶点的所有邻接顶点都被访问过后，则退当某个顶点的所有邻接顶点都被访问过后，则退当某个顶点的所有邻接顶点都被访问过后，则退回到前一次刚访问过的顶点回到前一次刚访问过的顶点回到前一次刚访问过的顶点回到前一次刚访问过的顶点k k，从，从，从，从k k的另一个没有的另一个没有的另一个没有的另一个没有被访问的邻接顶点出发进行深度优先搜索。被访问的邻接顶点出发进行深度优先搜索。被访问的邻接顶点出发进行深度优先搜索。被访问的邻接顶点出发进行深度优先搜索。重复上述过程重复上述过程重复上述过程重复上述过程,直到图中所有顶点都被访问过为止直到图中所有顶点都被访问过为止直到图中所有顶点都被访问过为止直到图中所有顶点都被访问过为止230课程代码：0600060n n深度优先搜索的示例深度优先搜索的示例例例V1V2V4V5V3V7V6V8深度遍历：深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V3 V6 V7 V5240课程代码：0600060n n深度优先搜索的示例深度优先搜索的示例遍历结果：遍历结果：A A、B B、D D、C C例例250课程代码：06000602）算法实现难点：难点：如何标记已访问结点如何标记已访问结点如何标记已访问结点如何标记已访问结点v?v?如何查找如何查找如何查找如何查找 v v 的的的的所有邻接点？所有邻接点？所有邻接点？所有邻接点？解决办法：解决办法：设置一个布尔向量数组设置一个布尔向量数组设置一个布尔向量数组设置一个布尔向量数组visitednvisitedn，初值为，初值为，初值为，初值为0 0。若序号为若序号为若序号为若序号为 i i 的结点已被访问过，则的结点已被访问过，则的结点已被访问过，则的结点已被访问过，则visitedi=1visitedi=1。根据图的存储方式不同，采取相应方法查找：根据图的存储方式不同，采取相应方法查找：根据图的存储方式不同，采取相应方法查找：根据图的存储方式不同，采取相应方法查找：邻接矩阵：邻接矩阵：邻接矩阵：邻接矩阵：v vi i 的邻接点是邻接矩阵中第的邻接点是邻接矩阵中第的邻接点是邻接矩阵中第的邻接点是邻接矩阵中第i i 行上非行上非行上非行上非0 0元素对应的列值，若元素对应的列值，若元素对应的列值，若元素对应的列值，若Aij0Aij0，则，则，则，则v vj j为为为为v vi i邻接点。邻接点。邻接点。邻接点。邻接表：是以邻接表：是以邻接表：是以邻接表：是以G.verticesiG.verticesi为表头结点的单链表上为表头结点的单链表上为表头结点的单链表上为表头结点的单链表上的所有结点。的所有结点。的所有结点。的所有结点。260课程代码：0600060V1V2V4V5V3V7V6V8例例1234V1V3V4V2vexdatafirstarc 2 7 8 3adjvexnext5V5 6 4 8 2V6V7V8678 7深度遍历：深度遍历：V1 V3 V7 V6 V2 V4 V8 V5270课程代码：06000603）算法分析图中有图中有 n 个顶点，个顶点，e 条边。条边。由于总共有由于总共有 2e 个边结点，所以扫描边的时个边结点，所以扫描边的时间为间为O(e)。而且对所有顶点递归访问。而且对所有顶点递归访问1次，次，所以遍历图的时间复杂性为所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为的所有的边，所需时间为O(n)，则遍历图中，则遍历图中所有的顶点所需的时间为所有的顶点所需的时间为O(n2)。280课程代码：06000607.3.2 广度优先搜索 BFS1 1）基本思想：）基本思想：任选图中一个顶点任选图中一个顶点任选图中一个顶点任选图中一个顶点 v v，访问此顶点，并作访问，访问此顶点，并作访问，访问此顶点，并作访问，访问此顶点，并作访问标记。标记。标记。标记。从从从从 v v 出发，依次访问出发，依次访问出发，依次访问出发，依次访问 v v 的各个未曾被访问过的的各个未曾被访问过的的各个未曾被访问过的的各个未曾被访问过的邻接顶点邻接顶点邻接顶点邻接顶点 w w1 1,w w2 2,w wt t，并作访问标记。，并作访问标记。，并作访问标记。，并作访问标记。然后再顺序访问然后再顺序访问然后再顺序访问然后再顺序访问 w w1 1,w w2 2,w wt t 的所有还未被访的所有还未被访的所有还未被访的所有还未被访问过的邻接顶点，并作访问标记。问过的邻接顶点，并作访问标记。问过的邻接顶点，并作访问标记。问过的邻接顶点，并作访问标记。如此做下去如此做下去如此做下去如此做下去,直到图中所有顶点都被访问到直到图中所有顶点都被访问到直到图中所有顶点都被访问到直到图中所有顶点都被访问到为止为止为止为止290课程代码：0600060n n广度优先搜索的示例广度优先搜索的示例例例V1V2V4V5V3V7V6V8例例广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V6 V7 V8 V5300课程代码：0600060n n广度优先搜索的示例广度优先搜索的示例遍历结果：遍历结果：A A、B B、C C、D D例例310课程代码：0600060 为了实现逐层访问，算法中使用了一个队列，以记忆为了实现逐层访问，算法中使用了一个队列，以记忆为了实现逐层访问，算法中使用了一个队列，以记忆为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层正在访问的这一层和上一层的顶点，以便于向下一层正在访问的这一层和上一层的顶点，以便于向下一层正在访问的这一层和上一层的顶点，以便于向下一层访问。访问。访问。访问。2）算法实现开始开始标志数组初始化标志数组初始化Vi=1Vi访问过访问过BFSVi=Vi+1Vi=Vexnums结束结束NNYY320课程代码：0600060 BFSBFS开始开始访问访问Vi,置置标志标志求求V邻接点邻接点WW存在吗存在吗V下一邻接点下一邻接点WW访问过访问过结束结束NYNY初始化队列初始化队列Vi入队入队队列空吗队列空吗队头队头V出队出队访问访问W,置置标志标志W入队入队NaaY330课程代码：0600060如果使用邻接表表示图，则循环的总时间如果使用邻接表表示图，则循环的总时间代价为代价为 d1+d2+dn=O(e)，其中的，其中的 di 是顶点是顶点 i 的度。的度。如果使用邻接矩阵，则对于每一个被访问如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的过的顶点，循环要检测矩阵中的 n 个元素，个元素，总的时间代价为总的时间代价为O(n2)。3 3）算法分析）算法分析340课程代码：06000607.4 图的连通性与生成树7.4.1 图的连通性问题图的连通性问题连通图与连通分量连通图与连通分量 在在无向图无向图中中,若从顶点若从顶点v1到顶点到顶点v2有路径有路径,则称顶点则称顶点v1与与v2是连通的。是连通的。如果图中如果图中任意一对顶点任意一对顶点都是连通的都是连通的,则称此则称此图是图是连通图连通图。非连通图的极大连通子图叫做。非连通图的极大连通子图叫做连通分量连通分量。强连通图与强连通分量强连通图与强连通分量 在在有向图有向图中中,若对若对于于每一对顶点每一对顶点vi和和vj,都存在一条都存在一条从从vi到到vj和和从从vj到到vi的路径的路径,则称此图是则称此图是强连通图强连通图。非强连。非强连通图的极大强连通子图叫做通图的极大强连通子图叫做强连通分量强连通分量。350课程代码：0600060连通图连通图例例245136强连通图强连通图356例例非连通图非连通图连通分量连通分量例例245136360课程代码：06000607.4.2 最小生成树 1）图的生成树）图的生成树连通图连通图连通图连通图GG的一个的一个的一个的一个子图子图子图子图如果是一棵包含如果是一棵包含如果是一棵包含如果是一棵包含GG的所有顶点的所有顶点的所有顶点的所有顶点的树（所有顶点均由边连接在一起，但不存在回的树（所有顶点均由边连接在一起，但不存在回的树（所有顶点均由边连接在一起，但不存在回的树（所有顶点均由边连接在一起，但不存在回路路路路,有有有有n-1n-1条边），则该子图称为条边），则该子图称为条边），则该子图称为条边），则该子图称为GG的的的的生成树生成树生成树生成树。生成树生成树生成树生成树是连通图的是连通图的是连通图的是连通图的极小连通子图极小连通子图极小连通子图极小连通子图。所谓极小是指：。所谓极小是指：。所谓极小是指：。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若在树中任意增加一条边，则将出现一个回路；若在树中任意增加一条边，则将出现一个回路；若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。若去掉一条边，将会使之变成非连通图。若去掉一条边，将会使之变成非连通图。若去掉一条边，将会使之变成非连通图。使用不同的遍历图的方法，可以得到不同的生成树使用不同的遍历图的方法，可以得到不同的生成树使用不同的遍历图的方法，可以得到不同的生成树使用不同的遍历图的方法，可以得到不同的生成树370课程代码：0600060说明说明一个图可以有许多棵不同的生成树一个图可以有许多棵不同的生成树一个图可以有许多棵不同的生成树一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：所有生成树具有以下共同特点：所有生成树具有以下共同特点：所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图生成树是图的极小连通子图生成树是图的极小连通子图生成树是图的极小连通子图 一个有一个有一个有一个有n n个顶点的连通图的生成树有个顶点的连通图的生成树有个顶点的连通图的生成树有个顶点的连通图的生成树有n-1n-1条边条边条边条边 生成树中任意两个顶点间的路径是唯一的生成树中任意两个顶点间的路径是唯一的生成树中任意两个顶点间的路径是唯一的生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路含含含含n n个顶点个顶点个顶点个顶点n-1n-1条边的图不一定是生成树条边的图不一定是生成树条边的图不一定是生成树条边的图不一定是生成树GHKI380V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8390课程代码：0600060例例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林深度优先生成森林400课程代码：0600060n n 问题提出问题提出 要在要在要在要在n n个城市间建立通信联络网，个城市间建立通信联络网，个城市间建立通信联络网，个城市间建立通信联络网，顶点顶点顶点顶点 城市城市城市城市 权权权权 城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价 生成树各边的权值总和称为生成树各边的权值总和称为生成树的权生成树的权。权。权最小的生成树称为最小的生成树称为最小生成树。最小生成树。2)构造最小生成树 n n 问题分析问题分析问题分析问题分析uu n n个城市间个城市间个城市间个城市间,最多可设置最多可设置最多可设置最多可设置n(n-1)/2n(n-1)/2条线路条线路条线路条线路uu n n个城市间建立通信网个城市间建立通信网个城市间建立通信网个城市间建立通信网,只需只需只需只需n-1n-1条线路条线路条线路条线路uu 问题转化为：如何在可能的线路中选问题转化为：如何在可能的线路中选问题转化为：如何在可能的线路中选问题转化为：如何在可能的线路中选择择择择n-1n-1条，能把所有城市（顶点）均连起条，能把所有城市（顶点）均连起条，能把所有城市（顶点）均连起条，能把所有城市（顶点）均连起来，且总耗费各边权值之和）最小来，且总耗费各边权值之和）最小来，且总耗费各边权值之和）最小来，且总耗费各边权值之和）最小1654327131791812752410410课程代码：0600060最小生成树的重要性质：最小生成树的重要性质：设设 G=G=（V V，E E）是一个连通网络，）是一个连通网络，U U是顶点集是顶点集V V的一个真子集。若（的一个真子集。若（u u，v v）是）是G G中所有的一个顶点在中所有的一个顶点在U,U,另一个顶点不在另一个顶点不在 U U 的边中，的边中，具有最小权值具有最小权值的一条的一条边，则一定存在边，则一定存在 G G 的一棵最小生成树包括此边。的一棵最小生成树包括此边。uvUVU420课程代码：0600060 普里姆(Prim)算法普里姆算法的基本思想：普里姆算法的基本思想：普里姆算法的基本思想：普里姆算法的基本思想：假设图假设图假设图假设图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)，将其顶点加入到生成，将其顶点加入到生成，将其顶点加入到生成，将其顶点加入到生成树的顶点集合树的顶点集合树的顶点集合树的顶点集合U U中。中。中。中。以后每一步从以后每一步从以后每一步从以后每一步从一个顶点在一个顶点在一个顶点在一个顶点在U U中中中中，而，而，而，而另一个顶点不在另一个顶点不在另一个顶点不在另一个顶点不在U U中中中中的的的的各条边中选择各条边中选择各条边中选择各条边中选择权值最小的边权值最小的边权值最小的边权值最小的边(u u,v v),把它的顶点加入到把它的顶点加入到把它的顶点加入到把它的顶点加入到集集集集合合合合U U中。中。中。中。如此继续下去，直到网络中的所有顶点都加入到生成树如此继续下去，直到网络中的所有顶点都加入到生成树如此继续下去，直到网络中的所有顶点都加入到生成树如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合顶点集合顶点集合顶点集合U U中为止。中为止。中为止。中为止。430课程代码：0600060 算法实现算法实现:(略略)算法分析：算法分析：上述算法的初始化时间是上述算法的初始化时间是O(1)O(1)，k k循环中有两循环中有两个循环语句，其时间大致为：个循环语句，其时间大致为：令令O(1)O(1)为某一正常数为某一正常数C C，展开上述求和公式可，展开上述求和公式可知其数量级仍是知其数量级仍是 n n 的平方。所以，整个算法的时的平方。所以，整个算法的时间复杂性是间复杂性是O(nO(n2 2)440课程代码：0600060 克鲁斯卡尔(Kruskal)算法克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：设有一个有设有一个有设有一个有设有一个有 n n 个顶点的连通网络个顶点的连通网络个顶点的连通网络个顶点的连通网络 G G=V V,E E ，最初先构造一个只有最初先构造一个只有最初先构造一个只有最初先构造一个只有 n n 个顶点，没有边的非连个顶点，没有边的非连个顶点，没有边的非连个顶点，没有边的非连通图通图通图通图 T T=V V,图中每个顶点自成一个连通图中每个顶点自成一个连通图中每个顶点自成一个连通图中每个顶点自成一个连通分量。分量。分量。分量。在在在在 E E 中选取一条具有中选取一条具有中选取一条具有中选取一条具有最小权值的边最小权值的边最小权值的边最小权值的边(u,v)(u,v)，若该，若该，若该，若该边的两个顶点边的两个顶点边的两个顶点边的两个顶点落在两个不同的连通分量落在两个不同的连通分量落在两个不同的连通分量落在两个不同的连通分量上，则上，则上，则上，则将此边将此边将此边将此边加入到加入到加入到加入到 T T 中中中中；否则将此边舍去，重新选；否则将此边舍去，重新选；否则将此边舍去，重新选；否则将此边舍去，重新选择一条权值最小的边。择一条权值最小的边。择一条权值最小的边。择一条权值最小的边。如此上步，直到如此上步，直到如此上步，直到如此上步，直到 T T 中所有顶点在同一个连通分中所有顶点在同一个连通分中所有顶点在同一个连通分中所有顶点在同一个连通分量上为止。量上为止。量上为止。量上为止。450课程代码：0600060应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程例例165432651356642516543212345460课程代码：06000607.5 有向无环图及其应用计划、施工过程、生产流程、程序流程等计划、施工过程、生产流程、程序流程等都是都是“工程工程”。除了很小的工程外，一般。除了很小的工程外，一般都把工程分为若干个叫做都把工程分为若干个叫做“活动活动”的子工的子工程。程。例如，计算机专业学生的学习就是一个工例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些活动。其中有些课程要求先修课程，有些则不要求。些则不要求。7.5.1 活动网络活动网络(Activity Network)用用顶点顶点表示活动的网络表示活动的网络 (AOV(AOV网络网络)470课程代码：0600060 C C1 1 高等数学高等数学高等数学高等数学 C C2 2 程序设计基础程序设计基础程序设计基础程序设计基础 C 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 480课程代码：0600060学生课程学习工程图学生课程学习工程图490课程代码：0600060可以用可以用可以用可以用有向图有向图有向图有向图表示一个工程。在这种有向图中，表示一个工程。在这种有向图中，表示一个工程。在这种有向图中，表示一个工程。在这种有向图中，用顶点表示活动用顶点表示活动用顶点表示活动用顶点表示活动，用有向边用有向边用有向边用有向边 表示活动间表示活动间表示活动间表示活动间的优先关系，的优先关系，的优先关系，的优先关系，V Vi i 必须先于活动必须先于活动必须先于活动必须先于活动V Vj j 进行。这种有进行。这种有进行。这种有进行。这种有向图叫做向图叫做向图叫做向图叫做顶点表示活动的顶点表示活动的顶点表示活动的顶点表示活动的AOVAOV网络网络网络网络(Activity (Activity On Vertices)On Vertices)。在在在在AOVAOV网络中，如果活动网络中，如果活动网络中，如果活动网络中，如果活动V Vi i 必须在活动必须在活动必须在活动必须在活动V Vj j 之前之前之前之前进行，则存在有向边进行，则存在有向边进行，则存在有向边进行，则存在有向边 ，AOVAOV网络中不网络中不网络中不网络中不能出现有向回路，即有向环。在能出现有向回路，即有向环。在能出现有向回路，即有向环。在能出现有向回路，即有向环。在AOVAOV网络中如网络中如网络中如网络中如果出现了有向环，则意味着某项活动应以自己果出现了有向环，则意味着某项活动应以自己果出现了有向环，则意味着某项活动应以自己果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的作为先决条件。因此，对给定的作为先决条件。因此，对给定的作为先决条件。因此，对给定的AOVAOV网络，必网络，必网络，必网络，必须先判断它须先判断它须先判断它须先判断它是否存在有向环。是否存在有向环。是否存在有向环。是否存在有向环。500课程代码：0600060检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构网络构造它的拓扑有序序列。即将各个顶点造它的拓扑有序序列。即将各个顶点(代表各个活动代表各个活动)排列成一个线性有序的排列成一个线性有序的序列，使得序列，使得AOV网络中所有应存在的前网络中所有应存在的前驱和后继关系都能得到满足。驱和后继关系都能得到满足。拓扑排序：拓扑排序：从某个集合上的一个从某个集合上的一个偏序偏序得得到该集合上的一个到该集合上的一个全序全序，这个操作称为，这个操作称为拓扑排序。拓扑排序。1）拓扑排序510课程代码：0600060例如，对学生选课工程图进行拓扑排序，得到的例如，对学生选课工程图进行拓扑排序，得到的例如，对学生选课工程图进行拓扑排序，得到的例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为拓扑有序序列为拓扑有序序列为拓扑有序序列为 C C1 1,C,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 6520课程代码：06000602）进行拓扑排序的方法 输入输入输入输入AOVAOVAOVAOV网络，令网络，令网络，令网络，令 n n n n 为顶点个数为顶点个数为顶点个数为顶点个数在在在在AOVAOVAOVAOV网络中选一个网络中选一个网络中选一个网络中选一个没有直接前驱没有直接前驱没有直接前驱没有直接前驱的顶点（即此顶点的顶点（即此顶点的顶点（即此顶点的顶点（即此顶点入度为入度为入度为入度为0 0 0 0）,并输出之；并输出之；并输出之；并输出之；从图中从图中从图中从图中删删删删去该去该去该去该顶点顶点顶点顶点,同时同时同时同时删删删删去所有它发出的去所有它发出的去所有它发出的去所有它发出的有向边有向边有向边有向边;重复以上两步重复以上两步重复以上两步重复以上两步,直到直到直到直到全部顶点均已输出，拓扑有序序列形成，拓扑排序全部顶点均已输出，拓扑有序序列形成，拓扑排序全部顶点均已输出，拓扑有序序列形成，拓扑排序全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或完成；或完成；或完成；或图中还有未输出的顶点，但已跳出处理循环。这说图中还有未输出的顶点，但已跳出处理循环。这说图中还有未输出的顶点，但已跳出处理循环。这说图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找明图中还剩下一些顶点，它们都有直接前驱，再也找明图中还剩下一些顶点，它们都有直接前驱，再也找明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时不到没有前驱的顶点了。这时不到没有前驱的顶点了。这时不到没有前驱的顶点了。这时AOVAOVAOVAOV网络中必定存在有网络中必定存在有网络中必定存在有网络中必定存在有向环。向环。向环。向环。530课程代码：0600060C0C1C2C3C4C5例：拓扑排序的过程例：拓扑排序的过程(a)有向无环图有向无环图(b)输出顶点输出顶点C4(c)输出顶点输出顶点C0C2C5C1C0C3C4C1C2C5C3C0C2C5C1C3(d)输出顶点输出顶点C3540课程代码：0600060C1C2C5(e)输出顶点输出顶点C2C5C1(f)输出顶点输出顶点C1C5(g)输出顶点输出顶点C5(h)拓扑排序完成拓扑排序完成550课程代码：0600060AOV网络及其邻接表表示网络及其邻接表表示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域，记录各个顶点域，记录各个顶点域，记录各个顶点域，记录各个顶点入度。入度为零的顶点即入度。入度为零的顶点即入度。入度为零的顶点即入度。入度为零的顶点即无前驱的顶点。无前驱的顶点。无前驱的顶点。无前驱的顶点。560课程代码：06000603）拓扑排序算法入度为入度为0的顶点即为没有前驱的顶点。的顶点即为没有前驱的顶点。删除顶点及相应弧的操作可转换为弧头顶点入删除顶点及相应弧的操作可转换为弧头顶点入度减度减1。为避免重复检查入度为为避免重复检查入度为0 的顶点，在算法中使用的顶点，在算法中使用一个链式栈将入度为一个链式栈将入度为 0 的顶点链接在一起，供的顶点链接在一起，供选择和输出无前驱的顶点。只要出现入度为零选择和输出无前驱的顶点。只要出现入度为零的顶点，就将它加入栈中。的顶点，就将它加入栈中。570课程代码：0600060算法描述使用这种栈的拓扑排序算法可以描述如下：使用这种栈的拓扑排序算法可以描述如下：(1)建立入度为零的顶点栈建立入度为零的顶点栈;输出顶点计数器输出顶点计数器=0 (2)当入度为零的顶点栈不空时当入度为零的顶点栈不空时,重复执行重复执行 从栈中取出顶点元素从栈中取出顶点元素从栈中取出顶点元素从栈中取出顶点元素,并输出之并输出之并输出之并输出之;计数器计数器计数器计数器+1+1从从从从AOVAOV网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边,边的边的边的边的终顶点入度减终顶点入度减终顶点入度减终顶点入度减 1;1;如果边的终顶点入度减至如果边的终顶点入度减至如果边的终顶点入度减至如果边的终顶点入度减至0,0,则该顶点进入度为零则该顶点进入度为零则该顶点进入度为零则该顶点进入度为零的顶点栈的顶点栈的顶点栈的顶点栈;(3)如果输出顶点个数少于如果输出顶点个数少于AOV网络的顶点个数网络的顶点个数,则报告网络中存在有向环。则报告网络中存在有向环。580课程代码：0600060分分分分析析析析此此此此拓拓拓拓扑扑扑扑排排排排序序序序算算算算法法法法可可可可知知知知，如如如如果果果果AOVAOV网网网网络络络络有有有有n n 个个个个顶顶顶顶点点点点，e e 条条条条边边边边，在在在在拓拓拓拓扑扑扑扑排排排排序序序序的的的的过过过过程程程程中中中中，搜搜搜搜索索索索入入入入度度度度为为为为零零零零的的的的顶顶顶顶点点点点，建建建建立立立立链链链链式式式式栈栈栈栈所所所所需需需需要要要要的的的的时时时时间间间间是是是是O(O(n n)。在在在在正正正正常常常常的的的的情情情情况况况况下下下下，有有有有向向向向图图图图有有有有 n n 个个个个顶顶顶顶点点点点，每每每每个个个个顶顶顶顶点点点点进进进进一一一一次次次次栈栈栈栈，出出出出一一一一次次次次栈栈栈栈，共共共共输输输输出出出出 n n 次次次次。顶顶顶顶点点点点入入入入度度度度减减减减一一一一的的的的运运运运算算算算共共共共执执执执行行行行了了了了 e e 次次次次。所所所所以以以以总总总总的的的的时时时时间间间间复复复复杂杂杂杂度为度为度为度为O(O(n n+e e)。4 4）算法分析）算法分析590课程代码：06000607.5.2 用边表示活动的网络(AOE网络)如果在如果在如果在如果在无环的带权有向图无环的带权有向图无环的带权有向图无环的带权有向图中中中中 用用用用有向边有向边有向边有向边表示一个工程中的表示一个工程中的表示一个工程中的表示一个工程中的活动活动活动活动(Activity)(Activity)用边上用边上用边上用边上权值权值权值权值表示活动表示活动表示活动表示活动持续时间持续时间持续时间持续时间(Duration)(Duration)用用用用顶点顶点顶点顶点表示表示表示表示事件事件事件事件 (Event)(Event)则这样的有向图叫做用边表示活动的网络，则这样的有向图叫做用边表示活动的网络，则这样的有向图叫做用边表示活动的网络，则这样的有向图叫做用边表示活动的网络，简称简称简称简称 AOE(Activity On Edges)AOE(Activity On Edges)网络网络网络网络。AOEAOEAOEAOE网络在某些工程估算方面非常有用。例如，可网络在某些工程估算方面非常有用。例如，可网络在某些工程估算方面非常有用。例如，可网络在某些工程估算方面非常有用。例如，可以使人们了解：以使人们了解：以使人们了解：以使人们了解：(1)(1)完成整个工程至少需要多少时间完成整个工程至少需要多少时间完成整个工程至少需要多少时间完成整个工程至少需要多少时间(假设没有环假设没有环假设没有环假设没有环)?)?(2)(2)为缩短完成工程所需的时间为缩短完成工程所需的时间为缩短完成工程所需的时间为缩短完成工程所需的时间,应当加快哪些活动应当加快哪些活动应当加快哪些活动应当加快哪些活动?600课程代码：0600060在在AOE网络中网络中,有些活动有些活动顺序进行顺序进行，有些活动，有些活动并并行进行行进行。从源点到各个顶点，以至从源点到汇点。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个同，但只有各条路径上所有活动都完成了，整个工程才算完成。工程才算完成。因此，因此，完成整个工程所需的时间取决于从源点到完成整个工程所需的时间取决于从源点到汇点的最长路径长度汇点的最长路径长度，即在这条路径上所有活动，即在这条路径上所有活动的持续时间之和。的持续时间之和。这条路径长度最长的路径就叫这条路径长度最长的路径就叫做关键路径做关键路径(Critical Path)。1）关键路径610课程代码：06000601324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=10要找出关键路径，必须找出要找出关键路径，必须找出关键活动关键活动，即不按期，即不按期完成就会影响整个工程完成的活动。完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动。关键路径上的所有活动都是关键活动。因此，只因此，只要找到了关键活动，就可以找到关键路径要找到了关键活动，就可以找到关键路径.例如，下图就是一个例如，下图就是一个AOE网。网。620课程代码：06000602）如何求关键路径定义几个与计算关键活动有关的量：定义几个与计算关键活动有关的量：事事事事件件件件V Vi i 的的的的最最最最早早早早发发发发生生生生时时时时间间间间VeVe(i i)是是是是从从从从源源源源点点点点V V0 0 到到到到顶顶顶顶点点点点V Vi i 的的的的最最最最长长长长路径长度。路径长度。路