基本搜索与遍历方法.ppt

第4章 基本搜索与遍历 4.1 基本概念 问题的求解过程：从初始状态出发，以某种次序系统地检查状态空间的每一个状态，搜索答案状态的过程。 问题的状态空间常用树或图表示,树或图中的一个结点代表问题的一个状态. 穷举搜索=盲目搜索=无知搜索，把所有的状态逐个检查，直到找到解或者检查完。 深度搜索和广度搜索都是无知搜索 有知搜索 已知的信息为指导，排除一部分状态空间。 有时可能找不到解，比如指导搜索的信息是错误的，则会误入歧途。 启发式搜索 使用经验法则，边搜索边评估到达目标状态的剩余距离。 4.2 图的搜索和遍历 4.2.1 后继结点 在树形结构，一个结点的直接后继结点是他的孩子结点 在图中，一个结点的后继结点是邻接于该结点的所有邻接点。 4.2.1 搜索方法 结点的被访问状态： 未访问：一个结点x若尚未访问 未检测：若结点x自身已访问,但其后继结点尚未全部访问 已检测：若结点x的后继结点全部被访问过 所谓检测一个结点x是指算法正从x出发，访问x的某个结点y，x被称为扩展结点，简称E-结点。 广度优先搜索 对于一个未检测结点,访问完其全部后继结点后才访问其他未检测结点 深度优先搜索:如果一个算法一旦访问某个结点，该结点成为未检测结点后，便立即被算法检测，成为E-结点，而此时，原E-结点尚未检测完毕，仍处于检测状态，需要在以后适当时候才能继续检测，这种做法成为深度优先搜索 活结点—未检测结点 死结点—其后续结点已全部访问过 4.2.2 邻接表类 有向图 【程序4-1】 ENode类 enum ColorType{ White, Gray, Black }; struct ENode { int adjVex; ENode* nextArc; }; class Graph //邻接表类 { public: Graph(int mSize) //构造仅有n个结点的图的邻接表 { n=mSize; a=new ENode* [n]; for (int i=0; in; i++) a[i]=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; //图中结点数目 }; 4.2.3 广度优先搜索（准备工作） 结点用编号0,1,…连续数字表示 定义一个指针数组a[n],其第i个元素存储有向图中第i个结点的地址 定义一个数组color[n],元素color[i]可取的值为white,gray,black,分别表示结点i处于未访问,未检测,已检测三种不同状态. 定义一个数组parent[n],元素parent[i]的值表示节点i的双亲结点编号,如parent[3]=2,表明结点3的双亲结点是2 4.2.3 广度优先搜索（解决思路） 一个结点一旦成为E-结点,将依次访问完它的全部未访问后继结点. 每访问一个结点，就把它加入活结点表 使用队列作为活结点表。 初始,图的所有结点均为white,即color[0..n]=white 从某个结点u开始，访问u，置color[u]=gray，然后依次访问u的各个白色邻接点，当u的所有邻接点访问完后， color[u]=black，u结点成为死结点 void Graph::BFS_Traversal(int* parent) { //将在parent数组中返回以双亲表示法表示的BFS生成森林 ColorType* color=new ColorType[n]; //颜色数组 coutendlBFS:; for(int u=0; un; u++) { color[u]=White; parent[u]=-1; } for (u=0; un; u++) if (color[u]==White) BFS(u, parent, color); //调用BFS，从未标记的结点出发，遍历其后继结点 d