第5章 图的搜索算法.ppt

、连通性问题、可平面性检验、着色问题和网络优化等问题中,图的结构是显式给出的,包括图中的顶点、边及权重,这类图我们称为显式图,也就是一般意义上的图。隐式图是由问题的初始结点,为了求解或求证问题,根据题目的规则(一般是由题目的意思隐含给出的),也就是生成子结点的约束条件,逐步扩展结点,直到得到目标结点为止的一个隐式的图。一、(v1,v2,…,vn)被称为顶点,连接顶点的曲线或直线称为边。通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为图,:图的边上附加一个代表性数据(比如表示长度、流量或其他),则称其为带权图。环:顶点本身也有边相连,这种边称为环。有限图:顶点与边数均为有限的图。简单图:没有环且每两个顶点间最多只有一条边相连的图。邻接与关联:当(v1,v2)∈E,或<v1,v2>∈E,即v1,v2间有边相连时,则称v1和v2是相邻的,它们互为邻接点,同时称(v1,v2)或<v1,v2>是与顶点v1、v2相关联的边。度数:从该顶点引出的边的条数,简称度。入度:有向图中把以顶点为终点的边的条数。出度:有向图中把以顶点为起点的边的条数。终端顶点:有向图中出度为0的顶点。路径与路长:在图G=(V,E)中,如果存在由不同的边(vi0,vi1),(vi1,vi2),…,(vin-1,vin)或是<vi0,vi1>,<vi1,vi2>,…,<vin-1,vin>)组成的序列,则称顶点vi0,vin是连通的,顶点序列(vi0,vi1,vi2,…,vin)是从顶点vi0到顶点vin的一条道路。路长是道路上边的数目,vi0到vin的这条道路上的路长为n。连通图:对于图中任意两个顶点vi、vj∈V,vi、vj之间有道路相连。网络:带权的连通图。1)子集树当要求解的问题需要是在n个元素的子集中进行搜索,其搜索空间树被称作子集树。这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)。n=3的子集树2)排列树当要求解的问题需要在n元素的排列中搜索问题的解时,解空间树被称作排列树。搜索空间为:(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!)图5-3n=4的部分子集树