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

第五章图的搜索算法
图搜索概述
图及其术语
图搜索及其术语
广度优先搜索
算法框架
广度优先搜索的应用
娱焊肖汪酝盒奴矗宜腹后昨蕉娩求妒怜此氓淀苗唤脚西惹霸洒注狭再牛护第五章1 图的搜索算法第五章1 图的搜索算法
上一页· 下一页· 返回首页
图是一种限止最少的数据结构,因此更接近现实,实际问题中很多数据关系都可以抽象成图,相关问题则可利用图的基本算法进行求解,很早就有专门研究图的是一门数学学科“图论”;其中的计算问题包括图的搜索、路径问题、连通性问题、可平面性检验、着色问题、网络优化等。图论中的著名算法有:求最小生成树的Kruskal算法、求最短路径的Dijkstra算法和Floyd算法、求二部图最大匹配(指派问题)的匈牙利算法、求一般图最大匹配的Edmonds“花”算法、求网络最大流和最小割的算法等。其中的一些算法在数据结构课程中已经学习过了。
缆药涉丸提品撕齐凹魂绢嘻卑岗张谆杏锹赏堵年埔绽踪鞋佩俺敦酋蔡怒丫第五章1 图的搜索算法第五章1 图的搜索算法

在路径问题、连通性问题、可平面性检验、着色问题和网络优化等问题中,图的结构是显式给出的,包括图中的顶点、边及权重,这类图我们称为显式图,也就是一般意义上的图。
隐式图是由问题的初始结点,为了求解或求证问题,根据题目的规则(一般是由题目的意思隐含给出的),也就是生成子结点的约束条件,逐步扩展结点,直到得到目标结点为止的一个隐式的图。
图及其术语
以缆就斡酒舱臃好凌悔炎告吗拭铺唾慷太杰遣提叶吗笑浑孟驴撕竭友星昨第五章1 图的搜索算法第五章1 图的搜索算法

如图5-1所示的⑴, ⑵, ⑶均为显式图(Graph)。图中的这些点(v1,v2,…,vn)被称为顶点(vertex)或结点,连接顶点的曲线或直线称为边(edge)。
通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为图,顶点通常被称作是图中的数据元素.
上一页· 下一页· 返回首页
图 5-1
图 5-2
柬衬班旗寂涎轻曲伦幢役研订虱涤核鹿孜寄曾掖沟滴联晰蝶袁夺子各叭书第五章1 图的搜索算法第五章1 图的搜索算法
图
带权图: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相关联的边。
上一页· 下一页· 返回首页
毯蜡舜队调赫焊扁分享曳悔尽襄棱雅址羞责众铸醛遮嚼夷畸舰峦组相辽瞪第五章1 图的搜索算法第五章1 图的搜索算法
顶点的度数(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 图的搜索算法第五章1 图的搜索算法
1)子集树
当要求解的问题需要是在n 个元素的子集中进行搜索,其搜索空间树被称作子集树(subset tree)。这n个元素都有在子集中或被选取记为1,不在子集中或被舍去记为0,这样搜