数据结构第八章图ppt课件.ppt

《数据结构第八章图ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构第八章图ppt课件.ppt（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去数数 据据 结结 构构（第八章第八章 图图）Data Structures胡学钢胡学钢 张张 晶晶计算机与信息学院计算机与信息学院 20092009年年2 2月月1合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去第八章第八章 图图(Graph)第八章第八章 图（图（Graph)8.1 基本概念和运算 8.2 图的存

2、储 8.3 图的遍历 8.4 最小生成树 8.5 有向无环图的应用 8.6 最短路径2合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 8.1 基本概念和运算 o图图 由顶点集由顶点集V和连接顶点的弧集和连接顶点的弧集E所组成的结构，所组成的结构，记作记作 G=(V,E)。其中弧的形式为其中弧的形式为，表示从顶点表示从顶点Vi到到Vj之间有一条弧，图形表示为：之间有一条弧，图形表示为：Vi Vj 有向图有向图例例：如右图中的：如右图中的G1就是一个有向图：就是一个有向图：其中：

3、其中：顶点集合顶点集合 V=1，2，3，4 弧集弧集 E=,2134图图G1 有向图示例有向图示例3合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 8.1 基本概念和运算 如果顶点间的关系是相互的，如果顶点间的关系是相互的，即弧的两端没有方向，则图为即弧的两端没有方向，则图为无向图。无向图。其中的弧称为其中的弧称为边。边。边的边的形式形式为为(Vi,Vj)，图形表示为：图形表示为：Vi Vj例例：如右图中的：如右图中的G2就是一个无向图：就是一个无向图：其中：其中：顶点集合顶

4、点集合 V=1，2，3，4 边集边集 E=（1,2）,（1,3）,（1,4）（2,4）,（3,4）2134图图G2 无向图示例无向图示例4合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算 若若G中每条边（弧）对应一个数值中每条边（弧）对应一个数值表示关系的程度，则称图表示关系的程度，则称图G为为网络网络。例例：图图G3 就是一个网络就是一个网络 对图对图G=(V,E)，若存在，若存在G1=(V1，E1)，满足满足V1V，E1E。则。则G1是是G的的子图。子

5、图。例如：例如：右图右图G4 就是就是G2 的子图。的子图。213465837图G3 网络示例2134图图G4 子图示例子图示例2134图图G2 无向图示例无向图示例5合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算顶点间关系顶点间关系：如果如果 E 则称则称 Vi，Vj相邻接相邻接，Vi邻接到邻接到Vj，Vj邻接自邻接自Vi。例如，右例如，右 图中，图中，V1邻接到邻接到V2，V4邻接自邻接自V3 若若(Vi,Vj)E则称则称Vi，Vj相邻接相邻接 顶点

