《图的搜索算法》PPT课件

《《图的搜索算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章图的搜索算法5．1图搜索概述5．1．1图及其术语5．1．2图搜索及其术语5．2广度优先搜索5．2．1算法框架5．2．2广度优先搜索的应用上一页·下一页·返回首页图是一种限止最少的数据结构，因此更接近现实，实际问题中很多数据关系都可以抽象成图，相关问题则可利用图的基本算法进行求解，很早就有专门研究图的是一门数学学科“图论”；其中的计算问题包括图的搜索、路径问题、连通性问题、可平面性检验、着色问题、网络优化等。图论中的著名算法有：求最小生成树的Kruskal算法、求最短路径的Dijkstra算法和Floyd算法、求二部图最大匹配（指派问题

2、）的匈牙利算法、求一般图最大匹配的Edmonds“花”算法、求网络最大流和最小割的算法等。其中的一些算法在数据结构课程中已经学习过了。1．显式图与隐式图在路径问题、连通性问题、可平面性检验、着色问题和网络优化等问题中，图的结构是显式给出的，包括图中的顶点、边及权重，这类图我们称为显式图，也就是一般意义上的图。隐式图是由问题的初始结点，为了求解或求证问题，根据题目的规则（一般是由题目的意思隐含给出的），也就是生成子结点的约束条件，逐步扩展结点，直到得到目标结点为止的一个隐式的图。5．1．1图及其术语2.显式图的常用术语如图5-1所示的⑴，⑵，

3、⑶均为显式图(Graph)。图中的这些点(v1,v2,…,vn)被称为顶点(vertex)或结点，连接顶点的曲线或直线称为边(edge)。通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为图，顶点通常被称作是图中的数据元素.上一页·下一页·返回首页图5-1图5-2图带权图：j即图5-2给图5-1中各图的边上附加一个代表性数据(比如表示长度、流量或其他)，则称其为带权图。环(cycle)：图5-1中⑶图中的v1点本身也有边相连，这种边称为环。有限图：顶点与边数均为有限的图，如图5-1中的三个图均属于有限图。简单图：没有环且每两个顶点间

4、最多只有一条边相连的图，如图5-1中的⑴图。邻接与关联：当（v1，v2）∈E，或∈E，即v1，v2间有边相连时，则称v1和v2是相邻的，它们互为邻接点（adjacent），同时称（v1，v2）或是与顶点v1、v2相关联的边。上一页·下一页·返回首页顶点的度数(degree)：从该顶点引出的边的条数，即与该顶点相关联的边的数目，简称度。入度（indegree）：有向图中把以顶点v为终点的边的条数称为是顶点v的入度。出度（outdegree）：有向图中把以顶点v为起点的边的条数称为是顶点v的出度。终端顶点：有向图中把

5、出度为0的顶点称为终端顶点，如图5-1中⑵图的v3。路径与路长：在图G=(V，E)中，如果存在由不同的边(vi0，vi1)，(vi1，vi2)，…，(vin-1，vin)或是，，…，)组成的序列，则称顶点vi0，vin是连通的，顶点序列（vi0，vi1，vi2，…，vin）是从顶点vi0到顶点vin的一条道路。路长是道路上边的数目，vi0到vin的这条道路上的路长为n。连通图：对于图中任意两个顶点vi、vj∈V，vi、vj之间有道路相连，则称该图为连通图。如5-1中的⑴图。网络：带权

6、的连通图，如图5-2所示。3．隐式图术语1）子集树当要求解的问题需要是在n个元素的子集中进行搜索，其搜索空间树被称作子集树（subsettree）。这n个元素都有在子集中或被选取记为1，不在子集中或被舍去记为0，这样搜索空间为：（0，0，……，0，0），（0，0，……，0，1），（0，0，……，1，0），（0，0，……，1，1），……（1，1，……，1，1）。共2n个状态。若表示为树形结构就是一棵有2n个叶结点的二叉树，对树中所有分支进行遍历的算法都必须耗时O（2n）。上一页·下一页·返回首页图5-3n=3的子集树上一页·下一页·返回首页2

7、）排列树上一页·下一页·返回首页·当要求解的问题需要在n元素的排列中搜索问题的解时，解空间树被称作排列树（permutationtree）。搜索空间为：（1，2，3，……，n-1，n）,（2，1，3，……，n-1，n）,（2，3，1，……，n-1，n）,（2，3，4，1，……，n-1，n）,（n，n-1，……，3，2，1）第一个元素有n种选择，第二个元素有n-1种选择，第三个元素有n-2种选择，……，第n个元素有1种选择，共计n!个状态。若表示为树形就是一个n度树，这样的树有n!个叶结点，所以每一个遍历树中所有节点的算法都必须耗时O(n!)

8、上一页·下一页·返回首页图5-3n=4的部分子集树4．图的存储1）邻接矩阵法上一页·下一页·返回首页·邻接矩阵是表示顶点之间相邻关系的矩阵，设G=(V,E)是具有n个顶点的图，则