《图搜索基础》ppt课件

图搜索基础一、图搜索概论1树与图的回顾5树和图的定义、基本术语5图的存储结构D树和图的遍历方法气2显式图&隐式图“3图搜索术语&方法分类二、广度优先搜索三、深度优先搜索|树与图的回顾ss树型结构(非线性结构)根度吊人市伟树的意义?具有层次关系自然界:枪余家谱北沥仁力林维一吴自例人类社会壬肉留市涉腐市“威海市行政组织机构历下区市中区“.。历城区编译:用树表示源程序的语法结构计算机领域汇数据库系统:用树组织信息算法分析,用树描述执行过程树的定义和基本术语定义:树(Tree)是n(z>z0)个结点的有限集。若n=0,称为空树;若m>0,则它满足如下两个条件:(D有且仅有一个特定的称为根(Root)的结点;(2)其余结点可分为m(m>0)个互不相交的有限集T72,Ta.s7m,其中每一个集合本身又是一椎树,并称为根的子树(SubTree)。树的定义是一个递归的定义。度=0一移绪康,非空租中无前驱婉点的婴怪基本术语:第1层蘑铡蚤谧者点拥有的子树数'叶子乙终端结点大A飞度丿0D分支结点个_一一。十具端结点善。根结点以3_外的分文结焯称为森林:是力(m>0)椰互不相交的树的集合。基克第内鄯绪库把根结点删除树就变成了森林。一定是P树瘀林一标树可以看成是一个特殊的椒林。不一定是给椒林中的各子树加上一个双亲结点,森林就变成了树。图的定义和基本术语定义:图(Graph)是一种复杂的非线性数据结构,由顶点集合及顶点间的关系(也称弧或边)集合组成。可以表示为:G=(PIPRD其中卫是顶点的有穷非空集合;VR是顶点之间关系的有穷集合,也叫做弧或边集合。弧是顶点的有序对,边是顶点的无序对。图的意义。图是一种限制最少的数据结构。D更接近现实;a实际问题中很多数据关系都可以抽象成图,相关问题则可利用图的基本算法进行求解,很早就有专门研究图的是一门数学学科“图论“。图论中著名算法;求最小生成树的Kruskal算法、求最短路径的Dijkstra算法和Floyd算法、求二分图最大匹配(指派问题)的匈牙利算法、求一般图最大匹配的Edmonds“花“算法、求网络最大流量和最小割集算法等。其中一些算法在数据结构课程中已经学习过。基本术语:顶点:图中的数据元素。弧:若<v,y>EVR,则<y,w>表示从y到w的一条弧,世称v为弧尾,称w为弧头,此时的图称为有向图。Gu=(Pu41)卯=lpoya4伟L=<7Ta>y<Pa>y<a4Py<办>】边:若<p,w>EYR必有<w,7>三VR,则以无序个对(v,W)代表这两个有序对,表示y和w之间的一条边,此时的图称为无向图。Gz巳(yz，Ez)yz=蓼l，TaPanay5厂=(pop2),(Pba(Poya)(Poys),(pa7(Paps)无向图无向图中边的取值范围:0SeSn(a-1)2。(r表示图中顶点数目,e表示边的数目,世不考虚顶点到自身的边)完全图:有a(z-U/2条边的无向图(即:无向图中每两个顶点间都存在一条边)称为完全图。有向图中弧的取值范围:0SeSn(n-UD。(r表示图中顶点数目,e表示弧的数目,世不考虚顶点到自身的孟)有向完全图:有n(a-U条弧的有向图(即:有向图中每两个顶点间都存在着方向相反的两条弧)称汊为有向完全图。燧简单图:没有环且每两个顶点间最多只有一条边相连的图。稀疏图:含有很少条边或弧的图。稠密图:含有很多条边或弧的接近完全图的图。权:与图的边或弧相关的数,这些数可以表示从一个顶点到另一个顶点的距离或耗费。网:带权的图。