6、的顶点的度度 顶点的邻接点的数目。顶点的邻接点的数目。有向图中：有向图中：入度入度，出度出度。度入度出度度入度出度。2134图图G1 有向图示例有向图示例6合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算路径路径 若若 顶点序列顶点序列Vi1，Vi2，Vik，满足满足E或或 者者(Vil，Vi(l+1)E）（）（l=1,2,k-1），），则该顶点序列则该顶点序列Vi1，Vi2，Vik 构成一条路径构成一条路径。例例:图图G1中，中，1,2,4,1,3,4是

7、一条路径是一条路径简单路径简单路径 中间经过的顶点不重复的路径。中间经过的顶点不重复的路径。例例:图图G1中，中，(1,2,4)(1,3,4)(1,3,4,1)都是简单路径。都是简单路径。回路回路 首尾相同的路径。首尾相同的路径。例如，例如，(1,3,4,1)简单回路简单回路 简单路径简单路径+回路回路2134图图G1 有向图示例有向图示例7合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算 若若无向图无向图中任意两点间都存在路径中任意两点间都存在路径 则称

8、为则称为连通图。连通图。否则，称为否则，称为不连通图（非连通图）不连通图（非连通图）。非连通图包含若干非连通图包含若干连通分量连通分量 极大连通子图。极大连通子图。若若有向图有向图中的任意两点间可以中的任意两点间可以互相到达互相到达 则称为则称为强连通图。强连通图。12534连通图示例6712534非连通图示例三个连通分量6712534强连通图示例8合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算若若无向图无向图中任意两点间都有一条边中任意两点间都有一条边

9、 则称为则称为无向完全图。无向完全图。（共有（共有n(n-1)/2条边）条边）若若有向图有向图中每个顶点到其余各点均有一条弧中每个顶点到其余各点均有一条弧 则称为则称为有向完全图。有向完全图。（共有（共有n(n-1)条边）条边）125345阶无向完全图21344阶有向图示例阶有向图示例9合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算若无向图满足：若无向图满足：连通并且无回路连通并且无回路 则称为则称为树。树。树的定义有如下几个树的定义有如下几个等价的描述

10、等价的描述：有最少边数的连通图。有最少边数的连通图。有有n-1条边的连通图。条边的连通图。连通的无环图。连通的无环图。有向树有向树 如果在有向图中，如果在有向图中，有一个顶点的入度为有一个顶点的入度为0，其余顶点的入度为，其余顶点的入度为1，则称此图为有向树。则称此图为有向树。并称其中入度为并称其中入度为0的顶点为的顶点为有向根有向根。右下图就是一个有向树，其中顶点右下图就是一个有向树，其中顶点1就是有向根。就是有向根。6712534树的示例6712534有向树示例10合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸

11、湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算图的运算：图的运算：基本运算基本运算：初始化图初始化图 插入顶点插入顶点 插入边（弧）插入边（弧）修改权值修改权值 删除顶点删除顶点 删除边（弧）删除边（弧）求指定顶点的邻接点求指定顶点的邻接点 常用运算常用运算：遍历遍历11合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算 邻接点的求解方法：邻接点的求解方法：具体实现依赖于图的存储结构，具体实现依赖于图的存储结构，可以考虑用两个运算来实现求解：

12、可以考虑用两个运算来实现求解：int firstadj(G,v);返回顶点返回顶点v的第一个邻接点号。的第一个邻接点号。若不存在时，返回若不存在时，返回0（或定义为（或定义为-1）。）。int nextadj(G,v,w);返回顶点返回顶点v的邻接点中处于邻接点的邻接点中处于邻接点w之后的邻接点号。之后的邻接点号。若不存在时，返回若不存在时，返回0（或定义为（或定义为-1）。）。12合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.2 图的存储图的存储图的存储 图结构在计算机

13、中的存储形式图结构在计算机中的存储形式1.邻接矩阵邻接矩阵 （1）不带权值 假设图中有n个顶点。则采用nn的矩阵A来表示，1 E 其中 Aij 0 否则例例：13240 1 1 00 0 0 10 0 0 11 0 0 0行的方向：发出的弧列的方向：进入的弧对应关系13合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.2 图的存储 （2）网络的表示方法 wij E Aij 0 或 否则例例：4 3 54 23 65 2 6 12430 1 1 11 0 0 11 0 0 11

14、 1 1 0无向图的邻接矩阵对称 14236352414合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.2 图的存储2.邻接表表示法邻接表表示法 将邻接点构成链表将邻接点构成链表 例例：12341243data firstadj2341414123对应关系15合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.2 图的存储o逆邻接链表逆邻接链表 将将“邻接自

15、邻接自”的顶点连成链表的顶点连成链表 1234data firstadj411343213212344412data firstadj对应关系代表弧16合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3 图的遍历图的遍历图的遍历访问图中所有顶点一次且仅且一次。访问图中所有顶点一次且仅且一次。深度优先搜索遍历深度优先搜索遍历 图的两种遍历算法图的两种遍历算法 广度优先搜索遍历广度优先搜索遍历8.3.1 深度优先搜索遍历（深度优先搜索遍历（Depth First Search)

