基本搜索与遍历方法.ppt
1,第4章 基本搜索与遍历,2,4.1 基本概念,搜索:一种通过系统地检查给定数据对象的每个结点,寻找一条从开始结点到答案结点的路径,最终输出问题解的求解方法.遍历:要求系统地检查数据对象的每个结点.分为：树遍历和图遍历状态空间:用于描述所求问题的各种可能的情况。每一种情况对应状态空间的一个状态。分为：初始状态代表搜索开始,目标（答案）状态代表已求得问题的解,3,问题的求解过程：从初始状态出发，以某种次序系统地检查状态空间的每一个状态，搜索答案状态的过程。问题的状态空间常用树或图表示,树或图中的一个结点代表问题的一个状态.穷举搜索=盲目搜索=无知搜索，把所有的状态逐个检查，直到找到解或者检查完。深度搜索和广度搜索都是无知搜索有知搜索已知的信息为指导，排除一部分状态空间。有时可能找不到解，比如指导搜索的信息是错误的，则会误入歧途。启发式搜索使用经验法则，边搜索边评估到达目标状态的剩余距离。,4,4.2 图的搜索和遍历,遍历:遵循某种次序,系统地访问一个数据结构的全部元素,每个元素只访问一次.实现遍历的关键是规定结点被访问的次序图有向图,5,4.2.1 后继结点,在树形结构，一个结点的直接后继结点是他的孩子结点在图中，一个结点的后继结点是邻接于该结点的所有邻接点。,6,搜索方法,结点的被访问状态：未访问：一个结点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 ENodeint 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,即color0.n=white从某个结点u开始，访问u，置coloru=gray，然后依次访问u的各个白色邻接点，当u的所有邻接点访问完后，coloru=black，u结点成为死结点,15,void Graph:BFS_Traversal(int*parent)/将在parent数组中返回以双亲表示法表示的BFS生成森林ColorType*color=new ColorTypen;/颜色数组coutendlBFS:;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(colorv=White)parentv=u;DFS(v,parent,color);coloru=Black;fu=time+;/记录第2个时间,结点号,21,2.深度优先树(略)3.时间分析 邻接表表示时,O(n+e)邻接矩阵表示时,O(n2)4.深度优先搜寻的性质(略),
