《最新图的搜索算法1ppt课件.ppt》由会员分享，可在线阅读，更多相关《最新图的搜索算法1ppt课件.ppt（168页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、上一页 下一页 返回首页 图图是一种限止最少的数据结构，因此更接近现实，实是一种限止最少的数据结构，因此更接近现实，实际问题中很多数据关系都可以抽象成图，相关问题则可利际问题中很多数据关系都可以抽象成图，相关问题则可利用图的基本算法进行求解，很早就有专门研究图的是一门用图的基本算法进行求解，很早就有专门研究图的是一门数学学科数学学科“图论图论”；其中的计算问题包括图的搜索、路径；其中的计算问题包括图的搜索、路径问题、连通性问题、可平面性检验、着色问题、网络优化问题、连通性问题、可平面性检验、着色问题、网络优化等。图论中的著名算法有：求最小生成树的等。图论中的著名算法有：求最小生成树的Krusk
2、al算法、算法、求最短路径的求最短路径的Dijkstra算法和算法和Floyd算法、求二部图最算法、求二部图最大匹配（指派问题）的匈牙利算法、求一般图最大匹配的大匹配（指派问题）的匈牙利算法、求一般图最大匹配的Edmonds“花花”算法、求网络最大流和最小割的算法等。算法、求网络最大流和最小割的算法等。其中的一些算法在数据结构课程中已经学习过了。其中的一些算法在数据结构课程中已经学习过了。 2）排列树）排列树 上一页上一页 下一页下一页 返回返回首页首页 当要求解的问题需要在当要求解的问题需要在n n 元素的排列中搜索问题的解元素的排列中搜索问题的解时，解空间树被称作时，解空间树被称作排列树（
3、排列树（permutation treepermutation tree）。搜索空间为：搜索空间为：（1 1，2 2，3 3，n-1n-1，n n）, , （2 2，1 1，3 3，n-1n-1，n n）, , （2 2，3 3，1 1，n-1n-1，n n）, ,（2 2，3 3，4 4，1 1，n-1n-1，n n）, ,（n n，n-1n-1，3 3，2 2，1 1） 第一个元素有第一个元素有n 种选择，第二个元素有种选择，第二个元素有n-1种选择，第种选择，第三个元素有三个元素有n-2种选择，种选择，第，第n个元素有个元素有1种选择，共种选择，共计计n!个状态。若表示为树形就是一个个状
4、态。若表示为树形就是一个n度树，这样的树有度树，这样的树有n! 个叶结点，所以每一个遍历树中所有节点的算法都必须耗个叶结点，所以每一个遍历树中所有节点的算法都必须耗时时O(n! ) 上一页 下一页 返回首页图图5-3 n=4的部分子集树的部分子集树 12503418 X1=115121o75173133282623211383292419454035615651141196416303227252220234 X2=2341 3 41 241 23X3=311 43 42 32 43 44 3 4 2 3 2 4 3 4 1 3 x4=1 4 4图的存储图的存储 1 1）邻接矩阵法邻接矩阵法
5、上一页上一页 下一页下一页 返回返回首页首页 邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵，是表示顶点之间相邻关系的矩阵，设设G=(V,E)G=(V,E)是具有是具有n n个顶点的个顶点的图图，则，则G G的邻接矩阵可定义为：的邻接矩阵可定义为： Ai,j=1, Ai,j=1, 若（若（Vi,Vj)Vi,Vj)或或是是E(G)E(G)中的边。中的边。 Ai,j=0, Ai,j=0, 若若 (Vi,Vj)(Vi,Vj)或或不是不是E(G)E(G)中的边。中的边。若若G G是是网络网络，则邻接矩阵可定义为：，则邻接矩阵可定义为： Ai,j=WAi,j=Wij ij 若（若（Vi,Vj)Vi,Vj)
6、或或属于属于E(G);E(G); Ai,j=0或或 若（若（Vi,Vj）或）或 不属于不属于E(G); 其中，其中，Wij表示边上的权值，表示边上的权值，表示一个计算机允许的，大于表示一个计算机允许的，大于所有边上权值的数；所有边上权值的数； 上一页上一页 下一页下一页 返回返回首页首页2 2）邻接表）邻接表 上一页上一页 下一页下一页 返回首页返回首页 例例11 对于图对于图G G中的每个结点中的每个结点Vi, Vi, 把所有邻接于把所有邻接于ViVi的顶点的顶点VjVj链成一个链成一个单链表，这个单链表就称为顶点单链表，这个单链表就称为顶点ViVi的邻接表。的邻接表。 邻接表由边表和顶点两
7、部分组成。邻接表由边表和顶点两部分组成。 边表边表为一个为一个单链表单链表，每个表结点均有两个域：，每个表结点均有两个域： 邻接点域邻接点域adjvexadjvex，存放与，存放与vivi相邻接的顶点相邻接的顶点v vj j的序号的序号j j。 链 域链 域 n e x tn e x t ， 将 邻 接 表 的 所 有 表 结 点 链 在 一 起 。， 将 邻 接 表 的 所 有 表 结 点 链 在 一 起 。 顶 点 表顶 点 表 为 一 数 组 ， 每 个 元 素 均 有 两 个 域 ：为 一 数 组 ， 每 个 元 素 均 有 两 个 域 ： 顶 点 域顶 点 域 v e r t e x
8、v e r t e x ， 存 放 顶 点， 存 放 顶 点 v vi i的 信 息的 信 息 指针域指针域firstedgefirstedge， v vi i的边表的头指针。的边表的头指针。 对于无向图来说，对于无向图来说，ViVi的邻接表中每个表结点都对应于与的邻接表中每个表结点都对应于与ViVi相关联的一条边，相关联的一条边， 对于有向图来说，对于有向图来说，ViVi的邻接表中每个表结点对应于的邻接表中每个表结点对应于ViVi为始点为始点射出的一条边。射出的一条边。 图7.1 上一页上一页 下一页下一页 返回首返回首页页图图5-5 图图5-1中（中（1）图的邻接表）图的邻接表 5.1.2
9、 图搜索及其术语1 1穷举搜索与启发式搜索穷举搜索与启发式搜索 穷举搜索穷举搜索是对图的最基本的搜索算法，是蛮力策略的一种是对图的最基本的搜索算法，是蛮力策略的一种表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规则，盲目搜索的方法。依次运用规则，盲目搜索的方法。 启发式搜索启发式搜索是利用一些是利用一些启发信息启发信息，提前判断出先搜索哪些，提前判断出先搜索哪些状态可能尽快找到问题的解或某些情况不可能取到最优解，从状态可能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性
10、而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性质，选用合适的细则，提高搜索的效率。质，选用合适的细则，提高搜索的效率。 上一页 下一页 返回首页2相关概念和术语 上一页上一页 下一页下一页 返回返回首页首页 问题状态问题状态: :树中的每一个结点确定所求解问题的一个问题状态。树中的每一个结点确定所求解问题的一个问题状态。状态空间状态空间: :由根结点到其它结点的所有路径（分支），就确定由根结点到其它结点的所有路径（分支），就确定 了这个问题的状态空间。了这个问题的状态空间。解状态解状态: :是这样一些问题状态是这样一些问题状态S，对于这些问题状态，由根到，对于这些问题状态，由根到S 的
11、那条路径确定了这解空间中的一个元组。的那条路径确定了这解空间中的一个元组。 答案状态答案状态: :是这样的一些解状态是这样的一些解状态S，对于这些解状态而言，由，对于这些解状态而言，由 根到根到S的这条路径确定了这问题的一个解的这条路径确定了这问题的一个解状态空间树状态空间树: :解空间的树结构又称隐式图。解空间的树结构又称隐式图。 活结点活结点：如果已生成一个结点而它的所有儿子结点还没有：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。全部生成，则这个结点叫做活结点。 E-结点结点：当前正在生成其儿子结点的活结点叫：当前正在生成其儿子结点的活结点叫E-结点（正结点（
12、正 扩展的结点）。扩展的结点）。死结点死结点 ：不再进一步扩展或者其儿子结点已全部生成的生：不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点成结点就是死结点 。5.2.1 算法框架 1算法的基本思路算法的基本思路 算法设计的基本步骤为：算法设计的基本步骤为： 1）确定图的存储方式；确定图的存储方式； 2）图的遍历过程中的操作，其中包括为输出问题解图的遍历过程中的操作，其中包括为输出问题解而进行的存储操作；而进行的存储操作； 3 3）输出问题的结论。输出问题的结论。 上一页 下一页 返回首页5.2 广度优先搜索 2 2算法框架算法框架 上一页上一页 下一页下一页 返回首页返回首页 例例
13、11 从从广度优先搜索定义可以看出活结点的扩展是按先来先处广度优先搜索定义可以看出活结点的扩展是按先来先处理的原则进行的，所以在算法中要用理的原则进行的，所以在算法中要用“队队”来存储每个来存储每个E-E-结点结点扩展出的活结点。为了算法的简洁，抽象地定义：扩展出的活结点。为了算法的简洁，抽象地定义：queuequeue为队列类型，为队列类型，InitQueue( ) InitQueue( ) 为队列初始化函数，为队列初始化函数， EnQueue(QEnQueue(Q，k)k)为入队函数，为入队函数，QueueEmpty(Q) QueueEmpty(Q) 为判断队空函数，为判断队空函数，DeQ
14、ueue(Q) DeQueue(Q) 为出队函数。为出队函数。 实际应用中，用数组或链表实现队列。实际应用中，用数组或链表实现队列。 开辟开辟数组数组visitedvisited记录记录visitedvisited结点的搜索情况。结点的搜索情况。 在算法框架中以输出结点值表示在算法框架中以输出结点值表示“访问访问”。1 1）邻接表表示图的广度优先搜索算法）邻接表表示图的广度优先搜索算法 int visitedn; /n visitedn; /n 为结点个数为结点个数/ /bfs(int k,graph head) int i； queue Q ； edgenode *p； /定义队列定义队列/
15、 InitQueue(Q)； /队列初始化队列初始化/ print(“visit vertex”，k)； / 访问源点访问源点vk/ visitedk=1； 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 (“visitv
16、ertex”，p-adjvex)；/访问访问vj/ visitedp-adjvex=1； EnQueue(Q，p-adjvex)； /访问过的访问过的vj人队人队/ p=p-next ； /找找vi的下一邻接点的下一邻接点/ 2）邻接矩阵表示的图的广度优先搜索算法）邻接矩阵表示的图的广度优先搜索算法上一页上一页 下一页下一页 返回返回首页首页bfsm(int k, graph g100，int n) int i，j； CirQueue Q； InitQueue(Q)； print (visit vertex， k)； /访问源点访问源点vk/ visitedk=1； EnQueue(Q，k)；
17、 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人队人队/ 5.2.2 广度优先搜索的应用 【例1】已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少 【例2】走迷宫问题 上一页 下一页 返回首页【例1】已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少。 算法设计： 上一
18、页 下一页 返回首页 例2 例3 图的广度优先搜索类似与树的层次遍图的广度优先搜索类似与树的层次遍历，逐层搜索正好可以尽快找到一个结点历，逐层搜索正好可以尽快找到一个结点与另一个结点相对而言最直接的路径。与另一个结点相对而言最直接的路径。 如图如图5-6表示的是从城市表示的是从城市A到城市到城市H的交通的交通图。从图中可以看出，从城市图。从图中可以看出，从城市A到城市到城市H要经要经过若干个城市。现要找出一条经过城市最少过若干个城市。现要找出一条经过城市最少一条路线。一条路线。 上一页上一页 下一页下一页 返回首页返回首页 例例2 2 例例33图5-6 表5-1 图5-6的邻接距阵 具体过程如
19、下： 1 1）将城市将城市A A（编号（编号1 1）入队，队首）入队，队首qhqh置置为为0 0、队尾、队尾qeqe置为置为1 1。2 2）将队首所指的城市所有可直通的城将队首所指的城市所有可直通的城市入队市入队( (如果这个城市在队中出现过就不如果这个城市在队中出现过就不入队入队),),然后将队首加然后将队首加1 1，得到新的队首城，得到新的队首城市。重复以上步骤，直到城市市。重复以上步骤，直到城市H H入队为止。入队为止。当搜到城市当搜到城市H H时，搜索结束。时，搜索结束。 3）输出最少城市线路输出最少城市线路。 上一页 下一页 返回首页 例2 例3数据结构设计： 1 1）线性线性数组数
20、组a作为活结点队的存储空间。作为活结点队的存储空间。2 2）队列的每个结点有两个成员：队列的每个结点有两个成员：ai.city记记录入队的城市，录入队的城市，ai.pre记录该城市的前趋城记录该城市的前趋城市在队列中的下标，这样通过市在队列中的下标，这样通过ai.pre就可以就可以倒推出最短线路。倒推出最短线路。3 3）设置数组设置数组visited记录已搜索过的城市。记录已搜索过的城市。 上一页 下一页 返回首页 例2 例3算法如下：search( )( )qh=0; qe=1;sq1.city=1;sq1.pre=0;visited1=1;qh=0; qe=1;sq1.city=1;sq1
21、.pre=0;visited1=1; while( qhqe) / while( qhqe) /当队不空当队不空/ /qh=qh+1; /qh=qh+1; /结点出队结点出队/ / for(i=1;i=n,i+) /for(i=1;i=n,i+) /扩展结点扩展结点/ / if if （jzsqqh.cityi=1 and visitedi=0jzsqqh.cityi=1 and visitedi=0） qe=qe+1; / qe=qe+1; /结点入队结点入队/ /sqqe.city=i;sqqe.pre=qh;visitedqe=1;sqqe.city=i;sqqe.pre=qh;visi
22、tedqe=1;if (sqqe.city=8) out( );if (sqqe.city=8) out( ); print(“No avaliable way.”);print(“No avaliable way.”); 上一页 下一页 返回首页 例2 例3算法分析算法分析：时间复杂度是：时间复杂度是O（n）；空间复杂性为）；空间复杂性为（n2），包括图本身的存储空间和搜索时辅助空间），包括图本身的存储空间和搜索时辅助空间“队队”的存储空间。的存储空间。out( ); /out( ); /输出路径输出路径/ /print(sqqe.city);print(sqqe.city); while(
23、sqqe.pre0)while(sqqe.pre0) qe=sqqe.pre; print(-,sqqe.city); 【例2】走迷宫问题 上一页 下一页 返回首页 例1 例3 迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的“1”1”）有的是路（图中的）有的是路（图中的“0”0”）。走迷宫就是从一个小方格沿上、下、左、）。走迷宫就是从一个小方格沿上、下、左、右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)(1,1)，出口是右下角出口是右下角(8
24、,8)(8,8)。根据给定的迷宫，找出一条从入口到出口的路径。根据给定的迷宫，找出一条从入口到出口的路径。 算法设计： 上一页 下一页 返回首页 例1 例3 从入口开始广度优先搜索可到达的方格入队，再扩展从入口开始广度优先搜索可到达的方格入队，再扩展 队首的方格，直到搜索到出口时算法结束。队首的方格，直到搜索到出口时算法结束。 对于迷宫中任意一点对于迷宫中任意一点A（Y，X），有四个搜索方向：），有四个搜索方向： 向上向上A（Y-1，X） 向下向下A（Y+1，X） 向左向左A（Y，X-1） 向右向右A（Y，X+1） 当对应方格可行（值为当对应方格可行（值为0），就扩展为活结点。），就扩展为活结
25、点。 数据结构设计：数据结构设计： 上一页 下一页 返回首页 例1 例3 用用数组数组做队的存储空间，队中结点有三个做队的存储空间，队中结点有三个成员：行号、列号、前一个方格在队列中的成员：行号、列号、前一个方格在队列中的下标。搜索过的方格不另外开辟空间记录其下标。搜索过的方格不另外开辟空间记录其访问的情况，而是用迷宫原有的存储空间置访问的情况，而是用迷宫原有的存储空间置元素值为元素值为“-1”-1”时，标识已经访问过该方格。时，标识已经访问过该方格。 为了构造循环体，用数组为了构造循环体，用数组fx=1,-1,0,0fx=1,-1,0,0、fy= 0,0,-1,1 fy= 0,0,-1,1
26、模拟上下左右搜索时的下标模拟上下左右搜索时的下标的变化过程。的变化过程。 int jz88= 1,0,0,0,1,0,1,1,0,1,1,1,1,0,1,1, 0,1,1,0,0,1,1,1, 0,1,0,1,1,1,0,1, 1,1,0,1,1,1,0,0,0,0,1,1,1,1,1,0, 1,1,1,0,0,1,1,0, 1,1,1,1,0,0,0,1;struct intcity, pre; sq100;int qh,qe,i,visited100;main( )int i,n=8;for(i=1;i=n,i=i+1) visitedi=0;search( );search( )qh=0
27、; qe=1;sq1.city=1;sq1.pre=0; visited1=1;while( qhqe) /当队不空当队不空/qh=qh+1; /结点出队结点出队/ for(i=1;i=n,i=i+1) /扩展结点扩展结点/if （jzsqqh.cityi=1 and visitedi=0） qe=qe+1; /结点入队结点入队/ sqqe.city=i;sqqe.pre=qh;visitedqe=1;if (sqqe.city=8) out( ); print(“No avaliable way.”);out( ); /输出路径输出路径/print(sqqe.city);while(sqqe
28、.pre0) qe=sqqe.pre; print(-,sqqe.city); 算法分析算法分析： 算法算法的时间复杂度并不复杂是的时间复杂度并不复杂是O O（n n），算法的空间复杂性），算法的空间复杂性为为O O（n n2 2），包括图本身的存储空间和搜索时辅助空间），包括图本身的存储空间和搜索时辅助空间“队队”的的存储空间。存储空间。 上一页 下一页 返回首页 例1 例3 深度优先遍历深度优先遍历首先访问出发点首先访问出发点v v，并将其标记为，并将其标记为已访问过；然后依次从已访问过；然后依次从v v出发搜索出发搜索v v的每个邻接点的每个邻接点w w。若若w w未曾访问过，则以未曾访
29、问过，则以w w为新的出发点继续进行深度为新的出发点继续进行深度优先遍历，直至图中所有和源点优先遍历，直至图中所有和源点v v有路径相通的顶点有路径相通的顶点均已被访问为止。均已被访问为止。 若此时图中仍有未访问的顶点，则另选一个尚若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。中所有顶点均已被访问为止。5.3 深度优先搜索深度优先搜索 深度搜索与广度搜索的相近，最终都要深度搜索与广度搜索的相近，最终都要扩展一个结点的所有子结点扩展一个结点的所有子结点. . 区别在于对扩展结点过程，深度搜
30、索扩区别在于对扩展结点过程，深度搜索扩展的是展的是E-E-结点的邻接结点中的一个，并将其结点的邻接结点中的一个，并将其作为新的作为新的E-E-结点继续扩展，当前结点继续扩展，当前E-E-结点仍为结点仍为活结点，待搜索完其子结点后，回溯到该结活结点，待搜索完其子结点后，回溯到该结点扩展它的其它未搜索的邻接结点。而广度点扩展它的其它未搜索的邻接结点。而广度搜索，则是扩展搜索，则是扩展E-E-结点的所有邻接结点，结点的所有邻接结点，E-E-结点就成为一个死结点。结点就成为一个死结点。 5.3.1 5.3.1 算法框架算法框架 1算法的基本思路算法的基本思路 2算法框架算法框架1 1算法的基本思路算法
31、的基本思路 算法设计的基本步骤为：算法设计的基本步骤为： 1 1）确定图的存储方式；）确定图的存储方式； 2 2）遍历过程中的操作，其中包括为输出）遍历过程中的操作，其中包括为输出问题解而进行的存储操作；问题解而进行的存储操作； 3 3）输出问题的结论。）输出问题的结论。 4 4）一般在回溯前的应该将结点状态恢复）一般在回溯前的应该将结点状态恢复为原始状态，特别是在有多解需求的问题中。为原始状态，特别是在有多解需求的问题中。2算法框架算法框架 1）用邻接表存储图的搜索算法）用邻接表存储图的搜索算法 2）用邻接矩阵存储图的搜索算法）用邻接矩阵存储图的搜索算法graph head100graph
32、head100；dfs(int k) / headdfs(int k) / head图的顶点数组图的顶点数组/ / edgenode edgenode * *ptr / ptrptr / ptr图的边表指针图的边表指针/ / visitedk=1; / visitedk=1; /* * 记录已遍历过记录已遍历过 * */ / print(“ print(“访问访问 ”,k); /,k); /* * 印出遍历顶点值印出遍历顶点值 * */ / ptr=headk.firstedge; / ptr=headk.firstedge; /* * 顶点的第一个邻接点顶点的第一个邻接点 * */ / wh
33、ile ( ptr NULL ) / while ( ptr NULL ) /* * 遍历至链表尾遍历至链表尾 * */ / if ( visitedptr-vertex=0) / if ( visitedptr-vertex=0) /* * 如过没遍历过如过没遍历过 * */ / dfs(ptr-vertex); / dfs(ptr-vertex); /* * 递归遍历递归遍历 * */ / ptr = ptr-nextnode; / ptr = ptr-nextnode; /* * 下一个顶点下一个顶点 * */ / 算法分析：n n图中有图中有 n n 个顶点，个顶点，e e 条边。扫描
34、边的时间为条边。扫描边的时间为O(e)O(e)。遍历图的时间复杂性为遍历图的时间复杂性为O(n+e)O(n+e)。 返回返回 graph g100100,int ngraph g100100,int n；dfsm(int k)dfsm(int k) int j int j； print(“ print(“访问访问 ”,k);,k); visitedk=1 visitedk=1； for(j=1 for(j=1；j=nj=n；j+) /j+) /依次搜索依次搜索vkvk的邻接点的邻接点 if(gkj=1 and visitedj=0) if(gkj=1 and visitedj=0) dfsm(
35、g,j) dfsm(g,j) /(vk /(vk，vj)Evj)E，且，且vjvj未访问过，故未访问过，故vjvj为新出发点为新出发点 算法分析：查找每一个顶点的所有的边，所需时间为查找每一个顶点的所有的边，所需时间为O(n)O(n)，遍，遍历图中所有的顶点所需的时间为历图中所有的顶点所需的时间为O(n2)O(n2)。 返回返回5.3.2 5.3.2 深度优先搜索的应用深度优先搜索的应用【例【例1】走迷宫问题：问题同】走迷宫问题：问题同5.2.2【例【例2】1、算法设计：深度优先搜索，就是一直向深度优先搜索，就是一直向着可通行的下一个方格行进，直到搜索到出着可通行的下一个方格行进，直到搜索到出
36、口就找到一个解。若行不通时，则返回上一口就找到一个解。若行不通时，则返回上一个方格，继续搜索其它方向。个方格，继续搜索其它方向。2、数据结构设计：我们还是用迷宫本身的存储我们还是用迷宫本身的存储空间除了记录走过的信息，还要标识是否可行：空间除了记录走过的信息，还要标识是否可行： mazeij=3 mazeij=3 标识走过的方格标识走过的方格 ； mazeij=2 mazeij=2 标识走入死胡同的方格，标识走入死胡同的方格，这样，最后存储为这样，最后存储为“3”3”的方格为可行的方格。的方格为可行的方格。而当一个方格四个方向都搜索完还没有走到出口，而当一个方格四个方向都搜索完还没有走到出口，
37、说明该方格或无路可走或只能走入了说明该方格或无路可走或只能走入了“死胡同死胡同”。3、算法int maze88=0,0,0,0,0,0,0,0,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,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,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,0,0,0,0,1,1,0,1,0,0,1,0,0,0, 0,1,
38、1,1,1,1,1,0;fx4=1,-1,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; fy4=0,0,-1,1; int i,j,k,total;main( )main( ) int total=0; int total=0; maze11=3; / maze11=3; /入口坐标设置已走标志入口坐标设置已走标志/ / search(1,1);search(1,1); print(“Total is”,total); / print(“Total is”,total); /统计总步数统计总步数/ / sea
39、rch(int i, int j)search(int i, int j)int k,newi,newj;int k,newi,newj; for(k=1;k=4;k+) / for(k=1;k=4;k+) /搜索可达的方格搜索可达的方格/ / if( if(check(i,j,k)check(i,j,k)=1)=1) newi=i+fxk; newj=j+fyk; newi=i+fxk; newj=j+fyk; mazenewinewj=3; / mazenewinewj=3; /来到新位置后来到新位置后, ,设置已走过标志设置已走过标志/ / if (newi=8 and newj=8)
40、/ if (newi=8 and newj=8) /到出口则输出到出口则输出, ,否则下一步递归否则下一步递归/ / Out( );Out( ); else search(newi,newj); else search(newi,newj); mazeij=2; / mazeij=2; /某一方格只能走入死胡同某一方格只能走入死胡同/ / Out( )Out( ) int i,j; int i,j; for( i=1;i=8;i+) for( i=1;i=8;i+) print(“ print(“换行符换行符”);); for(j=1;j=8;j+) for(j=1;j=8;j+) if if
41、（mazeij=3mazeij=3） print(“V”);print(“V”); total+; / total+; /统计总步数统计总步数/ / else else print(“ print(“* *”);”); check(int i,int j,int k)check(int i,int j,int k)int flag=1;int flag=1; i= i+fxk; j= j +fyk; i= i+fxk; j= j +fyk; if(i8 or j8) / if(i8 or j8) /是否在迷宫内是否在迷宫内/ / flag=0; flag=0; else else if(maz
42、eij0) / if(mazeij0) /是否可行是否可行/ / flag=0; flag=0; return(flag); return(flag); 4、算法说明： 1）和广度优先算法一样每个方格有四个方）和广度优先算法一样每个方格有四个方向可以进行搜索，这样一点结点（方格）向可以进行搜索，这样一点结点（方格）就可多次成为就可多次成为“活结点活结点”，而在广度优先，而在广度优先算法一点结点（方格）就可一次成为算法一点结点（方格）就可一次成为“活活结点结点”，一出队就成了死结点。，一出队就成了死结点。 2）用广度优先算法，搜索出的是一条最短）用广度优先算法，搜索出的是一条最短的路径，而用深度
43、优先搜索则只能找出一的路径，而用深度优先搜索则只能找出一条可行的路径，而不能保证是最短的路径。条可行的路径，而不能保证是最短的路径。 3）在空间效率上二者相近。都需要辅助空）在空间效率上二者相近。都需要辅助空间。间。 【例【例2】有如图有如图1所示的七巧板，试编写一所示的七巧板，试编写一源程序如下，使用至多四种不同颜色对七巧源程序如下，使用至多四种不同颜色对七巧板进行涂色板进行涂色(每块涂一种颜色每块涂一种颜色)，要求相邻区域，要求相邻区域的颜色互不相同，打印输出所有可能的涂色的颜色互不相同，打印输出所有可能的涂色方案。方案。 1、问题分析:为了让算法为了让算法能识别不同区域间的相邻关能识别不
44、同区域间的相邻关 系，我们把七巧板上每一个系，我们把七巧板上每一个区域看成一个顶点若两个区区域看成一个顶点若两个区域相邻，则相应的顶点间用域相邻，则相应的顶点间用一条边相连，这样该问题就一条边相连，这样该问题就转化为图一个图的搜索问题转化为图一个图的搜索问题了。了。2、算法设计: 按顺序分别对号、号、按顺序分别对号、号、.、号区、号区域进行试探性涂色，用、号代表种域进行试探性涂色，用、号代表种颜色。颜色。 则涂色过程如下：则涂色过程如下： 1 1）对某一区域涂上与其相邻区域不同的颜色。）对某一区域涂上与其相邻区域不同的颜色。 2 2）若使用种颜色进行涂色均不能满足要求，）若使用种颜色进行涂色均
45、不能满足要求，则回溯一步，更改前一区域的颜色。则回溯一步，更改前一区域的颜色。 3 3）转步骤继续涂色，直到全部区域全部涂）转步骤继续涂色，直到全部区域全部涂色为止，输出结果。色为止，输出结果。 已经有研究证明，对任意的平面图至少存在一已经有研究证明，对任意的平面图至少存在一种四色涂色法。种四色涂色法。3、数据采用的存储结构：邻接矩阵存储邻接矩阵存储 0 1 0 0 1 0 10 1 0 0 1 0 1 1 0 0 1 0 1 01 0 0 1 0 1 0 0 0 0 0 0 1 10 0 0 0 0 1 1 0 1 0 0 0 1 10 1 0 0 0 1 1 1 0 0 0 0 0 11
46、0 0 0 0 0 1 0 1 1 1 0 0 00 1 1 1 0 0 0 1 0 1 1 1 0 01 0 1 1 1 0 04、算法如下:int data77,n,color7,total;int data77,n,color7,total;main( )main( ) int i,j; int i,j; for(i=1;i=n;i+) for(i=1;i=n;i+) for(j=1;j=n;j+) for(j=1;j=n;j+) input(dataij); input(dataij); for(j=1;j=n;j+) for(j=1;j7) if (s7) output( );out
47、put( ); else else for(i=1;i=4;i+) for(i=1;i=4;i+) colors=i; colors=i; if if （colorsame(s)colorsame(s)=0=0） try(s+1);try(s+1); output( )output( ) int i,; int i,; print( print(换行符，换行符，serial numberserial number：,total);,total); for i:=1 to n do for i:=1 to n do print(colori); print(colori); total=tota
48、l+1; total=total+1; colorsame(int s)colorsame(int s) / /判断相邻点是否同色判断相邻点是否同色/ / int i,flag; int i,flag; flag=0; flag=0; for(i=1;i=s-1;i+) for(i=1;iDFN(3)=3L(10)=4DFN(3)=3。同理，结点。同理，结点2 2、5 5也是关结点。也是关结点。 按后根次序访问深度优先生成树的结点，按后根次序访问深度优先生成树的结点，可以很容易地算出可以很容易地算出L L（U U）。于是，为了确定）。于是，为了确定图图G G的关结点的关结点, ,必须既完成对必
49、须既完成对G G的深度优先检索，的深度优先检索，产生产生G G的深度优先生成树的深度优先生成树T T，又要按后根次序，又要按后根次序访问树访问树T T的结点。的结点。算法ART计算DFN和L的算法如下： int DFNnint DFNn，LnLn，numnum，n n ART ART（u u，v v） /u/u是深度优先检索的开是深度优先检索的开始结点。在深度优先生成树中，始结点。在深度优先生成树中， u u若有父亲，那末若有父亲，那末v v就是它的父亲。假设就是它的父亲。假设数组数组DFNDFN是全程量，并将其初始化为是全程量，并将其初始化为0 0。numnum是是全程变量，被初始化为全程变
50、量，被初始化为 1 1。n n是是 G G的结点数的结点数算法如下：算法如下： int DFNn，Ln，num=1，n；TRY（u，v）DFNu=num；Lu=num；num=num1；while （每个邻接于（每个邻接于u的结点的结点 w ） if （DFN（w）=0） TRY（w，u）；）； if(L（u）L（w）L（u）=L（w）；）； else if （wv） if (L（u）DFN（w）) L（u）= DFN（w）；）； 算法说明： 算法算法ARTART实现了对图实现了对图G G的深度优先检索；的深度优先检索；在检索期间，对每个新访问的结点赋予深度在检索期间，对每个新访问的结点赋予深