16、这一问题求解包括几个部分。这一问题求解包括几个部分。1.基本算法基本算法 从顶点从顶点v0出发深度优先搜索遍历图出发深度优先搜索遍历图G的的dfs(v0)描述如下：描述如下：(1)访问访问v0；(2)依次从依次从v0的未被访问过的邻接点出发深度遍历。的未被访问过的邻接点出发深度遍历。17合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去dfs(8)dfs(9)dfs(4)dfs(3)8.3.1 深度优先搜索遍历深度优先搜索遍历下面以下图为例来讨论下面以下图为例来讨论dfs算法的执

17、行过程：调用算法的执行过程：调用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)18合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而

18、出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历将将dfs（1）执行过程中所搜索的边连接起来（有标注）执行过程中所搜索的边连接起来（有标注的边），的边），得到一棵生成树得到一棵生成树-dfs生成树。生成树。6712534810967125348109原图及其搜索示意图dfs(1)生成树19合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历下面讨论下面讨论dfs算法的设计

19、。算法的设计。为此，先回顾一下为此，先回顾一下dfs(v0)的描述：的描述：(1)访问访问v0；(2)依次从依次从v0的未被访问过的邻接点出发深度遍历。的未被访问过的邻接点出发深度遍历。分析分析：由算法描述可知：由算法描述可知：访问访问顶点顶点v0的基本操作：的基本操作：可用可用visite(v0)简单表示。简单表示。设置访问标志数组设置访问标志数组visited，并约定：，并约定：某顶点某顶点vi未被访问时，未被访问时，visitedi=FALSE（初值）（初值）vi被访问过后，被访问过后，visitedi=TRUE（初值）（初值）求邻接点可以采用两个函数：求邻接点可以采用两个函数：firs

20、tadj(G,v)：返回：返回v的第一个邻接点（号），或的第一个邻接点（号），或0（不存在时）。（不存在时）。nextadj(G,v,w);返回返回v的第邻接点中处于邻接点的第邻接点中处于邻接点w之后的邻接点号之后的邻接点号,或或0（不存在时）（不存在时）访问访问v0时，时，visitedi=TRUE;20合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去YN8.3.1 深度优先搜索遍历深度优先搜索遍历 由讨论可得到由讨论可得到dfs算法的流程图如下算法的流程图如下：由此得深度遍

21、历基本算法由此得深度遍历基本算法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);visitedv0=TRUE;W=0?W被访问被访问过？过？Ndfs(w);w=nextadj(G,v,w);w=firstadj(G,v)：21合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢

22、地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历问题问题：（1）dfs算法是否算法是否适用于有向图适用于有向图？（2）如何设置如何设置标志数组标志数组visited的初值？的初值？能否在能否在dfs算法中设置？算法中设置？（3）从某顶点出发是否能保证访问到）从某顶点出发是否能保证访问到所有顶点所有顶点？或者说：选择一个起点调用一次或者说：选择一个起点调用一次dfs算法，能否实现对算法，能否实现对整个图整个图的遍历？的遍历？2.遍历整个图的算法遍历整个图的算法 dfs算法在应用于非连通图，或者是某些有向图时，算法在应用于非连通图，或者是某些有向图时，某一次调用就不能保证访问到所有顶点。如下图

23、所示。某一次调用就不能保证访问到所有顶点。如下图所示。6125346712534810922合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历为此，需要为此，需要重新选择起点重新选择起点来调用来调用dfs算法。算法。如何选择新的起点？如何选择新的起点？起点应满足什么条件？起点应满足什么条件？将对访问标志数组的赋初值运算，将对访问标志数组的赋初值运算，以及选择起点的控制合在一起，以及选择起点的控制合在一起，构成对构成对整个图的遍历算法整个

24、图的遍历算法如下：如下：void travel_dfs(graph G)for(i=1;i=n;i+)visitedi=FALSE;for(i=1;i=n;i+)if(!visitedi)dfs(i);23合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历 3.深度遍历算法的应用问题问题：（1）如何设计算法以判断给定的无向图是否是连通的？）如何设计算法以判断给定的无向图是否是连通的？（2）如何设计算法以求解给定的无向图中的边数？）如何设

