《图搜索基础》PPT课件.ppt

1,图搜索基础,2,树的定义和基本术语,定义：,树(Tree)是 n(n0)个结点的有限集。若 n=0，称 为空树；若 n 0，则它满足如下两个条件：(1)有且仅有一个特定的称为根(Root)的结点；(2)其余结点可分为 m(m0)个互不相交的有限集 T1,T2,T3,Tm，其中每一个集合本身又是一棵树，并称为 根的子树(SubTree)。,树的定义是一个递归的定义。,3,树的逻辑结构：树中任一结点都可以有零个或多个直接后继结点 但至多只能有一个直接前趋结点。,T3,T2,T1,基本术语：,结点的度：结点拥有的子树数。,度=0叶子 终端结点,度 0分支结点 非终端 结点 根结点以 外的分支 结点称为 内部结点,树的度：树内各结点的度的最大值。,结点的祖先：从根到该结点所经分支上的所有结点。,结点的子孙：以某结点为根的子树中的任一结点。,第 1 层,第 2 层,第 3 层,第 4 层,堂兄弟 双亲在同一层的结点,树的深度：树中结点的最大层次。,有序树：树中结点的各子树从左至右有次序(最左边的为第一个孩子)。,无序树：树中结点的各子树无次序。,结点：数据元素+指向子树的分支,森林：是 m(m0)棵互不相交的树的集合。,一棵树可以看成是一个特殊的森林。,把根结点删除树就变成了森林。,给森林中的各子树加上一个双亲结点，森林就变成了树。,树,森林,一定是,不一定是,4,定义：,图(Graph)是一种复杂的非线性数据结构，由顶 点集合及顶点间的关系(也称弧或边)集合组成。可 以表示为：G(V,VR)其中 V 是顶点的有穷非空集合；VR 是顶点之间关系 的有穷集合，也叫做弧或边集合。弧是顶点的有序对，边是顶点的无序对。,图的定义和基本术语,5,度：无向图中顶点 v 的度是和 v 相关联的边的数目，记为TD(v)。,入度：有向图中以顶点 v 为终点的弧数目称为 v 的入度，记ID(v)。,出度：有向图中以顶点 v 为起点的弧数目称为 v 的出度，记OD(v)。,度：入度和出度之和，即：TD(v)=ID(v)+OD(v)。,如果顶点 vi 的度为 TD(vi)，则一个有 n 个顶点 e 条边(弧)的图，满足如下关系：,终端顶点：有向图中把出度为 0的顶点称为终端顶点。,6,路径：从顶点v到v的路径是一个顶点序列(v=vi,0,vi,1,vi,m=v)，满足(vi,j-1,vi,j)VR 或 VR(1 j m)。,对于有向图，路径也是有向的。,路径长度：路径上边或弧的数目。,回路(环)：第一个顶点和最后一个顶点相同的路径。,简单路径：序列中顶点(两端点除外)不重复出现的路径。,简单回路(简单环)：前后两端点相同的简单路径。,连通：无向图中从顶点v到v有路径，则说v和v是连通的。,连通图：无向图中任意两个顶点都是连通的。,7,连通分量：无向图的极大连通子图；任何连通图的连通分量只有一个，即其本身；非连通图有多个连通分量(非连通图的每一个连通部分)。,强连通图：有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。,强连通分量：有向图的极大强连通子图；任何强连通图的强连通分量只有一个，即其本身；非强连通图有多个强连通分量。,8,对于一个具有n个顶点的图，可用两个数组存储。其中一个一维数组存储数据元素(顶点)的信息，另一个二维数组(图的邻接矩阵)存储数据元素之间的关系(边或弧)信息。,邻接矩阵：设 G=(V,VR)是具有 n 个顶点的图，顶点的顺序依次为 v1,v2,vn，则 G 的邻接矩阵是具有如下性质的 n 阶方阵：,图的存储结构之数组表示法(邻接矩阵表示法),9,v1 v2 v3 v4,v1 v2 v3 v4 v5,v1 v2 v3 v4,v1 v2 v3 v4 v5,特点：,无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为 n(n-1)/2。,有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n，空间复杂度O(n2)，用于稀疏图时空间浪费严重。,无向图中顶点vi的度 TD(vi)是邻接矩阵中第i行1的个数。,有向图中,顶点vi的出度是邻接矩阵中第i行1的个数。,顶点vi的入度是邻接矩阵中第i列1的个数。,10,网的邻接矩阵可定义为：,v1 v2 v3 v4 v5 v6,v1 v2 v3 v4 v5 v6,11,顶点表结点,边表结点,3,1,4,2,0,4,3,1,2,0,2,1,特点：,若无向图中有n个顶点、e条边，则其邻接表需n个顶点表结点和2e个边表结点。适宜存储稀疏图。,无向图中顶点 vi 的度为第 i 个单链表中的结点数。,图的存储结构之邻接表(类似于树的孩子链表表示法),12,0,1,2,3,2,1,3,0,v1,v3,v4,v2,邻接表,逆邻接表,顶点 vi 的出度为第 i 个单链 表中的结点个数。,特点：,顶点 vi 的入度为整个单链表 中邻接点域值是i-1的结点 个数。,找出度易，找入度难。,找入度易，找出度难。,顶点 vi 的入度为第 i 个单链 表中的结点个数。,顶点 vi 的出度为整个单链表 中邻接点域值是i-1的结点 个数。,13,从图的任意指定顶点出发，依照某种规则去访问图中所有顶点，且每个顶点仅被访问一次，此过程叫做图的遍历。,图的遍历按照广度优先和深度优先规则去实施，通常有广度优先遍历法(Breadth_Frist SearchBFS)和深度优先遍历法(Depth_First SearchDFS)两种。,图的遍历,14,方法：从图的某一结点出发，首先依次访问该结点的所有邻接顶点 Vi1,Vi2,Vin,再依次访问与 Vi1,Vi2,Vin 相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。,例：,广度优先遍历：,V1,V2,V3,V4,V5,V6,V7,V8,V1,V3,V2,V7,V6,V5,V4,V8,V1,V2,V3,V5,V4,V7,V6,V8,图的遍历之广度优先遍历(BFS),15,方法：首先访问指定的起始顶点，然后在与该顶点邻接的顶点中选择一个未被访问的顶点进行访问，接着再从现在访问的顶点的 邻接顶点中任意选择一个未被访问的顶点进行访问，如此继续，若 到达无未被访问的邻接顶点的顶点时，则退回到最近访问过的那 个顶点，若它还有未被访问的邻接顶点，则选择一个进行访问。重复上述过程，直到全部顶点都访问完毕。,例：,V1,深度优先遍历：,V2,V4,V8,V5,V3,V6,V7,V1,V2,V5,V8,V4,V3,V6,V7,V1,V2,V4,V8,V5,V3,V7,V6,V1,V2,V5,V8,V4,V3,V7,V6,V1,V3,V6,V7,V2,V4,V8,V5,图的遍历之深度优先遍历(DFS),16,2 显式图&隐式图,在路径问题、连通性问题和网络优化等问题中，图的结构是显式给出的，包括图中的顶点、边及权重，这类图称为显式图，即一般意义上的图。,隐式图是由问题的初始结点，为了求解或求证问题，根据问题的规则(一般是由题目的意思隐含给出的)，也就是生成子结点的约束条件，逐步扩展结点，直至得到目标结点为止的一个隐式的图。,两种典型的隐式图：子集树，排列树,17,2 显式图&隐式图-子集树,当要求解的问题需要在n 个元素的子集中进行搜索，其搜索空间树被称作子集树(subset tree)。这n个元素都在子集中或被选取记为1，不在子集中或被舍去记为0，这样搜索空间为：(0,0,0,0),(0,0,0,1),(0,0,1,0),(0,0,1,1),(1,1,1,1)。,18,2 显式图&隐式图-子集树,共2n 个状态。若表示为树形结构就是一棵有2n个叶结点的二叉树，对树中所有分支进行遍历的算法都必须耗时O(2n),19,2 显式图&隐式图-排列树,当要求解的问题需要在n个元素的排列中搜索问题的解时，解空间树被称作排列树(permutation tree)。搜索空间为：(1,2,3,n-1,n),(2,1,3,n-1,n),(2,3,1,n-1,n),(2,3,4,1,n-1,n),.(n,n-1,3,2,1),第一个元素有n 种选择，第二个元素有n-1种选择，第三个元素有n-2种选择，第n个元素有1种选择，共计n!个状态。若表示为树形就是一个n度树，这样的树有n!个叶结点，所以每一个遍历树中所有节点的算法都必须耗时O(n!),20,2 显式图&隐式图-排列树,21,3 图搜索术语&方法分类,穷举搜索（盲目搜索）是对图的最基本的搜索算法，是蛮力策略的一种表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规则，盲目搜索的方法。,启发式搜索是利用一些启发信息，提前判断出先搜索哪些状态可能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性质，选用合适的细则，提高搜索的效率。,搜索分为两大类：,隐含地检查所有可能情况,22,3 图搜索术语&方法分类,问题状态:树中的每一个结点确定所求解问题的一个问题状态。状态空间:由根结点到其它结点的所有路径（分支），就确定了这个问题的状态空间。解状态:是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了该解空间中的一个元组。答案状态:是这样一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解（即它满足隐式约束条件）。状态空间树:解空间的树结构，又称隐式图。,23,3 图搜索术语&方法分类,活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。E-结点：当前正在生成其儿子结点的活结点叫E-结点（正在扩展的结点）。死结点：不再进一步扩展或者其儿子结点已全部生成的结点就是死结点。,24,3 图搜索术语&方法分类,n皇后问题要在n*n的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解。,问题状态,状态空间,解状态,答案状态,25,二、广度优先搜索,1 图的广度优先遍历/搜索算法2 广度优先搜索的应用例7.1 求经过城市最少的路线问题例7.2 走迷宫问题,26,1 广度优先搜索,广度优先搜索,首先访问出发点V，接着依次访问V的所有邻接点Wi，再依次访问分别与Wi邻接的所有未曾访问过的顶点，直至与V相通的顶点都已访问，若此时还有未访问的顶点，则按相同的过程继续。,活结点的扩展是按先来先处理的原则进行。,“先被访问的顶点”的邻接点先于“后被”被访问,27,1 广度优先搜索-算法要素,广度优先搜索：活结点的扩展是按先来先处理的原则进行；但搜索过程中还需暂时保存部分活结点。在算法中用“队”来存储每个E-结点扩展出的活结点。实际应用中，用数组或链表实现队列。开辟数组visited 记录结点的搜索情况。,28,2 广度优先搜索-算法的基本思路,算法设计的基本步骤,1）确定图的存储方式；2）图的遍历过程中的操作，其中包括为输出问题解而进行的存储操作；3）输出问题的结论。,29,1 广度优先搜索-一般算法,图的搜索的不同实现图：邻接表/邻接矩阵队列：链表/数组机制：递归/非递归,广度优先搜索用非 递归实现方便。,/从顶点v 开始的广度优先搜索把顶点v标记为已到达顶点；初始化队列Q，其中仅包含一个元素v;while(Q不空)从队列中删除顶点w;令u 为邻接于w 的顶点;while(u)if(u 尚未被标记)把u 加入队列；把u 标记为已到达顶点；u=邻接于w 的下一个顶点；,30,1 广度优先搜索-邻接表表示图的算法,int visitedn;/n 为结点个数bfs(int k,graph head)int i;queue Q;edgenode*p;/定义队列 InitQueue(Q)；/队列初始化 print(“visit vertex”,k);visitedk=1;/访问源点vk EnQueue(Q,k);/vk已访问，将其入队 while(!QueueEmpty(Q)/队非空则执行 i=DeQueue(Q);/vi出队为E-结点 p=headi.firstedge;/取vi的边表头指针 while(pnull)/扩展E-结点 if(visitedp-adjvex=0)/若vj未访问过 print(“visit vertex”,p-adjvex);/访问vj visitedp-adjvex=1;EnQueue(Q,p-adjvex);/访问过的vj入队 p=p-next;/找vi的下一邻接点,31,1 广度优先搜索-邻接矩阵表示图的算法,bfsm(int k,graph g100,int n)int i,j;queue Q;InitQueue(Q);print(“visit vertex”,k);/访问源点vk visitedk=1;EnQueue(Q,k);while(not QueueEmpty(Q)i=DeQueue(Q);/vi出队 for(j=0;jn;j+)/扩展结点 if(gij=1 and visitedj=0)print(“visit vertex”,j);visitedj=1;EnQueue(Q,j);/访问过的vj入队,32,例7.1 已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少。,2 广度优先搜索的应用-例7.1,如上图表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现要找出一条经过城市最少的一条路线并输出该路线。,33,2 广度优先搜索的应用-例7.1-分析,图的广度优先搜索类似与树的层次遍历，逐层搜索正好可以尽快找到一个结点与另一个结点相对而言最直接的路径。,A B C D E F G H,ABCDEFGH,城市交通图对应的邻接距阵,34,1)将城市A（编号1）入队，队首qh置0，队尾qe置1。2)将队首所指的城市所有可直通的城市入队(如果这个城市在队中出现过就不入队),然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。3)输出最少城市线路。,2 广度优先搜索的应用-例7.1-分析设计,A B C D E F G H,ABCDEFGH,35,1）二维数组jz作为邻接矩阵的存储空间。2）数组sq作为活结点队的存储空间。3）队列的每个结点有两个成员：sqi.city记录入队的城市，sqi.pre记录该城市的前趋城市在队列中的下标，这样通过sqi.pre就可以倒推出最短线路。4）设置数组visited记录已搜索过的城市。,2 广度优先搜索的应用-例7.1-数据结构设计,36,2 广度优先搜索的应用-例7.1-算法设计,search()qh=0;qe=1;sq1.city=1;sq1.pre=0;visited1=1;while(qhqe)/当队不空 qh=qh+1;/结点出队 for(i=1;i=n,i+)/扩展结点 if(jzsqqh.cityi=1 and visitedi=0)qe=qe+1;/结点入队sqqe.city=i;sqqe.pre=qh;visitedi=1;if(sqqe.city=8)out();return;print(“No avaliable way.”);,37,算法分析：时间复杂度是O(n)；空间复杂性为(n2)，包括图本身的存储空间和搜索时辅助空间“队”的存储空间。,out()/输出路径 print(sqqe.city);while(sqqe.pre0)qe=sqqe.pre;print(-,sqqe.city);,2 广度优先搜索的应用-例7.1-算法设计,38,例7.2 迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的“1”），有的是路（图中的“0”）。走迷宫就是从一个小方格沿上、下、左、右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)，出口是右下角(8,8)。根据给定的迷宫，找出一条从入口到出口的路径。,2 广度优先搜索的应用-例7.2,39,2 广度优先搜索的应用-例7.2-分析,(1,1),(3,3),确定图结构本问题的原始描述，与显式图的标准形象有差别。,从入口开始出发，广度优先搜索所有可到达的方格入队，再扩展队首的方格，直到搜索到出口时，便得到一条通路。,40,2 例7.2-分析设计,问题1：如何用所学过的知识来表示现实中的迷宫？,(1,1),(3,3),邻接表？邻接矩阵？利用原有的迷宫数据，检查两点之间是否存在边相连；这样就不必查询任何其他的存储结构了。,二维数组,41,2 例7.2-分析设计,对于迷宫中任意一点A(X,Y)，有四个扩展方向：,问题2：在寻找路径过程中，活结点的扩展？,向上A(X1,Y+0)向下A(X+1,Y+0)向左A(X+0,Y1)向右A(X+0,Y+1)当对应方格值为0，就扩展为活结点。,规律性强，验证简单,为了构造循环体，用数组fx=-1,1 0,0,fy=0,0,-1,1模拟上下左右搜索时下标的变化过程。,函数check，检查当前状态是否合理。,42,2 例7.2-分析设计,问题3：在寻找路径过程中，如何实现所遇到的寻找策略和返回策略的解决？,队的实现：数组队中结点有三个成员：行号、列号、前一个方格在队列中的下标。struct int x,y,pre;sq100;,为了能够倒推出路径,43,2 例7.2-分析设计,另开辟visited 数组记录已搜索过的路径。用迷宫原有的存储空间置元素值为“-1”时，标识已经访问过该方格。,问题4：在搜索路径过程中，对搜索过的路径如何标记？,44,int maze88=0,0,0,0,0,0,0,0,0,1,1,1,1,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0,0,1,1,1,1,1,1,0;int fx4=-1,1,0,0,fy4=0,0,-1,1,;struct int x,y,pre;sq100;int qh,qe,i,j,k;main()search();,2 广度优先搜索的应用-例7.2-算法设计,45,search()qh=0;qe=1;maze11=-1;/代表访问过 sq1.pre=0;sq1.x=1;sq1.y=1;while(qhqe)/当队不空 qh=qh+1;/出队 for(k=1;k=4,k=k+1)/搜索可达的方格 i=sqqh.x+fxk;j=sqqh.y+fyk;if(check(i,j)=1)qe=qe+1;/入队 sqqe.x=i;sqqe.y=j;sqqe.pre=qh;mazeij=-1;if(sqqe.x=8 and sqqe.y=8)out();return;print(“No avaliable way.”);,check()int flag=1;if(i8 or j8)flag=0;/是否在迷宫内 if(mazeij=1ormazeij=-1)flag=0;/是否可行 return(flag);,46,out()/输出路径 print(“(”sqqe.x,“,”,sqqe.y,“)”);while(sqqe.pre0)qe=sqqe.pre;print(-,“,”,sqqe.x,“,”,sqqe.y,“)”);,算法分析：时间复杂度是O(n)；空间复杂性为(n2)，包括图本身的存储空间和搜索时辅助空间“队”的存储空间。,2 例7.2-算法设计及分析,47,三、深度优先搜索,1 图的深度优先遍历/搜索算法2 深度优先搜索的应用例7.2 走迷宫问题例7.3 七巧板涂色问题例7.4 割点的判断及消除,48,1 深度优先搜索,首先访问出发点V1，然后依次搜索其每个邻接点W。若W为曾访问过，则以W为新的出发点继续深度优先搜索，直至和V有路径相通的点全部访问。若此时还有未访问点，则以此作新出发点继续。,49,深度优先与广度优先的策略比较：区别在于扩展结点的过程；广度优先搜索，扩展E-结点的所有邻接点，E-结点就成为一个死结点。一个结点只有一次成为“活结点”。深度优先搜索，扩展的是E-结点的邻接结点中的一个，并将其作为新的E-结点继续扩展；当前E-结点仍为活结点，待搜索完其子结点后，回溯到该结点扩展它的其它未搜索的邻接结点。一个结点可能多次成为“活结点”。,1 深度优先搜索,50,2 深度优先搜索的应用-例7.2-分析2,(1,1),(3,3),确定图结构本问题的原始描述，与显式图的标准形象有差别。,从始点出发，按深度优先搜索方式搜索该图，一直向着可通行的下一个方格行进，直到搜索到终点时，便得到一条通路。若行不通时，则返回上一个方格，继续搜索其他方向。,有没有其他方法？,51,2 深度优先搜索的应用-例7.2-分析2,数据结构设计：用迷宫本身的存储空间除了记录走过的信息，还要标识是否可行：mazeij=3 标识走过的方格；mazeij=2 标识走入死胡同的方格；当一个方格四个方向都搜索完还没有走到出口(存储为2)，说明该方格或无路可走或只能走入了“死胡同”。最后存储为“3”的方格为可行的方格。,函数check，检查当前状态是否合理。,约束条件,52,2 深度优先搜索的应用-例7.2-算法2,int maze88=0,0,0,0,0,0,0,0,0,11,1,1,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0,0,1,1,1,1,1,1,0;fx4=1,-1,0,0,fy4=0,0,-1,1;int i,j,k,total;main()int total=0;maze11=3;/入口坐标设置已走标志 search(1,1);print(“Total is”,total);/统计总步数,53,search(int i,int j)int k,newi,newj;for(k=1;k=4;k+)/搜索可达的方格 if(check(i,j,k)=1)newi=i+fxk;newj=j+fyk;mazenewinewj=3;/来到新位置后,设置已走过标志 if(newi=8 and newj=8)/到出口则输出,否则下一步递归 Out();else search(newi,newj);mazeij=2;/某一方格只能走入死胡同,2 深度优先搜索的应用-例7.2-算法2,54,Out()int i,j;for(i=1;i=8;i+)print(“换行符”);for(j=1;j=8;j+)if(mazeij=3)print(“V”);total+;/统计总步数 else print(“*”);,2 深度优先搜索的应用-例7.2-算法2,check(int i,int j,int k)int flag=1;i=i+fxk;j=j+fyk;/是否在迷宫内 if(i8 or j8)flag=0;else if(mazeij0)/是否可行 flag=0;return(flag);,55,2 深度优先搜索的应用-例 7.2-算法说明2,注意：用广度优先策略，搜索出的是一条最短的路径，而用深度优先搜索则只能找出一条可行的路径，而不能保证是最短的路径。,