1、1数数 据据 结结 构构（第八章第八章 图图）Data Structures胡学钢胡学钢 张张 晶晶计算机与信息学院计算机与信息学院 20092009年年2 2月月2第八章第八章 图图(Graph)第八章第八章 图（图（Graph)8.1 基本概念和运算 8.2 图的存储 8.3 图的遍历 8.4 最小生成树 8.5 有向无环图的应用 8.6 最短路径3 8.1 基本概念和运算 o图图 由顶点集由顶点集V和连接顶点的弧集和连接顶点的弧集E所组成的结构，所组成的结构，记作记作 G=(V,E)。其中弧的形式为其中弧的形式为，表示从顶点表示从顶点Vi到到Vj之间有一条弧，图形表示为：之间有一条弧，图
2、形表示为：Vi Vj -有向图有向图例例：如右图中的：如右图中的G1就是一个有向图：就是一个有向图：其中：其中：顶点集合顶点集合 V=1，2，3，4 弧集弧集 E=,2134图图G1 有向图示例有向图示例4 8.1 基本概念和运算 如果顶点间的关系是相互的，如果顶点间的关系是相互的，即弧的两端没有方向，则图为即弧的两端没有方向，则图为无向图。无向图。其中的弧称为其中的弧称为边。边。边的边的形式形式为为(Vi,Vj)，图形表示为：图形表示为：Vi Vj例例：如右图中的：如右图中的G2就是一个无向图：就是一个无向图：其中：其中：顶点集合顶点集合 V=1，2，3，4 边集边集 E=（1,2）,（1,
3、3）,（1,4）（2,4）,（3,4）2134图图G2 无向图示例无向图示例58.1 基本概念和运算 若若G中每条边（弧）对应一个数值中每条边（弧）对应一个数值表示关系的程度，则称图表示关系的程度，则称图G为为网络网络。例例：图图G3 就是一个网络就是一个网络 对图对图G=(V,E)，若存在，若存在G1=(V1，E1)，满足满足V1V，E1E。则。则G1是是G的的子图。子图。例如：例如：右图右图G4 就是就是G2 的子图。的子图。213465837图G3 网络示例2134图图G4 子图示例子图示例2134图图G2 无向图示例无向图示例68.1 基本概念和运算顶点间关系顶点间关系：如果如果 E
4、则称则称 Vi，Vj相邻接相邻接，Vi邻接到邻接到Vj，Vj邻接自邻接自Vi。例如，右例如，右 图中，图中，V1邻接到邻接到V2，V4邻接自邻接自V3 若若(Vi,Vj)E则称则称Vi，Vj相邻接相邻接 顶点的顶点的度度 顶点的邻接点的数目。顶点的邻接点的数目。有向图中：有向图中：入度入度，出度出度。度入度出度度入度出度。2134图图G1 有向图示例有向图示例78.1 基本概念和运算路径路径 若若 顶点序列顶点序列Vi1，Vi2，Vik，满足满足E或或 者者(Vil，Vi(l+1)E）（）（l=1,2,k-1），），则该顶点序列则该顶点序列Vi1，Vi2，Vik 构成一条路径构成一条路径。例例
5、:图图G1中，中，1,2,4,1,3,4是一条路径是一条路径简单路径简单路径 中间经过的顶点不重复的路径。中间经过的顶点不重复的路径。例例:图图G1中，中，(1,2,4)(1,3,4)(1,3,4,1)都是简单路径。都是简单路径。回路回路 首尾相同的路径。首尾相同的路径。例如，例如，(1,3,4,1)简单回路简单回路 简单路径简单路径+回路回路2134图图G1 有向图示例有向图示例88.1 基本概念和运算 若若无向图无向图中任意两点间都存在路径中任意两点间都存在路径 则称为则称为连通图。连通图。否则，称为否则，称为不连通图（非连通图）不连通图（非连通图）。非连通图包含若干非连通图包含若干连通分
6、量连通分量-极大连通子图。极大连通子图。若若有向图有向图中的任意两点间可以中的任意两点间可以互相到达互相到达 则称为则称为强连通图。强连通图。12534连通图示例6712534非连通图示例-三个连通分量6712534强连通图示例98.1 基本概念和运算若若无向图无向图中任意两点间都有一条边中任意两点间都有一条边 则称为则称为无向完全图。无向完全图。（共有（共有n(n-1)/2条边）条边）若若有向图有向图中每个顶点到其余各点均有一条弧中每个顶点到其余各点均有一条弧 则称为则称为有向完全图。有向完全图。（共有（共有n(n-1)条边）条边）125345阶无向完全图21344阶有向图示例阶有向图示例1
7、08.1 基本概念和运算若无向图满足：若无向图满足：连通并且无回路连通并且无回路 则称为则称为树。树。树的定义有如下几个树的定义有如下几个等价的描述等价的描述：有最少边数的连通图。有最少边数的连通图。有有n-1条边的连通图。条边的连通图。连通的无环图。连通的无环图。有向树有向树 如果在有向图中，如果在有向图中，有一个顶点的入度为有一个顶点的入度为0，其余顶点的入度为，其余顶点的入度为1，则称此图为有向树。则称此图为有向树。并称其中入度为并称其中入度为0的顶点为的顶点为有向根有向根。右下图就是一个有向树，其中顶点右下图就是一个有向树，其中顶点1就是有向根。就是有向根。6712534树的示例671
8、2534有向树示例118.1 基本概念和运算图的运算：图的运算：基本运算基本运算：初始化图初始化图 插入顶点插入顶点 插入边（弧）插入边（弧）修改权值修改权值 删除顶点删除顶点 删除边（弧）删除边（弧）求指定顶点的邻接点求指定顶点的邻接点 常用运算常用运算：遍历遍历128.1 基本概念和运算 邻接点的求解方法：邻接点的求解方法：具体实现依赖于图的存储结构，具体实现依赖于图的存储结构，可以考虑用两个运算来实现求解：可以考虑用两个运算来实现求解：int firstadj(G,v);返回顶点返回顶点v的第一个邻接点号。的第一个邻接点号。若不存在时，返回若不存在时，返回0（或定义为（或定义为-1）。）
9、。int nextadj(G,v,w);返回顶点返回顶点v的邻接点中处于邻接点的邻接点中处于邻接点w之后的邻接点号。之后的邻接点号。若不存在时，返回若不存在时，返回0（或定义为（或定义为-1）。）。138.2 图的存储图的存储图的存储-图结构在计算机中的存储形式图结构在计算机中的存储形式1。邻接矩阵。邻接矩阵 （1）不带权值 假设图中有n个顶点。则采用nn的矩阵A来表示，1 E 其中 Aij 0 否则例例：13240 1 1 00 0 0 10 0 0 11 0 0 0行的方向：发出的弧列的方向：进入的弧对应关系148.2 图的存储 （2）网络的表示方法 wij E Aij 0 或 否则例例：
10、4 4 3 54 23 65 2 6 12430 1 1 11 0 0 11 0 0 11 1 1 0无向图的邻接矩阵对称 142363524158.2 图的存储2.邻接表表示法邻接表表示法 -将将 邻接点构成链表邻接点构成链表 例例：12341243data firstadj2341414123对应关系168.2 图的存储o逆邻接链表逆邻接链表-将将“邻接自邻接自”的顶点连成链表的顶点连成链表 1234data firstadj41134321321234data firstadj4412data firstadj对应关系代表弧178.3 图的遍历图的遍历图的遍历访问图中所有顶点一次且仅且一
11、次。访问图中所有顶点一次且仅且一次。深度优先搜索遍历深度优先搜索遍历 图的两种遍历算法图的两种遍历算法 广度优先搜索遍历广度优先搜索遍历8.3.1 深度优先搜索遍历（深度优先搜索遍历（Depth First Search)这一问题求解包括几个部分。这一问题求解包括几个部分。1.基本算法基本算法 从顶点从顶点v0出发深度优先搜索遍历图出发深度优先搜索遍历图G的的dfs(v0)描述如下：描述如下：(1)访问访问v0；(2)依次从依次从v0的未被访问过的邻接点出发深度遍历。的未被访问过的邻接点出发深度遍历。18dfs(8)dfs(9)dfs(4)dfs(3)8.3.1 深度优先搜索遍历深度优先搜索遍
12、历下面以下图为例来讨论下面以下图为例来讨论dfs算法的执行过程：调用算法的执行过程：调用dfs(1)此箭头表示是从遍历运算dfs(1)中调用dfs(2)，即从顶点1直接转到2 此虚箭头表示是在dfs(3)执行完毕后返回到遍历运算dfs(2)中，即从顶点3返回到267125348109dfs(1)dfs(2)dfs(5)dfs(6)dfs(7)dfs(10)在访问顶点3后，由于顶点3的邻接点已全被访问，故dfs（3）执行到此结束，应返回到调用层，即返回到dfs(2)dfs(1)包含如下两部分操作：（1）访问顶点1；（2）依次执行dfs(2)和dfs(8)198.3.1 深度优先搜索遍历深度优先搜
13、索遍历将将dfs（1）执行过程中所搜索的边连接起来（有标注）执行过程中所搜索的边连接起来（有标注的边），的边），得到一棵生成树得到一棵生成树-dfs生成树。生成树。6712534810967125348109原图及其搜索示意图dfs(1)生成树208.3.1 深度优先搜索遍历深度优先搜索遍历下面讨论下面讨论dfs算法的设计。算法的设计。为此，先回顾一下为此，先回顾一下dfs(v0)的描述：的描述：(1)访问访问v0；(2)依次从依次从v0的未被访问过的邻接点出发深度遍历。的未被访问过的邻接点出发深度遍历。分析分析：由算法描述可知：由算法描述可知：访问访问顶点顶点v0的基本操作：的基本操作：可用
14、可用visite(v0)简单表示。简单表示。设置访问标志数组设置访问标志数组visted，并约定：，并约定：某顶点某顶点vi未被访问时，未被访问时，vistedi=FALSE（初值）（初值）vi被访问过后，被访问过后，vistedi=TRUE（初值）（初值）求邻接点可以采用两个函数：求邻接点可以采用两个函数：firstadj(G,v)：返回：返回v的第一个邻接点（号），或的第一个邻接点（号），或0（不存在时）。（不存在时）。nextadj(G,v,w);返回返回v的第邻接点中处于邻接点的第邻接点中处于邻接点w之后的邻接点号之后的邻接点号,或或0（不存在时）（不存在时）访问访问v0时，时，vis
15、tedi=FTRUE;21YN8.3.1 深度优先搜索遍历深度优先搜索遍历 由讨论可得到由讨论可得到dfs算法的流程图如下算法的流程图如下：由此得深度遍历基本算法由此得深度遍历基本算法dfs(v0)如下如下:void dfs(int v0)visite(v0);visitedv0=TRUE;w=firstadj(G,v0);while(w!=0)if(!visitedw)dfs(w);w=nextadj(G,v0,w);Nvisite(v0);vistedv0=TRUE;W=0?W被访被访问过？问过？Ndfs(w);w=nextadj(G,v,w);w=firstadj(G,v)：228.3.
16、1 深度优先搜索遍历深度优先搜索遍历问题问题：（1）dfs算法是否算法是否适用于有向图适用于有向图？（2）如何设置如何设置标志数组标志数组visited的初值？的初值？能否在能否在dfs算法中设置？算法中设置？（3）从某顶点出发是否能保证访问到）从某顶点出发是否能保证访问到所有顶点所有顶点？或者说：选择一个起点调用一次或者说：选择一个起点调用一次dfs算法，能否实现对算法，能否实现对整个图整个图的遍历？的遍历？2.遍历整个图的算法遍历整个图的算法 dfs算法在应用于非连通图，或者是某些有向图时，算法在应用于非连通图，或者是某些有向图时，某一次调用就不能保证访问到所有顶点。如下图所示。某一次调用
17、就不能保证访问到所有顶点。如下图所示。61253467125348109238.3.1 深度优先搜索遍历深度优先搜索遍历为此，需要为此，需要重新选择起点重新选择起点来调用来调用dfs算法。算法。如何选择新的起点？如何选择新的起点？起点应满足什么条件？起点应满足什么条件？将对访问标志数组的赋初值运算，将对访问标志数组的赋初值运算，以及选择起点的控制合在一起，以及选择起点的控制合在一起，构成对构成对整个图的遍历算法整个图的遍历算法如下：如下：void travel_dfs(graph G)for(i=1;i=n;i+)visitedi=FALSE;for(i=1;i=n;i+)if(!visite
18、di)dfs(i);248.3.1 深度优先搜索遍历深度优先搜索遍历 3.深度遍历算法的应用问题问题：（1）如何设计算法以判断给定的无向图是否是连通的？）如何设计算法以判断给定的无向图是否是连通的？（2）如何设计算法以求解给定的无向图中的边数？）如何设计算法以求解给定的无向图中的边数？（3）设计算法以判断给定的无向图是树。）设计算法以判断给定的无向图是树。（4）设计算法以判断给定的有向图是以）设计算法以判断给定的有向图是以v0为根的有向树。为根的有向树。（5）设计算法以判断图中的一个节点是否为关节点。）设计算法以判断图中的一个节点是否为关节点。258.3.1 深度优先搜索遍历深度优先搜索遍历例
19、1 设计算法以求解无向图G的连通分量的个数。分析：对无向图G来说，选择某一顶点v执行dfs(v)，可访问到所在连通分量中的所有顶点 因此，选择起点的次数就是图G的连通分量数，这可通过修改遍历整个图的算法dfs_travel来实现：每调用一次dfs算法计数一次。另外，考虑到要求求解连通分量数，因而可以将算法设计为整型函数。具体算法如下：268.3.1 深度优先搜索遍历深度优先搜索遍历int numofGC(graph G)int i;int k=0;/k用于连通分量的计数 for(i=1;i=n;i+)visitedi=FALSE;for(i=1;i=n;i+)if(visitedi=FALSE
20、)k+;dfs(G,i);/用k来累计连通分量个数 return k;遍历整个图的算法dfs_travel中的原来的部分278.3.1 深度优先搜索遍历深度优先搜索遍历例例2 设计算法求出无向图设计算法求出无向图G的边数。的边数。算法如下：算法如下：void dfs(graph G,int v)int w;visitedv=TRUE;/设置访问标志（访问结点的其它操作被省设置访问标志（访问结点的其它操作被省去）去）w=firstadj(G,v);while(w!=0)E+;/此处意味着找到一条边，故累计到变量此处意味着找到一条边，故累计到变量E中中 if(visitedw=FALSE)dfs(
21、G,w);w=nextadj(G,v,w);dfs算法中原有的操作288.3.1 深度优先搜索遍历深度优先搜索遍历int Enum(graph G)int i;E=0;/全局变量E记录整个图中的边数 for(i=1;i=n;i+)visitedi=FALSE;for(i=1;i=n;i+)if(visitedi=FALSE;)dfs(G,i);return E/2;遍 历 整 个 图 的 算 法dfs_travel中的原来的部分298.3.1 深度优先搜索遍历深度优先搜索遍历 4.4.深度遍历算法的应用二深度遍历算法的应用二例例3 3：设计算法，将：设计算法，将1-n(=20,1-n(=20,
22、或其他数或其他数)放在一个环上，使环上放在一个环上，使环上任意两个相邻元素的和为质数。任意两个相邻元素的和为质数。分析分析：可以用：可以用图图来描述该问题：来描述该问题：用用顶点顶点表示一个表示一个数数 若两个数的和为质数，若两个数的和为质数，则对应顶点之间有一条则对应顶点之间有一条边边。例如，若例如，若n=10n=10，对应图如右所示。，对应图如右所示。在这一表示下，问题转化为：在这一表示下，问题转化为：求图中包含所有顶点的简单回路求图中包含所有顶点的简单回路。如图所示的一个解。如图所示的一个解。（1 1，2 2，3 3，4 4，7 7，6 6，5 5，8 8，9 9，1010）671253
23、48910308.3.1 深度优先搜索遍历深度优先搜索遍历算法设计中需要注意的：算法设计中需要注意的：通过在通过在dfsdfs算法的基础上变化而得：算法的基础上变化而得：（1 1）路径的记录：需要增加变量或参数以记录路径，因）路径的记录：需要增加变量或参数以记录路径，因此，不妨设一个数组以记录路径中的顶点序列和一个此，不妨设一个数组以记录路径中的顶点序列和一个记录长度的变量。记录长度的变量。（2 2）若某些走法行不通，需要重来，为此，要恢复）若某些走法行不通，需要重来，为此，要恢复visitedi标志。标志。（3 3）需要判断首尾相接。）需要判断首尾相接。318.3.1 深度优先搜索遍历深度优
24、先搜索遍历算法构思算法构思如下:(1)设环上已有设环上已有k个元素（个元素（0kn）。）。(2)若若kn,且不在当前路径上的顶点中存在与且不在当前路径上的顶点中存在与Bk相邻的，相邻的，则则依次依次从从余下余下的顶点中取出与的顶点中取出与Bk相邻的顶点放置在相邻的顶点放置在Bk+1中中,转转(1)。(3)若若kn，而在余下的这些顶点中找不到一个与，而在余下的这些顶点中找不到一个与BK相邻的顶点，相邻的顶点，或者是虽然存在邻接点，但这些结点均已在同等条件下放置过了，或者是虽然存在邻接点，但这些结点均已在同等条件下放置过了，因而须从环上去掉因而须从环上去掉BK，转，转(1)。(4)若若k=,有两种
25、情况有两种情况:(a)Bn与与B1相邻接相邻接,说明已求得一解说明已求得一解,则输出求解结果则输出求解结果,然后返回。然后返回。(b)Bn与与B1不邻接，说明前面的放置法不行不邻接，说明前面的放置法不行,即不构成环即不构成环,因而需要因而需要重新放置，即要去掉重新放置，即要去掉Bn和和Bn-1，然而转，然而转(1)。为避免遗漏某种放。为避免遗漏某种放置，从最后往前依次用余下的顶点中的与其前面相邻接的顶点替置，从最后往前依次用余下的顶点中的与其前面相邻接的顶点替换。换。采用递归方式实现如下：采用递归方式实现如下：其中其中visited为标志数组，表示各结点是否在当前的路径上。为标志数组，表示各结
26、点是否在当前的路径上。328.3.2 广度优先搜索遍历广度优先搜索遍历o 8.3.2 广度优先搜索遍历（广度优先搜索遍历（Breadth_first search)广度优先遍历广度优先遍历 由近及远逐层访问顶点（典型的层次遍历）由近及远逐层访问顶点（典型的层次遍历）1.基本算法基本算法 从顶点从顶点v0出发广度优先搜索遍历图的算法出发广度优先搜索遍历图的算法bfs(v0):（1）访问）访问v0 （2）依次访问）依次访问v0的各邻接点。的各邻接点。（3）设最近一层访问序列为）设最近一层访问序列为vi1，vi2，vik，则依次访问则依次访问 vi1，vi2，vik的的 未被访问过未被访问过的邻接点
27、。的邻接点。338.3.2 广度优先搜索遍历广度优先搜索遍历bfs(1)bfs(1)的执行过程如下图所示。的执行过程如下图所示。其中用红线标注搜索路线。其中用红线标注搜索路线。将搜索的便连起来得到将搜索的便连起来得到bfsbfs生成树。生成树。6712534810967125348109bfs生成树348.3.2 广度优先搜索遍历广度优先搜索遍历算法构思：算法构思：(1)设访问标志数组；设访问标志数组；(2)为了能依次访问上一层次的访问序列中的各顶点的邻接点，为了能依次访问上一层次的访问序列中的各顶点的邻接点，需要设置一个结构以保存上一层次的顶点，需要设置一个结构以保存上一层次的顶点，这一结构
28、还要满足这样的要求：这一结构还要满足这样的要求：这一层中最先被访问的顶点，其后继也应被最先检测到。这一层中最先被访问的顶点，其后继也应被最先检测到。由此可知，这一结构应是由此可知，这一结构应是队列队列。(3)既然涉及到队列（不妨既然涉及到队列（不妨Q），则需要安排队列的运算：），则需要安排队列的运算：(a)初始化；初始化；(b)入队：每访问一个顶点入队：每访问一个顶点v，除了访问操作、设置标志外，除了访问操作、设置标志外，还要将其入队。还要将其入队。(c)出队：从队列中删除一个顶点出队：从队列中删除一个顶点v，这意味着要依次访问，这意味着要依次访问v的的所有未被访问过的邻接点。所有未被访问过的
29、邻接点。358.3.2 广度优先搜索遍历广度优先搜索遍历广度遍历的基本算法如下：广度遍历的基本算法如下：void bfs(int v0)Queue Q;visite(v0);visitedv0=TRUE;Q.append(v0);while(!Q.Empty()v=Q.Serve();w=firstadj(G,v);while(w!=0)if(!visitew)visite(w);visitedw=TRUE;Q.append(w);w=nextadj(G,v,w);368.3.2 广度优先搜索遍历广度优先搜索遍历2.遍历整个图的算法遍历整个图的算法 void travel_bfs(graph
30、G)for(i=1;i=n;i+)visitedi=FALSE;for(i=1;i=n;i+)if(!visitedi)bfs(i);3.广度遍历算法的应用广度遍历算法的应用例：迷宫中的最短路径算法例：迷宫中的最短路径算法378.4 最小生成树问题问题：修建一个连接各个小区与供应站点之间的管道使得造价成本最修建一个连接各个小区与供应站点之间的管道使得造价成本最低，即构造一颗最小生成树。但是如何求解？低，即构造一颗最小生成树。但是如何求解？o8.4.1 prim算法算法 1.基本思想基本思想 在满足如下条件的过程中选出一条最小的边：在满足如下条件的过程中选出一条最小的边：一端已选，另一端未选。一
31、端已选，另一端未选。因此，该算法需要给出起点，以作为已选顶点。因此，该算法需要给出起点，以作为已选顶点。2.实例实例 对右图所示图，对右图所示图，用用Prim算法求最小生成树。算法求最小生成树。1746125349 1299156103388.4 最小生成树 46125349 1299156171039 61253412991561710439 61253412991561710439 61253412991561710439 61253412991561710439 6125341299156171043398.4 最小生成树-求解过程的表格化求解已选顶点已选顶点集集 U顶点顶点1候选边候选
32、边顶点顶点2候选边候选边顶点顶点3候选边候选边顶点顶点4候选边候选边顶点顶点5候选边候选边顶点顶点6候选边候选边11,61,6,51,6,5,41,6,5,4,31,6,5,4,3,2(1,2)/12(1,3)/(1,4)/(1,5)/9(1,6)/9(1,2)/12(6,2)/15(6,3)/17(6,4)/20(1,5)/9(6,5)/9(6,4)/20(5,4)/4(1,2)/12(6,2)/15(6,3)/17(1,2)/12(6,2)/15(6,3)/17(4,3)/3(1,2)/12(6,2)/15(3,2)/61746125349 1299156103408.4 最小生成树 Pr
33、im算法练习求下图的最小生成树：1235412354435323136已选顶点集合U顶点1候选边顶点2候选边顶点3候选边顶点4候选边顶点5候选边1(1,2)/3(1,3)/3(1,4)/4(1,5)/1,3(3,2)/5(3,4)/2(3,5)/61,3,4(4,2)/(4,5)/11,3,4,5(5,2)/31,3,4,5,213425Prim最小生成树最小生成树注：最小生成树不唯一,但权值之和相同。418.4 最小生成树3.算法算法Prim算法的简要描述（设起点为v0）：设置各候选边(v0,vi)；for (i=1;i=n-1;i+)从候选边中找出权值最小的边(v,vk)；/其中v已选边，
34、vk未选 将vk设置为已选顶点；调整候选边集合-调整新入选顶点和未选顶点之间的边的集合 由此可知，需要考虑如下几个方面的实现：（1）已选顶点的标识：可用数组来或集合来存储（或形式化描述）。（2）候选边的存储：虽然每个顶点可能对应多个候选边，但只要最小的一个，因此，用一个数组也可以，不妨用edges（下标用1-n即可）428.4 最小生成树初始化候选边数组edges；U=v0；for(i=1;i=n-1;i+)k=最小候选边的未选的一端；U=U+k；以k修改edges；注：edges的元素可以设置为v 思考：权值最小的边一定在最小生成树中么？分析:prim算法的时间复杂度？438.4 最小生成树
35、void prim(graph G,graph&T)for(i=1;i=n;i+)if (G.Av0,i )edgesi.vj=v0;edgesi.w=G.Av0,i;else edgesi.w=;for(i=1;i=n;i+)selectedi=FALSE;selected1=TRUE;for(i=1;i=n-1;i+)minw=;for(j=1;j=n;i+)if (!selectedj&edgesj.wG.Ak,w)edgesw.w=G.Ak,w;edgesw.vj=k;w=nextadj(G,k,w);初始化候选边数组edges初始化已选边数组selectedprim算法的时间复杂度是
36、O(n2)。设置起始点已选从候选边中找出权值最小的边将k设置为已选顶点调整候选边集合448.4 最小生成树void prim(graph&g,int v0)/Prim算法的主函数，假设算法的主函数，假设v0是起点是起点MinEdgeArray MinEdges;int i,j,k;selected_Vset=v0;/将起始顶点将起始顶点v0作为己选点作为己选点 Init_MinEdges(g,MinEdges,v0);/初始化候选边集合初始化候选边集合for(i=1;in;i+)/控制控制n-1次最小边的选择次最小边的选择 k=Get_MinEdge(g,MinEdges);/调用函数选择对应
37、最小候选边的未选顶点调用函数选择对应最小候选边的未选顶点 selected_Vset=selected_Vset+k;/在己选点集中插入顶点在己选点集中插入顶点k change_MinEdges_with(g,MinEdges,k);/调整当前候选边集调整当前候选边集458.4 最小生成树typedef struct /候选边存储结构候选边存储结构 int v;/未选顶点对应的候选边的另一端点未选顶点对应的候选边的另一端点 int w;/未选顶点对应的候选边的权值未选顶点对应的候选边的权值 MinEdgeType;typedef MinEdgeType MinEdgeArraymax_num;
38、/候选边集的存储结构候选边集的存储结构void Init_MinEdges(graph&g,MinEdgeArray&MinEdges,int v0)/初始化候选边集初始化候选边集 int i;for(i=1;i=n;i+)/初始化每个未选顶点对应的候选边的相关信息初始化每个未选顶点对应的候选边的相关信息if (have_edge(g,v0,i)/若若g中存在边中存在边(v0,i)MinEdgesi.v=v0;/设置顶点设置顶点i到起点到起点v0的候选边信息的候选边信息 MinEdgesi.w=edge_weight(g,v0,i);/另一端点及相应的权值另一端点及相应的权值 else Min
39、Edgesi.w=;/否则，以否则，以表示不存在边表示不存在边(v0,i)468.4 最小生成树 int Get_MinEdge(graph&g,MinEdgeArray&MinEdges)/从候选边集中选出边最短的顶点从候选边集中选出边最短的顶点 int MMin,j,k;MMin=;/设置当前最短边的权值设置当前最短边的权值 for(j=1;j=n;j+)/逐个比较，搜索最小的边逐个比较，搜索最小的边 if (j是未选顶点是未选顶点&MinEdgesj.wMMin)k=j;/记录当前具有最小边的未选顶点记录当前具有最小边的未选顶点 MMin=MinEdgesj.w;/以及对应最短边的权值以
40、及对应最短边的权值return k;/最后的最后的k值记录的就是具有最小边的未选顶点，作为函数值返回值记录的就是具有最小边的未选顶点，作为函数值返回478.4 最小生成树void change_MinEdges_with(graph&g,MinEdgeArray&MinEdges,int k)int j;/对新选出的候选顶点对新选出的候选顶点k调整当前候选边集调整当前候选边集 for(j=1;j=n;j+)/依次检查每个顶点依次检查每个顶点 if(j 是未选顶点是未选顶点)if(have_edge(g,k,j)&edge_weight(g,k,j)MinEdgesj.w)/若顶点若顶点j到到k
41、有更小的边有更小的边 MinEdgesj.w=edge_weight(g,k,j);/替换顶点替换顶点j原候选边的相关信息原候选边的相关信息 MinEdgesj.v=k;488.4 最小生成树 2.实例 判断构成回路的经典方法：电位法o Kruskal算法算法 1.基本思想基本思想 反复在满足如下条件的边中选出一条最小的边 使其和已选边不构成回路。1347521225352111364498.4 最小生成树o 3算法实现的讨论 Kruskal算法的简要描述：T=(V,);/初始化生成树T while(T中所含边数n-1)从E中选取当前最短边(u,v)；从E中删去边(u,v)；if(u,v)与T
42、中边不构成回路)将边(u,v)加入T中；需解决问题：需解决问题：（1）候选边的存储（2）判断所选择的边和已选的边不构成回路？分析分析Kruskal算法的时间复杂度为(eloge)、(n3)。其时间性能和空间性能都不是很如意。508.4 最小生成树Kruskal算法练习 o Kruskal算法算法 基本思想基本思想 反复在满足如下条件的边中选出一条最小的边 使其和已选边不构成回路。1235443532313612354Kruskal最小生成树最小生成树518.5 有向无环图的应用工程问题o 工程工程由多项活动构成，且活动之间存在一定制约。工程问题：1)工程是否顺利进行？2)工程至少需要的时间？3
43、)工程中哪些是关键环节？p 用图来表示工程：其中，顶点表示活动；弧表示活动之间的制约关系。这种图称为AOV网(Activity On Vertex Network)。工程是否顺利进行？AOV网是否存在有向回路123456528.5 有向无环图的应用工程问题o如何判断AOV网中是否存在有向回路？o解决方法：n(1)用深度遍历要做许多试探性工作；n(2)用产生顶点序列的方法拓扑排序；若图中顶点Vi到顶点Vj存在路径，则在序列中顶点Vi领先于顶点Vj。满足上述条件的顶点序列称为拓扑序列拓扑序列，产生这一序列的过程称为拓扑排序拓扑排序。o结论：如果能产生拓扑序列则说明AOV网中无回路，否则有回路。53
44、8.5 拓扑排序o 拓扑排序拓扑排序算法简单描述：找一个入度为0的顶点v输出；删除v及相关弧；重复，直到无入度为0的顶点为止。548.5 拓扑排序实例12345612345653124563461234561235462456512345612345664123456123456对下图所示AOV网进行拓扑排序558.5 有向无环图的应用拓扑排序 判断有无回路的条件：是否有拓扑序列。思考：入度数组Ind（数组初始化的实现）；“删除v”的实现后继的入度减一；找入度为0的顶点将入度为0的待输出顶点放到栈中，若出现入度为0 的顶点则入栈。拓扑排序算法分析拓扑排序算法分析 拓扑排序算法：初始化入度数组I
45、nd（若出现0入度顶点，则入栈s）；若栈s为空，则跳出循环，转到 v=pop(s)并输出v；对v的所有后继w实现：Indw-1；若Indw=0；则w入栈；转；判断是否存在回路。568.5 有向无环图的应用拓扑排序o 栈的演示123456123546132546578.5 有向无环图的应用拓扑排序 Bool toposort(graph G)get_Ind(G,Ind);stack s;int count=0;for(i=1;i=n;i+)if(Indi=0)s.push(i);while(!s.empty()v=s.pop();coutv;count+;w=firstadj(G,v);whil
46、e(w!=0)Indw-;if(Indw=0)s.push(w);w=nextadj(G,v,w);if(count=n)return TURE:else returen FALSE;p 分析 若图采用邻接矩阵来存储，则算法复杂度为(n2)；若图采用邻接表来存储，则算法复杂度为(n+e)。588.5 有向无环图的应用练习例:写出一种的拓扑序列所以，其中一种拓扑序列为：25147368910思考：写出所有的拓扑排序。598.5 关键路径关键路径问题引入问题引入o工程工程由多项活动构成，且活动之间存在一定制约。工程问题：1)工程是否顺利进行？拓扑排序（AOV）2)工程至少需要的时间？3)工程中哪些
47、是关键环节？p用图来表示工程：其中，用弧表示活动；用弧的权值表示活动的持续时间；用弧两端的顶点分别表示活动的开始和结束，即工程中的瞬间行为或事件。这种图称为AOE网(Activity On Edge Network)。工程至少需要的时间？工程中哪些是关键环节？AOE网中源点到汇点的最长路径 关键路径关键路径123456126537238911608.5 关键路径关键路径相关概念相关概念123456126537238911在AOE网中分别对应一个顶点，称开始点（即入度为0的顶点）为源点源点，称结束点（即出度为0的顶点）为汇点。汇点。整个工程所需要的最少时间不是所有活动所需时间的累加,而应是从源点
48、到汇点之间的最长最长的一条路径。称这条最长的路径为关键路径关键路径(critical path)。p求解事件的最早发生时间最早发生时间：每个顶点事件的最早发生时间都依赖于其前驱顶点事件的最早发生时间。源点对应事件的最早发生时间为0p求解事件的最迟发生时间最迟发生时间每个顶点事件的最迟发生时间都不能影响到后续各顶点的最迟发生时间。618.5 关键路径关键路径p 为求最长路经，则需求各顶点对应事件的最早发生时间E;p 为不耽误工期，则需求各顶点对应时间的最迟发生时间L.如何判断AOE网中的关键路径？关键路径上的事件最早发生时间和最晚发生时间相等；关键路径上的活动的开始和结束事件发生的时间差等于活动
49、的持续时间。最早发生时间=最晚发生时间相等关键路径628.5 关键路径关键路径实例实例 关键路径的求解方法及路径12345678910a1=3a3=5a2=4a5=3a4=6a8=5a9=4a6=4a10=3a12=6a11=4a15=4a14=6a13=5a7=334598141312191915131491076300关键路径：（1,2,5,7,10）和（1,2,5,8,10）关键活动：a1，a4，a8，a9，a13，a14 638.6 最短路径(Shortest path)o 从单个点到其余各点之间的最短路径 n Dijkstra算法o 各点之间的最短路径 n Floyd算法648.6
50、最短路径Dijkstra算法o 从单个点到其余各点间的最短路径从单个点到其余各点间的最短路径Dijkstra算法算法 基本思想基本思想 按照最短路径长度不减的次序求各顶点的解。若已知道路v0v1v2v3vn-1vn是v0到vn最近的路，则途径的某顶点vi也为v0到vi最短的路。12345612653723892658.6 最短路径Dijkstra算法实例12345612653723892求下图中顶点1到其余各顶点的最短路径。101238510364142512(1)初始化:1到v,若有边,则pathv=边;disti=边的值(2)选出disti为最小值,则pathi为1到i的最短路径(3)修改