25、计算法以求解给定的无向图中的边数？（3）设计算法以判断给定的无向图是树。）设计算法以判断给定的无向图是树。（4）设计算法以判断给定的有向图是以）设计算法以判断给定的有向图是以v0为根的有向树。为根的有向树。（5）设计算法以判断图中的一个节点是否为关节点。）设计算法以判断图中的一个节点是否为关节点。24合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历例1 设计算法以求解无向图G的连通分量的个数。分析：对无向图G来说，选择某一顶点v执行d

26、fs(v)，可访问到所在连通分量中的所有顶点 因此，选择起点的次数就是图G的连通分量数，这可通过修改遍历整个图的算法dfs_travel来实现：每调用一次dfs算法计数一次。另外，考虑到要求求解连通分量数，因而可以将算法设计为整型函数。具体算法如下：25合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历int numofGC(graph G)int i;int k=0;/k用于连通分量的计数 for(i=1;i=n;i+)visited

27、i=FALSE;for(i=1;i=n;i+)if(visitedi=FALSE)k+;dfs(G,i);/用k来累计连通分量个数 return k;遍历整个图的算法dfs_travel中的原来的部分26合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历例例2 设计算法求出无向图设计算法求出无向图G的边数。的边数。算法如下：算法如下：void dfs(graph G,int v)int w;visitedv=TRUE;/设置访问标志（访

28、问结点的其它操作被省去）设置访问标志（访问结点的其它操作被省去）w=firstadj(G,v);while(w!=0)E+;/此处意味着找到一条边，故累计到变量此处意味着找到一条边，故累计到变量E中中 if(visitedw=FALSE)dfs(G,w);w=nextadj(G,v,w);dfs算法中原有的操作27合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历int Enum(graph G)int i;E=0;/全局变量E记录整个

29、图中的边数 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中的原来的部分28合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历 4.4.深度遍历算法的应用二深度遍历算法的应用二例例3 3：设计算法，将：设计算法，将1-n(=20,1-n(=20,或其他数或其他数)放在

30、一个环上，使环上放在一个环上，使环上任意两个相邻元素的和为质数。任意两个相邻元素的和为质数。分析分析：可以用：可以用图图来描述该问题：来描述该问题：用用顶点顶点表示一个表示一个数数 若两个数的和为质数，若两个数的和为质数，则对应顶点之间有一条则对应顶点之间有一条边边。例如，若例如，若n=10n=10，对应图如右所示。，对应图如右所示。在这一表示下，问题转化为：在这一表示下，问题转化为：求图中包含所有顶点的简单回路求图中包含所有顶点的简单回路。如图所示的一个解。如图所示的一个解。（1 1，2 2，3 3，4 4，7 7，6 6，5 5，8 8，9 9，1010）6712534891029合肥工业

31、大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历算法设计中需要注意的：算法设计中需要注意的：通过在通过在dfsdfs算法的基础上变化而得：算法的基础上变化而得：（1 1）路径的记录：需要增加变量或参数以记录路径，因）路径的记录：需要增加变量或参数以记录路径，因此，不妨设一个数组以记录路径中的顶点序列和一个记此，不妨设一个数组以记录路径中的顶点序列和一个记录长度的变量。录长度的变量。（2 2）若某些走法行不通，需要重来，为此，要恢复）若某些走法

32、行不通，需要重来，为此，要恢复visitedi标志。标志。（3 3）需要判断首尾相接。）需要判断首尾相接。30合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历算法构思算法构思如下:(1)设环上已有设环上已有k个元素（个元素（0kn）。）。(2)若若kn,且不在当前路径上的顶点中存在与且不在当前路径上的顶点中存在与Bk相邻的，相邻的，则则依次依次从从余下余下的顶点中取出与的顶点中取出与Bk相邻的顶点放置在相邻的顶点放置在Bk+1中中,转

33、转(1)。(3)若若kn，而在余下的这些顶点中找不到一个与，而在余下的这些顶点中找不到一个与BK相邻的顶点，相邻的顶点，或者是虽然存在邻接点，但这些结点均已在同等条件下放置过了，因或者是虽然存在邻接点，但这些结点均已在同等条件下放置过了，因而须从环上去掉而须从环上去掉BK，转，转(1)。(4)若若k=,有两种情况有两种情况:(a)Bn与与B1相邻接相邻接,说明已求得一解说明已求得一解,则输出求解结果则输出求解结果,然后返回。然后返回。(b)Bn与与B1不邻接，说明前面的放置法不行不邻接，说明前面的放置法不行,即不构成环即不构成环,因而需要因而需要重新放置，即要去掉重新放置，即要去掉Bn和和Bn

34、-1，然而转，然而转(1)。为避免遗漏某种放。为避免遗漏某种放置，从最后往前依次用余下的顶点中的与其前面相邻接的顶点替换。置，从最后往前依次用余下的顶点中的与其前面相邻接的顶点替换。31合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.1 深度优先搜索遍历深度优先搜索遍历采用递归方式实现如下：采用递归方式实现如下：其中其中visited为标志数组，表示各结点是否在当前的路径上。为标志数组，表示各结点是否在当前的路径上。void getcc(int k)/A,B,visit

35、ed为全局变量，k初值为1，B1固定为1 int i;if(k=n&ABn,B1=1)/所有顶点在路径上，且构成回路，输出 print(B);else if(k0)for(i=1;i=n;i+)if(visitedi=FALSE&ABk,i=1)/搜索与Bk相邻的下一个数i visitedi=TRUE;Bk+1=i;/将i放入路径中 getcc(k+1);/往后搜索 visitedi=FALSE;/取消顶点i的放置，以便可被重新放入 调用前，要产生邻接矩阵 A的值。数组visited全置为FALSE,visited1置为TRUE。k为1,B1为1。本递归算法利用函数调用及返回实现搜索与回溯，若

36、不用递归，本算法则较为麻烦。试模拟执行之。32合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.2 广度优先搜索遍历广度优先搜索遍历o8.3.2 广度优先搜索遍历（广度优先搜索遍历（Breadth_first search)广度优先遍历广度优先遍历 由近及远逐层访问顶点（典型的层次遍历）由近及远逐层访问顶点（典型的层次遍历）1.基本算法基本算法 从顶点从顶点v0出发广度优先搜索遍历图的算法出发广度优先搜索遍历图的算法bfs(v0):（1）访问）访问v0 （2）依次访问）依

