基本搜索与遍历方法

《基本搜索与遍历方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章基本搜索与遍历14.1基本概念搜索:一种通过系统地检查给定数据对象的每个结点,寻找一条从开始结点到答案结点的路径,最终输出问题解的求解方法.遍历:要求系统地检查数据对象的每个结点.分为：树遍历和图遍历状态空间:用于描述所求问题的各种可能的情况。每一种情况对应状态空间的一个状态。分为：初始状态—代表搜索开始,目标（答案）状态—代表已求得问题的解2问题的求解过程：从初始状态出发，以某种次序系统地检查状态空间的每一个状态，搜索答案状态的过程。问题的状态空间常用树或图表示,树或图中的一个结点代表问题的一个状态.穷举搜索=盲目搜索=无知搜索，把所有的状态逐个检查，

2、直到找到解或者检查完。深度搜索和广度搜索都是无知搜索有知搜索已知的信息为指导，排除一部分状态空间。有时可能找不到解，比如指导搜索的信息是错误的，则会误入歧途。启发式搜索使用经验法则，边搜索边评估到达目标状态的剩余距离。34.2图的搜索和遍历遍历:遵循某种次序,系统地访问一个数据结构的全部元素,每个元素只访问一次.实现遍历的关键是规定结点被访问的次序图有向图44.2.1后继结点在树形结构，一个结点的直接后继结点是他的孩子结点在图中，一个结点的后继结点是邻接于该结点的所有邻接点。54.2.1搜索方法结点的被访问状态：未访问：一个结点x若尚未访问未检测：若结点x自身

3、已访问,但其后继结点尚未全部访问已检测：若结点x的后继结点全部被访问过所谓检测一个结点x是指算法正从x出发，访问x的某个结点y，x被称为扩展结点，简称E-结点。6广度优先搜索对于一个未检测结点,访问完其全部后继结点后才访问其他未检测结点深度优先搜索:如果一个算法一旦访问某个结点，该结点成为未检测结点后，便立即被算法检测，成为E-结点，而此时，原E-结点尚未检测完毕，仍处于检测状态，需要在以后适当时候才能继续检测，这种做法成为深度优先搜索7图1深度优先搜索图2广度优先搜索8活结点—未检测结点死结点—其后续结点已全部访问过94.2.2邻接表类有向图指针数组，第i个

4、元素存储有向图中结点i的地址10【程序4-1】ENode类enumColorType{White,Gray,Black};structENode{intadjVex;ENode*nextArc;};11classGraph//邻接表类{public:Graph(intmSize)//构造仅有n个结点的图的邻接表{n=mSize;a=newENode*[n];for(inti=0;i

5、arent);//数组parent保存BFS生成森林protected:voidDFS(intu,int*parent,ColorType*color);//深度优先访问从u可达结点voidBFS(intu,int*parent,ColorType*color);//广度优先访问从u可达结点ENode**a;//生成指向ENode类对象的指针数组intn;//图中结点数目};124.2.3广度优先搜索（准备工作）结点用编号0,1,…连续数字表示定义一个指针数组a[n],其第i个元素存储有向图中第i个结点的地址定义一个数组color[n],元素color[i

6、]可取的值为white,gray,black,分别表示结点i处于未访问,未检测,已检测三种不同状态.定义一个数组parent[n],元素parent[i]的值表示节点i的双亲结点编号,如parent[3]=2,表明结点3的双亲结点是2134.2.3广度优先搜索（解决思路）一个结点一旦成为E-结点,将依次访问完它的全部未访问后继结点.每访问一个结点，就把它加入活结点表使用队列作为活结点表。初始,图的所有结点均为white,即color[0..n]=white从某个结点u开始，访问u，置color[u]=gray，然后依次访问u的各个白色邻接点，当u的所有邻接点访

7、问完后，color[u]=black，u结点成为死结点14voidGraph::BFS_Traversal(int*parent){//将在parent数组中返回以双亲表示法表示的BFS生成森林ColorType*color=newColorType[n];//颜色数组cout<

8、delete[]color;cout<