已阅读5页,还剩16页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1,第4章 基本搜索与遍历,2,4.1 基本概念,搜索: 一种通过系统地检查给定数据对象的每个结点,寻找一条从开始结点到答案结点的路径,最终输出问题解的求解方法. 遍历:要求系统地检查数据对象的每个结点. 分为:树遍历和图遍历 状态空间:用于描述所求问题的各种可能的情况。每一种情况对应状态空间的一个状态。 分为:初始状态代表搜索开始, 目标(答案)状态代表已求得问题的解,3,问题的求解过程:从初始状态出发,以某种次序系统地检查状态空间的每一个状态,搜索答案状态的过程。 问题的状态空间常用树或图表示,树或图中的一个结点代表问题的一个状态. 穷举搜索=盲目搜索=无知搜索,把所有的状态逐个检查,直到找到解或者检查完。 深度搜索和广度搜索都是无知搜索 有知搜索 已知的信息为指导,排除一部分状态空间。 有时可能找不到解,比如指导搜索的信息是错误的,则会误入歧途。 启发式搜索 使用经验法则,边搜索边评估到达目标状态的剩余距离。,4,4.2 图的搜索和遍历,遍历:遵循某种次序,系统地访问一个数据结构的全部元素,每个元素只访问一次. 实现遍历的关键是规定结点被访问的次序 图 有向图,5,4.2.1 后继结点,在树形结构,一个结点的直接后继结点是他的孩子结点 在图中,一个结点的后继结点是邻接于该结点的所有邻接点。,6,4.2.1 搜索方法,结点的被访问状态: 未访问:一个结点x若尚未访问 未检测:若结点x自身已访问,但其后继结点尚未全部访问 已检测:若结点x的后继结点全部被访问过 所谓检测一个结点x是指算法正从x出发,访问x的某个结点y,x被称为扩展结点,简称E-结点。,7,广度优先搜索 对于一个未检测结点,访问完其全部后继结点后才访问其他未检测结点 深度优先搜索:如果一个算法一旦访问某个结点,该结点成为未检测结点后,便立即被算法检测,成为E-结点,而此时,原E-结点尚未检测完毕,仍处于检测状态,需要在以后适当时候才能继续检测,这种做法成为深度优先搜索,8,图1 深度优先搜索,图2 广度优先搜索,9,活结点未检测结点 死结点其后续结点已全部访问过,10,4.2.2 邻接表类,有向图,指针数组,第i个元素 存储有向图中结点i的地址,11,【程序4-1】 ENode类 enum ColorType White, Gray, Black ; struct ENode int adjVex; ENode* nextArc; ;,12,class Graph /邻接表类 public: Graph(int mSize) /构造仅有n个结点的图的邻接表 n=mSize; a=new ENode* n; for (int i=0; in; i+) ai=NULL; void DFS_Traversal(int* parent); /数组parent保存DFS生成森林 void BFS_Traversal(int* prarent); /数组parent保存BFS生成森林 protected: void DFS(int u, int* parent, ColorType* color);/深度优先访问从u可达结点 void BFS(int u, int* parent, ColorType* color);/广度优先访问从u可达结点 ENode* a; /生成指向ENode类对象的指针数组 int n; /图中结点数目 ;,13,4.2.3 广度优先搜索(准备工作),结点用编号0,1,连续数字表示 定义一个指针数组an,其第i个元素存储有向图中第i个结点的地址 定义一个数组colorn,元素colori可取的值为white,gray,black,分别表示结点i处于未访问,未检测,已检测三种不同状态. 定义一个数组parentn,元素parenti的值表示节点i的双亲结点编号,如parent3=2,表明结点3的双亲结点是2,14,4.2.3 广度优先搜索(解决思路),一个结点一旦成为E-结点,将依次访问完它的全部未访问后继结点. 每访问一个结点,就把它加入活结点表 使用队列作为活结点表。 初始,图的所有结点均为white,即color0n=white 从某个结点u开始,访问u,置coloru=gray,然后依次访问u的各个白色邻接点,当u的所有邻接点访问完后, coloru=black,u结点成为死结点,15,void Graph:BFS_Traversal(int* parent) /将在parent数组中返回以双亲表示法表示的BFS生成森林 ColorType* color=new ColorTypen; /颜色数组 coutendl“BFS:“; for(int u=0; un; u+) coloru=White; parentu=-1; for (u=0; un; u+) if (coloru=White) BFS(u, parent, color); /调用BFS,从未标记的结点出发,遍历其后继结点 delete color; coutendl; ,【程序4-2】 图的广度优先遍历,16,void Graph:BFS(int u, int* parent, ColorType* color) /u =起始节点编号, parent=记录双亲结点,color=结点的访问状态 Queue q(QSize); coloru=Gray; coutnextArc) /检测E-结点u的全部邻接点,总循环次数=图中总边数 int v=w-adjVex; if (colorv=White) colorv=Gray; cout“ “v; parentv=u; /构造BFS生成森林 q.Append(v); /新的活结点进入活结点表q coloru=Black; /将编号为u的结点标记为死结点 ,au存放的结点u的首个后继结点的存放地址,17,2.广度优先树(略) 3.时间分析 邻接表表示时,O(n+e), 邻接矩阵表示时,O(n2) BFS算法的正确性(略),18,4.2.4 深度优先搜索,如果一个遍历算法在访问了E-结点x 的某个后继结点y后,立即把y做为新的E-结点,去访问y的后继结点,直到y检测完后,x才能再次成为E-结点,继续访问x的其他未被访问过的后继结点。 深度优先搜索使用堆栈作为活结点表,19,1.深度优先遍历算法 假定初始时,图G的所有结点都为白色,从图的某个结点u出发的深度优先遍历搜索的递归过程DFS可描述如下: 1)访问结点u,将coloru置成gray; 2)依次从u的邻接点出发,深度优先搜索。,20,【程序4-3】 图的深度优先搜索,void Graph:DFS(int u, int* parent, ColorType* color) coloru=Gray; coutnextArc) int v=w-adjVex; if (
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 江苏省盐城市东台市三仓片区2023-2024学年中考生物仿真试卷含解析
- 江苏省盐城市东台第一教育集团2024届中考语文全真模拟试题含解析
- 2023-2024年《装修工程合作合同样本书范本 》
- 江苏省盐城市大丰区第一共同体达标名校2024年中考语文考试模拟冲刺卷含解析
- 2024年购房合同可以抵押贷款么
- 2024年度《车辆运输合同样本范本》
- 云南省迪庆州香格里拉中学2024届高考数学倒计时模拟卷含解析
- 新疆阿克苏地区沙雅县二中2023-2024学年高三下学期联合考试数学试题含解析
- 武汉市武昌区2024年高三第二次调研数学试卷含解析
- 天津市蓟县康中中学2024年高三六校第一次联考数学试卷含解析
- 国华220kv变电站电气设备及工作原理
- 最新最全中小学教育教学理论试题及答案(多套)
- 护理安全与职业防护培训课件
- 智慧电力大数据平台建设及应用方案
- 初中八年级物理实验通知单和记录单
- 建设单位工程安全、质量管理制度(3篇)
- GCP培训考试题库含答案(完整版)
- 脑卒中患者康复治疗的标准作业流程
- 仓库管理员考核试题与答案
- 服药时间记录表
- DB64-T 243-2018.小流域水土流失综合治理验收技术规范-(高清可复制)
评论
0/150
提交评论