37、次访问v0的各邻接点。的各邻接点。（3）设最近一层访问序列为）设最近一层访问序列为vi1，vi2，vik，则依次访问则依次访问 vi1，vi2，vik的的 未被访问过未被访问过的邻接点。的邻接点。33合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.2 广度优先搜索遍历广度优先搜索遍历bfs(1)bfs(1)的执行过程如下图所示。的执行过程如下图所示。其中用红线标注搜索路线。其中用红线标注搜索路线。将搜索的便连起来得到将搜索的便连起来得到bfsbfs生成树。生成树。671

38、2534810967125348109bfs生成树34合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.2 广度优先搜索遍历广度优先搜索遍历算法构思：算法构思：(1)设访问标志数组；设访问标志数组；(2)为了能依次访问上一层次的访问序列中的各顶点的邻接点，为了能依次访问上一层次的访问序列中的各顶点的邻接点，需要设置一个结构以保存上一层次的顶点，需要设置一个结构以保存上一层次的顶点，这一结构还要满足这样的要求：这一结构还要满足这样的要求：这一层中最先被访问的顶点，其后继也应

39、被最先检测到。这一层中最先被访问的顶点，其后继也应被最先检测到。由此可知，这一结构应是由此可知，这一结构应是队列队列。(3)既然涉及到队列（不妨既然涉及到队列（不妨Q），则需要安排队列的运算：），则需要安排队列的运算：(a)初始化；初始化；(b)入队：每访问一个顶点入队：每访问一个顶点v，除了访问操作、设置标志外，除了访问操作、设置标志外，还要将其入队。还要将其入队。(c)出队：从队列中删除一个顶点出队：从队列中删除一个顶点v，这意味着要依次访问，这意味着要依次访问v的的所有未被访问过的邻接点。所有未被访问过的邻接点。35合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅

