基本搜索与遍历方法.ppt

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 (