第五章1 图的搜索算法.ppt

第五章图的搜索算法 图搜索概述 图及其术语 图搜索及其术语 广度优先搜索 5 . 算法框架 广度优先搜索的应用上一页·下一页·返回首页图是一种限止最少的数据结构,因此更接近现实,实际问题中很多数据关系都可以抽象成图,相关问题则可利用图的基本算法进行求解,很早就有专门研究图的是一门数学学科“图论”;其中的计算问题包括图的搜索、路径问题、连通性问题、可平面性检验、着色问题、网络优化等。图论中的著名算法有: 求最小生成树的 Kruskal 算法、求最短路径的 Dijkstra 算法和 Floyd 算法、求二部图最大匹配(指派问题)的匈牙利算法、求一般图最大匹配的 Edmonds “花”算法、求网络最大流和最小割的算法等。其中的一些算法在数据结构课程中已经学面性检验、着色问题和网络优化等问题中,图的结构是显式给出的, 包括图中的顶点、边及权重,这类图我们称为显式图, 也就是一般意义上的图。隐式图是由问题的初始结点,为了求解或求证问题,根据题目的规则(一般是由题目的意思隐含给出的),也就是生成子结点的约束条件,逐步扩展结点,直到得到目标结点为止的一个隐式的图。 图及其术语 5-1 所示的⑴,⑵,⑶均为显式图( Graph) 。图中的这些点(v1,v2, …,vn)被称为顶点( vertex) 或结点,连接顶点的曲线或直线称为边( edge) 。通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为图,顶点通常被称作是图中的数据元素. 上一页·下一页·返回首页 v 1v 2v 3v 4 v 1v 3v 2v 4⑴⑵v 1v 2v 3v 4v 5⑶图 5-1 v 1v 3v 2v 43 429 6图 5-2 图带权图:j即图 5 -2给图 5-1 中各图的边上附加一个代表性数据(比如表示长度、流量或其他),则称其为带权图。环( cycle) :图 5-1 中⑶图中的 v 1 点本身也有边相连,这种边称为环。有限图:顶点与边数均为有限的图,如图 5-1 中的三个图均属于有限图。简单图:没有环且每两个顶点间最多只有一条边相连的图,如图 5-1 中的⑴图。邻接与关联:当( v 1 , v 2 )∈E,或< v 1 , v 2 > ∈E,即 v 1, v 2 间有边相连时,则称 v 1 和 v 2 是相邻的,它们互为邻接点( adjacent ), 同时称( v 1 , v 2 )或< v 1 , v 2 > 是与顶点 v 1 、 v 2 相关联的边。上一页·下一页·返回首页顶点的度数 ( degree) :从该顶点引出的边的条数,即与该顶点相关联的边的数目,简称度。入度( indegree ):有向图中把以顶点 v为终点的边的条数称为是顶点 v的入度。出度( outdegree ):有向图中把以顶点 v为起点的边的条数称为是顶点 v的出度。终端顶点:有向图中把出度为 0的顶点称为终端顶点,如图 5-1 中⑵图的 v 3 。路径与路长: 在图 G=( V , E) 中,如果存在由不同的边 ( v i0 , v i1 ) , (v i1 , v i2 ) ,…, (v in-1 , v in ) 或是 < v i0 , v i1 > , <vi 1 , v i 2> ,…, < v in-1 , v in >) 组成的序列,则称顶点 v i0, v in 是连通的,顶点序列( v i0 , v i1 , v i2 ,…, v in ) 是从顶点 v i0 到顶点 v in 的一条道路。路长是道路上边的数目, v i0 到 v in 的这条道路上的路长为 n。连通图: 对于图中任意两个顶点 v i 、 v j ∈V, v i 、 v j 之间有道路相连,则称该图为连通图。如 5-1 中的⑴图。网络: 带权的连通图,如图 5-2 所示。 1)子集树当要求解的问题需要是在 n 个元素的子集中进行搜索,其搜索空间树被称作子集树( subset tree )。这n个元素都有在子集中或被选取记为 1,不在子集中或被舍去记为 0,这样搜索空间为: (0,0,……,0,0),( 0,0,……,0,1), (0,0,……,1,0),( 0,0,……,1,1), ……(1,1,……,1,1)。共2 n 个状态。若表示为树形结构就是一棵有 2 n个叶结点的二叉树, 对树中所有分支进行遍历的算法都必须耗时 O(2 n)。上一页·下一页·返回首页图 5-3 n=3 的子集树上一页·下一页·返回首页 2)排列树上一页· 下