40、速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.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);36合肥工业大学合肥工业大学 计算机与信息学院计

41、算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3.2 广度优先搜索遍历广度优先搜索遍历2.遍历整个图的算法遍历整个图的算法 void travel_bfs(graph G)for(i=1;i=n;i+)visitedi=FALSE;for(i=1;i=n;i+)if(!visitedi)bfs(i);3.广度遍历算法的应用广度遍历算法的应用例：迷宫中的最短路径算法例：迷宫中的最短路径算法37合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸

42、湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.4 最小生成树问题问题：修建一个连接各个小区与煤气供应站点之间的管道，使得造价修建一个连接各个小区与煤气供应站点之间的管道，使得造价成本最低，即构造一颗最小生成树。但是如何求解？成本最低，即构造一颗最小生成树。但是如何求解？对应模型对应模型：树结构，生成树，最小生成树：树结构，生成树，最小生成树o8.4.1 prim算法算法 1.基本思想基本思想 在满足如下条件的边中选出一条最小的边：在满足如下条件的边中选出一条最小的边：一端已选，另一端未选。一端已选，另一端未选。因此，该算法需要给出起点，以作为已选顶点。因此，该算法需要给出起点，以作为已选顶点。2

43、.实例实例 对右图所示图，对右图所示图，用用Prim算法求最小生成树。算法求最小生成树。1746125349 129915610338合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.4 最小生成树 46125349 1299156171039 61253412991561710439 61253412991561710439 61253412991561710439 61253412991561710439 612534129915617104339合肥工业大学合肥工业大学

44、 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.4 最小生成树-求解过程的表格化求解已选顶点已选顶点集集 U顶点顶点1候选边候选边顶点顶点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

45、(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 129915610340合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.4 最小生成树3.算法算法Prim算法的简要描述（设起点为v0）：设置各候选边(v0,vi)；for (i=1;i=n-1;i+)从候选边中找出权值最小的边(v,vk)；/其中v已选边，vk未选 将vk设置为已选顶点；调整候选边

46、集合-调整新入选顶点和未选顶点之间的边的集合 由此可知，需要考虑如下几个方面的实现：（1）已选顶点的标识：可用数组来或集合来存储（或形式化描述）。（2）候选边的存储：虽然每个顶点可能对应多个候选边，但只要最小的一个，因此，用一个数组也可以，不妨用edges（下标用1-n即可）41合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.4 最小生成树初始化候选边数组edges；U=v0；for(i=1;i=n-1;i+)k=最小候选边的未选的一端；U=U+k；以k修改edges；注：

47、edges的元素可以设置为v 思考：权值最小的边一定在最小生成树中么？分析:prim算法的时间复杂度？42合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.4 最小生成树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;selectedv0=TRUE;for(i=1;i

48、=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算法的时间复杂度是O(n2)。设置起始点已选从候选边中找出权值最小的边将k设置为已选顶点调整候选边集合43合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.4 最小生成树 2.实例判断构成回路的经典方法：电

49、位法：初始状态：各顶点的电位=顶点号 每当选择一条边时，相连通的顶点的电位全都按照其中最小的值设置。由此可知新的候选边是否和已选边构成回路 -判断方法？oKruskal算法算法 1.基本思想基本思想 反复在满足如下条件的边中选出一条最小的边 和已选边不构成回路。13245671347521225352111364121111144合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.4 最小生成树o3算法实现的讨论 Kruskal算法的简要描述：T=(V,);/初始化生成树T w

50、hile(T中所含边数n-1)从E中选取当前最短边(u,v)；从E中删去边(u,v)；if(u,v)与T中边不构成回路)将边(u,v)加入T中；需解决问题：需解决问题：（1）候选边的存储（2）判断所选择的边和已选的边不构成回路？分析分析Kruskal算法的时间复杂度为(eloge)、(n3)。其时间性能和空间性能都不是很如意。45合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.4 最小生成树Kruskal算法练习 oKruskal算法算法 基本思想基本思想 反复在满足如下条