《《图的搜索算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图的搜索算法》PPT课件.ppt（155页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章第五章图的搜索算法图的搜索算法5 51 1 图搜索概述图搜索概述 5 51 11 1 图及其术语图及其术语 5 51 12 2 图搜索及其术语图搜索及其术语5 52 2 广度优先搜索广度优先搜索 5 52 21 1 算法框架算法框架522广度优先搜索的广度优先搜索的应用应用上一页 下一页 返回首页 图图是一种限止最少的数据结构，因此更接近现实，实际问是一种限止最少的数据结构，因此更接近现实，实际问题中很多数据关系都可以抽象成图，相关问题则可利用图的基题中很多数据关系都可以抽象成图，相关问题则可利用图的基本算法进行求解，很早就有专门研究图的是一门数学学科本算法进行求解，很早就有专门研究图的
2、是一门数学学科“图图论论”；其中的计算问题包括图的搜索、路径问题、连通性问题、；其中的计算问题包括图的搜索、路径问题、连通性问题、可平面性检验、着色问题、网络优化等。图论中的著名算法有：可平面性检验、着色问题、网络优化等。图论中的著名算法有：求最小生成树的求最小生成树的Kruskal算法、求最短路径的算法、求最短路径的Dijkstra算法算法和和Floyd算法、求二部图最大匹配（指派问题）的匈牙利算法、算法、求二部图最大匹配（指派问题）的匈牙利算法、求一般图最大匹配的求一般图最大匹配的Edmonds“花花”算法、求网络最大流和最小算法、求网络最大流和最小割的算法等。其中的一些算法在数据结构课程
3、中已经学习过了。割的算法等。其中的一些算法在数据结构课程中已经学习过了。1显式图与隐式图显式图与隐式图 在路径问题、连通性问题、可平面性检验、着色在路径问题、连通性问题、可平面性检验、着色问题和网络优化等问题中，图的结构是显式给出的，问题和网络优化等问题中，图的结构是显式给出的，包括图中的顶点、边及权重，这类图我们称为包括图中的顶点、边及权重，这类图我们称为显式图显式图，也就是一般意义上的也就是一般意义上的图图。隐式图隐式图是由问题的初始结点，为了求解或求证是由问题的初始结点，为了求解或求证问题，根据题目的规则（一般是由题目的意思隐含问题，根据题目的规则（一般是由题目的意思隐含给出的），也就是
4、生成子结点的约束条件，逐步扩给出的），也就是生成子结点的约束条件，逐步扩展结点，直到得到目标结点为止的一个展结点，直到得到目标结点为止的一个隐式的图隐式的图。5 51 11 1 图及其术语图及其术语2.显式图的常用术语 如图如图5-1所示的所示的，均为显式图均为显式图(Graph)。图中的这些点图中的这些点(v1,v2,vn)(v1,v2,vn)被称为被称为顶点顶点(vertex)或或结点结点，连接顶点的曲线或直线称为连接顶点的曲线或直线称为边边(edge)。通常将这种由若干个顶点以及连接某些顶点的边所组通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为成的图形称为图图，顶点通常被称作
5、是图中的，顶点通常被称作是图中的数据元素数据元素.上一页 下一页 返回首页图图5-1图图5-2图带权图带权图：j即图即图5-2给图给图 5-1中各图的边上附加一个代表性数据中各图的边上附加一个代表性数据(比如表示长度、流量或其他比如表示长度、流量或其他)，则称其为带权图，则称其为带权图。环环(cycle)：图：图5-1中中 图中的图中的 v 1点本身也有边相连，这种点本身也有边相连，这种边称为环。边称为环。有限图有限图：顶点与边数均为有限的图，如图：顶点与边数均为有限的图，如图 5-1中的三个图均属中的三个图均属于有限图。于有限图。简单图简单图：没有环且每两个顶点间最多只有一条边相连的图，如：
6、没有环且每两个顶点间最多只有一条边相连的图，如图图 5-1中的中的 图。图。邻接与关联邻接与关联：当（：当（v 1，v 2）E，或，或 E，即，即 v 1，v 2间有边相连时，则称间有边相连时，则称 v 1和和 v 2是相邻的，它们互为是相邻的，它们互为邻接点（邻接点（adjacent），同时称（），同时称（v 1，v 2）或）或 是与顶点是与顶点 v 1、v 2相关联的边。相关联的边。上一页 下一页 返回首页顶点的度数顶点的度数(degree)：从该顶点引出的边的条数，即与该顶点：从该顶点引出的边的条数，即与该顶点相关联的边的数目，简称度。相关联的边的数目，简称度。入度（入度（indegre
7、e）：有向图中把以顶点：有向图中把以顶点 v为终点的边的条数称为终点的边的条数称为是顶点为是顶点 v的入度。的入度。出度（出度（outdegree）：有向图中把以顶点：有向图中把以顶点 v为起点的边的条数称为起点的边的条数称为是顶点为是顶点 v的出度。的出度。终端顶点终端顶点：有向图中把出度为：有向图中把出度为 0的顶点称为终端顶点，如图的顶点称为终端顶点，如图 5-1中中 图的图的 v 3。路径与路长：路径与路长：在图在图 G=(V，E)中，如果存在由不同的边中，如果存在由不同的边(v i0，v i1)，(v i1，v i2)，(v in-1，v in)或是或是，)组成的序列，组成的序列，则
8、称顶点则称顶点 v i0，v in是连通的，顶点序列（是连通的，顶点序列（v i0，v i1，v i2，v in）是从顶点）是从顶点 v i0到顶点到顶点 v in的一条道路。路长是道的一条道路。路长是道路上边的数目，路上边的数目，v i0到到 v in的这条道路上的路长为的这条道路上的路长为 n。连通图：连通图：对于图中任意两个顶点对于图中任意两个顶点 v i、v j V，v i、v j之间有之间有道路相连，则称该图为连通图。如道路相连，则称该图为连通图。如 5-1中的中的 图。图。网络：网络：带权的连通图，如图带权的连通图，如图 5-2所示。所示。3 3隐式图术语隐式图术语 1 1）子集树
9、子集树 当要求解的问题需要是在当要求解的问题需要是在n n 个元素的子集中进行搜索，其搜个元素的子集中进行搜索，其搜索空间树被称作索空间树被称作子集树（子集树（subset treesubset tree）。这。这n n个元素都有在子集个元素都有在子集中或被选取记为中或被选取记为1 1，不在子集中或被舍去记为，不在子集中或被舍去记为0 0，这样搜索空间，这样搜索空间为：为：（0 0，0 0，0 0，0 0），（），（0 0，0 0，0 0，1 1），），（0 0，0 0，1 1，0 0），（），（0 0，0 0，1 1，1 1），），（1 1，1 1，1 1，1 1）。）。共共2 2n n 个
10、状态。若表示为个状态。若表示为树形结构树形结构就是一棵有就是一棵有2 2n n个叶结点的二叉个叶结点的二叉树，对树中所有分支进行遍历的算法都必须耗时树，对树中所有分支进行遍历的算法都必须耗时O（2n）。上一页上一页 下一页下一页 返回返回首页首页图图5-3n=3的子集树的子集树 上一页 下一页 返回首页2）排列树）排列树 上上一一页页 下下一一页页 返返回回首页首页 当当要要求求解解的的问问题题需需要要在在n n 元元素素的的排排列列中中搜搜索索问问题题的的解解时时，解空间树被称作解空间树被称作排列树（排列树（permutation treepermutation tree）。搜索空间为：搜索
11、空间为：（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!个状态。个状态。若表示为树形就是一个若表示为树形就是一个n度树，这样的树有度树，这样的树有n!个叶结点，所以每个叶结点，所以每一个遍历树中所有节点的
12、算法都必须耗时一个遍历树中所有节点的算法都必须耗时O(n!)上一页 下一页 返回首页图图5-3n=4的部分子集树的部分子集树 4 4图的存储图的存储 1 1）邻接矩阵法邻接矩阵法 上上一一页页 下下一一页页 返返回回首页首页 邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵，是表示顶点之间相邻关系的矩阵，设设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
13、(G)E(G)中的边。中的边。若若G G是是网络网络，则邻接矩阵可定义为：，则邻接矩阵可定义为：Ai,j=WAi,j=Wij ij 若（若（Vi,Vj)Vi,Vj)或或属于属于E(G);E(G);Ai,j=0或或若（若（Vi,Vj）或）或不属于不属于E(G);其其中中，Wij表表示示边边上上的的权权值值，表表示示一一个个计计算算机机允允许许的的，大大于于所有边上权值的数；所有边上权值的数；上上一一页页 下下一一页页 返返回回首页首页2 2）邻接表）邻接表 上上一一页页 下下一一页页 返返回回首首页页 例例1 1 对于图对于图G G中的每个结点中的每个结点Vi,Vi,把所有邻接于把所有邻接于Vi
14、Vi的顶点的顶点VjVj链成一个链成一个单链表，这个单链表就称为顶点单链表，这个单链表就称为顶点ViVi的邻接表。的邻接表。邻接表由边表和顶点两部分组成。邻接表由边表和顶点两部分组成。边表边表为一个为一个单链表单链表，每个表结点均有两个域：，每个表结点均有两个域：邻邻接接点点域域adjvexadjvex，存存放放与与vivi相相邻邻接接的的顶顶点点v vj j的的序序号号j j。链链 域域 nextnext，将将 邻邻 接接 表表 的的 所所 有有 表表 结结 点点 链链 在在 一一 起起。顶顶 点点 表表 为为 一一 数数 组组，每每 个个 元元 素素 均均 有有 两两 个个 域域：顶顶点点
15、域域vertexvertex，存存放放顶顶点点v vi i的的信信息息 指针域指针域firstedgefirstedge，v vi i的边表的头指针。的边表的头指针。对于无向图来说，对于无向图来说，ViVi的邻接表中每个表结点都对应于与的邻接表中每个表结点都对应于与ViVi相关联的一条边，相关联的一条边，对于有向图来说，对于有向图来说，ViVi的邻接表中每个表结点对应于的邻接表中每个表结点对应于ViVi为始点为始点射出的一条边。射出的一条边。上上一一页页 下下一一页页 返返回回首首页页图图5-5图图5-1中（中（1）图的邻接表）图的邻接表 512 图搜索及其术语1 1穷举搜索与启发式搜索穷举搜
16、索与启发式搜索 穷举搜索穷举搜索是对图的最基本的搜索算法，是蛮力策略的一种是对图的最基本的搜索算法，是蛮力策略的一种表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规则，盲目搜索的方法。依次运用规则，盲目搜索的方法。启发式搜索启发式搜索是利用一些是利用一些启发信息启发信息，提前判断出先搜索哪些，提前判断出先搜索哪些状态可能尽快找到问题的解或某些情况不可能取到最优解，从状态可能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性而可以提前舍弃对这些状态的尝试。即考虑给定问题的特
17、有性质，选用合适的细则，提高搜索的效率。质，选用合适的细则，提高搜索的效率。上一页 下一页 返回首页2相关概念和术语 上上一一页页 下下一一页页 返返回回首页首页 问题状态问题状态:树中的每一个结点确定所求解问题的一个问题状态。树中的每一个结点确定所求解问题的一个问题状态。状态空间状态空间:由根结点到其它结点的所有路径（分支），就确定由根结点到其它结点的所有路径（分支），就确定 了这个问题的状态空间。了这个问题的状态空间。解状态解状态:是这样一些问题状态是这样一些问题状态S，对于这些问题状态，由根到，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。的那条路径确定了这解空间中的一
18、个元组。答案状态答案状态:是这样的一些解状态是这样的一些解状态S，对于这些解状态而言，由，对于这些解状态而言，由 根到根到S的这条路径确定了这问题的一个解的这条路径确定了这问题的一个解状态空间树状态空间树:解空间的树结构又称隐式图。解空间的树结构又称隐式图。活结点活结点：如果已生成一个结点而它的所有儿子结点还没有：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。全部生成，则这个结点叫做活结点。E-结点结点：当前正在生成其儿子结点的活结点叫：当前正在生成其儿子结点的活结点叫E-结点（正结点（正 扩展的结点）。扩展的结点）。死结点死结点：不再进一步扩展或者其儿子结点已全部
19、生成的生：不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点成结点就是死结点。521 算法框架 1算法的基本思路算法的基本思路算法设计的基本步骤为算法设计的基本步骤为：1）确定图的存储方式；确定图的存储方式；2）图的遍历过程中的操作，其中包括为输图的遍历过程中的操作，其中包括为输出问题解而进行的存储操作；出问题解而进行的存储操作；3 3）输出问题的结论。输出问题的结论。上一页 下一页 返回首页2 2算法框架算法框架 上上一一页页 下下一一页页 返返回回首首页页 例例1 1从从广度优先搜索定义可以看出活结点的扩展是按先来先处广度优先搜索定义可以看出活结点的扩展是按先来先处理的原则进行的，
20、所以在算法中要用理的原则进行的，所以在算法中要用“队队”来存储每个来存储每个E-E-结点结点扩展出的活结点。为了算法的简洁，抽象地定义：扩展出的活结点。为了算法的简洁，抽象地定义：queuequeue为队列类型，为队列类型，InitQueue()InitQueue()为队列初始化函数，为队列初始化函数，EnQueue(QEnQueue(Q，k)k)为入队函数，为入队函数，QueueEmpty(Q)QueueEmpty(Q)为判断队空函数，为判断队空函数，DeQueue(Q)DeQueue(Q)为出队函数。为出队函数。实际应用中，用数组或链表实现队列。实际应用中，用数组或链表实现队列。开辟开辟数
21、组数组visitedvisited记录记录visitedvisited结点的搜索情况。结点的搜索情况。在算法框架中以输出结点值表示在算法框架中以输出结点值表示“访问访问”。1 1）邻接表表示图的广度优先搜索算法）邻接表表示图的广度优先搜索算法 intvisitedn;/n visitedn;/n 为结点个数为结点个数/bfs(intk,graphhead)inti；queueQ；edgenode*p；/定义队列定义队列/InitQueue(Q)；/队列初始化队列初始化/print(“visitvertex”，k)；/访问源点访问源点vk/visitedk=1；EnQueue(Q，k)；/vk已
22、访问，将其入队。已访问，将其入队。/while(!QueueEmpty(Q)/队非空则执行队非空则执行/i=DeQueue(Q)；/vi出队为出队为E-结点结点/p=headi.firstedge；/取取vi的边表头指针的边表头指针/while(pnull)/扩展扩展E-结点结点/if(visitedp-adjvex=0)/若若vj未访问过未访问过/print(“visitvertex”，p-adjvex)；/访问访问vj/visitedp-adjvex=1；EnQueue(Q，p-adjvex)；/访问过的访问过的vj人队人队/p=p-next；/找找vi的下一邻接点的下一邻接点/2）邻接矩
23、阵表示的图的广度优先搜索算法）邻接矩阵表示的图的广度优先搜索算法上上一一页页 下下一一页页 返返回回首页首页bfsm(intk,graphg100，intn)inti，j；CirQueueQ；InitQueue(Q)；print(visitvertex，k)；/访问源点访问源点vk/visitedk=1；EnQueue(Q，k)；while(notQueueEmpty(Q)i=DeQueue(Q)；/vi出队出队/for(j=0;jn;j+)/扩展结点扩展结点/if(gij=1andvisitedj=0)print(visitvertex，j)；visitedj=1；EnQueue(Q，j)；
24、/访问过的访问过的vj人队人队/522 广度优先搜索的应用 【例1】已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少 【例2】走迷宫问题 上一页 下一页 返回首页【例1】已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少。算法设计：上一页 下一页 返回首页 例2 例3 图的广度优先搜索类似与树的层次遍图的广度优先搜索类似与树的层次遍历，逐层搜索正好可以尽快找到一个结点历，逐层搜索正好可以尽快找到一个结点与另一个结点相对而言最直接的路径。与另一个结点相对而言最直接的路径。如图如图5-6表示的是从城市表示的是从城市A到城市到城市H的交通的交
25、通图。从图中可以看出，从城市图。从图中可以看出，从城市A到城市到城市H要经要经过若干个城市。现要找出一条经过城市最少过若干个城市。现要找出一条经过城市最少一条路线。一条路线。上一页上一页 下一页下一页 返回首页返回首页 例例2 2 例例3 3图5-6 表5-1 图5-6的邻接距阵 具体过程如下：1 1）将城市将城市A A（编号（编号1 1）入队，队首）入队，队首qhqh置为置为0 0、队尾、队尾qeqe置为置为1 1。2 2）将队首所指的城市所有可直通的城将队首所指的城市所有可直通的城市入队市入队(如果这个城市在队中出现过就不如果这个城市在队中出现过就不入队入队),),然后将队首加然后将队首加
26、1 1，得到新的队首城，得到新的队首城市。重复以上步骤，直到城市市。重复以上步骤，直到城市H H入队为止。入队为止。当搜到城市当搜到城市H H时，搜索结束。时，搜索结束。3）输出最少城市线路输出最少城市线路。上一页 下一页 返回首页 例2 例3数据结构设计：1 1）线性线性数组数组a作为活结点队的存储空间。作为活结点队的存储空间。2 2）队队列列的的每每个个结结点点有有两两个个成成员员：ai.city记记录录入入队队的的城城市市，ai.pre记记录录该该城城市市的的前前趋趋城城市市在在队队列列中中的的下下标标，这这样样通通过过ai.pre就就可可以以倒推出最短线路。倒推出最短线路。3 3）设置
27、数组设置数组visited记录已搜索过的城市。记录已搜索过的城市。上一页 下一页 返回首页 例2 例3算法如下：search()()qh=0;qe=1;sq1.city=1;sq1.pre=0;visited1=1;qh=0;qe=1;sq1.city=1;sq1.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
28、 and visitedi=0）qe=qe+1;/qe=qe+1;/结点入队结点入队/sqqe.city=i;sqqe.pre=qh;visitedqe=1;sqqe.city=i;sqqe.pre=qh;visitedqe=1;if(sqqe.city=8)out();if(sqqe.city=8)out();print(“No avaliable way.”);print(“No avaliable way.”);上一页 下一页 返回首页 例2 例3算法分析算法分析：时间复杂度是：时间复杂度是O（n）；空间复杂性为（）；空间复杂性为（n2），），包括图本身的存储空间和搜索时辅助空间包括图本
29、身的存储空间和搜索时辅助空间“队队”的存储空的存储空间。间。out();/out();/输出路径输出路径/print(sqqe.city);print(sqqe.city);while(sqqe.pre0)while(sqqe.pre0)qe=sqqe.pre;print(-,sqqe.city);【例2】走迷宫问题 上一页 下一页 返回首页 例1 例3 迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的“1”“1”）有的是路（图中的）有的是路（图中的“0”“0”）。走迷宫就是从一个小方格沿上、下、左、）。走迷宫就是从一个小方格
30、沿上、下、左、右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)(1,1)，出口是右下角，出口是右下角(8,8)(8,8)。根据给定的迷宫，找出一条从入口到出口的路径。根据给定的迷宫，找出一条从入口到出口的路径。算法设计：上一页 下一页 返回首页 例1 例3 从入口开始广度优先搜索可到达的方格入队，再扩展从入口开始广度优先搜索可到达的方格入队，再扩展 队队首的方格，直到搜索到出口时算法结束。首的方格，直到搜索到出口时算法结束。对于迷宫中任意一点对于迷宫中任意一点A（Y，X），有四个搜索方向：），有四个搜索方向：向上
31、向上A（Y-1，X）向下向下A（Y+1，X）向左向左A（Y，X-1）向右向右A（Y，X+1）当对应方格可行（值为当对应方格可行（值为0），就扩展为活结点。），就扩展为活结点。数据结构设计：数据结构设计：上一页 下一页 返回首页 例1 例3 用用数数组组做做队队的的存存储储空空间间，队队中中结结点点有有三三个个成成员员：行行号号、列列号号、前前一一个个方方格格在在队队列列中中的的下下标标。搜搜索索过过的的方方格格不不另另外外开开辟辟空空间间记记录录其其访访问问的的情情况况，而而是是用用迷迷宫宫原原有有的的存存储储空空间间置置元素值为元素值为“-1”“-1”时，标识已经访问过该方格。时，标识已经访
32、问过该方格。为了构造循环体，用数组为了构造循环体，用数组fx=1,-1,0,0fx=1,-1,0,0、fy=fy=0,0,-1,1 0,0,-1,1 模拟上下左右搜索时的下标的模拟上下左右搜索时的下标的变化过程。变化过程。intjz88=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;structintcity,pre;sq100;intqh,qe,i,visited100;main()i
33、nti,n=8;for(i=1;i=n,i=i+1)visitedi=0;search();search()qh=0;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=1andvisitedi=0）qe=qe+1;/结结点入点入队队/sqqe.city=i;sqqe.pre=qh;visitedqe=1;if(sqqe.city=8)out();print(“Noavaliableway.”);out();
34、/输输出路径出路径/print(sqqe.city);while(sqqe.pre0)qe=sqqe.pre;print(-,sqqe.city);算法分析算法分析：算法算法的时间复杂度并不复杂是的时间复杂度并不复杂是O O（n n），算法的空间复杂性），算法的空间复杂性为为O O（n n2 2），包括图本身的存储空间和搜索时辅助空间），包括图本身的存储空间和搜索时辅助空间“队队”的的存储空间。存储空间。上一页 下一页 返回首页 例1 例3深度优先遍历深度优先遍历首先访问出发点首先访问出发点v v，并将其标记为，并将其标记为已访问过；然后依次从已访问过；然后依次从v v出发搜索出发搜索v v的
35、每个邻接点的每个邻接点w w。若若w w未曾访问过，则以未曾访问过，则以w w为新的出发点继续进行深度为新的出发点继续进行深度优先遍历，直至图中所有和源点优先遍历，直至图中所有和源点v v有路径相通的顶点有路径相通的顶点均已被访问为止。均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。中所有顶点均已被访问为止。5.3深度优先搜索深度优先搜索 深度搜索与广度搜索的相近，最终都要深度搜索与广度搜索的相近，最终都要扩展一个结点的所有子结点扩展
36、一个结点的所有子结点.区别在于对扩展结点过程，深度搜索扩区别在于对扩展结点过程，深度搜索扩展的是展的是E-E-结点的邻接结点中的一个，并将其结点的邻接结点中的一个，并将其作为新的作为新的E-E-结点继续扩展，当前结点继续扩展，当前E-E-结点仍为结点仍为活结点，待搜索完其子结点后，回溯到该结活结点，待搜索完其子结点后，回溯到该结点扩展它的其它未搜索的邻接结点。而广度点扩展它的其它未搜索的邻接结点。而广度搜索，则是扩展搜索，则是扩展E-E-结点的所有邻接结点，结点的所有邻接结点，E-E-结点就成为一个死结点。结点就成为一个死结点。5 53 31 1 算法框架算法框架 1算法的基本思路算法的基本思
37、路2算法框架算法框架1 1算法的基本思路算法的基本思路 算法设计的基本步骤为：算法设计的基本步骤为：1 1）确定图的存储方式；）确定图的存储方式；2 2）遍历过程中的操作，其中包括为输出）遍历过程中的操作，其中包括为输出问题解而进行的存储操作；问题解而进行的存储操作；3 3）输出问题的结论。）输出问题的结论。4 4）一般在回溯前的应该将结点状态恢复）一般在回溯前的应该将结点状态恢复为原始状态，特别是在有多解需求的问题中。为原始状态，特别是在有多解需求的问题中。2算法框架算法框架1）用邻接表存储图的搜索算法）用邻接表存储图的搜索算法2）用邻接矩阵存储图的搜索算法）用邻接矩阵存储图的搜索算法gra
38、ph head100graph head100；dfs(int k)/headdfs(int k)/head图的顶点数组图的顶点数组/edgenode*ptr /ptr edgenode*ptr /ptr图的边表指针图的边表指针/visitedk=1;/*visitedk=1;/*记录已遍历过记录已遍历过*/*/print(“print(“访问访问”,k);/*”,k);/*印出遍历顶点值印出遍历顶点值*/*/ptr=headk.firstedge;/*ptr=headk.firstedge;/*顶点的第一个邻接点顶点的第一个邻接点*/*/while(ptr NULL)/*while(ptr
39、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 条边。扫描边的时间为条边。扫描边的时间为O(e)O(e)。遍历图的时间复杂性为遍历图的时间复杂性为O(n+e)O(n+e)。返回返回 graph g100100
40、,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(g,j)dfsm(g,j)/(vk /(vk，vj)Evj)E，且，且vjvj未访问过，故未访问过，故vjvj为新出发点为新出发点 算法分析：查找每一个顶点的所有的边，所
41、需时间为查找每一个顶点的所有的边，所需时间为O(n)O(n)，遍，遍历图中所有的顶点所需的时间为历图中所有的顶点所需的时间为O(n2)O(n2)。返回返回5 53 32 2 深度优先搜索的应用深度优先搜索的应用【例【例1】走迷宫问题：问题同】走迷宫问题：问题同522【例【例2】1、算法设计：深度优先搜索，就是一直向深度优先搜索，就是一直向着可通行的下一个方格行进，直到搜索到出着可通行的下一个方格行进，直到搜索到出口就找到一个解。若行不通时，则返回上一口就找到一个解。若行不通时，则返回上一个方格，继续搜索其它方向。个方格，继续搜索其它方向。2、数据结构设计：我们还是用迷宫本身的存储我们还是用迷宫
42、本身的存储空间除了记录走过的信息，还要标识是否可行：空间除了记录走过的信息，还要标识是否可行：mazeij=3 mazeij=3 标识走过的方格标识走过的方格 ；mazeij=2 mazeij=2 标识走入死胡同的方格，标识走入死胡同的方格，这样，最后存储为这样，最后存储为“3”“3”的方格为可行的方格。的方格为可行的方格。而当一个方格四个方向都搜索完还没有走到出口，而当一个方格四个方向都搜索完还没有走到出口，说明该方格或无路可走或只能走入了说明该方格或无路可走或只能走入了“死胡同死胡同”。3、算法int maze88=0,0,0,0,0,0,0,0,int maze88=0,0,0,0,0,
43、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,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
44、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);/统计总步数统计总步数/search(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(che
45、ck(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)/if(newi=8 and newj=8)/到出口则输出到出口则输出,否则下一步递归否则下一步递归/Out();Out();else search(newi,newj);else search(newi,newj);mazeij=2;/mazeij=2;/某一方格只能走入死胡同某一方格只能走入
46、死胡同/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（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=
47、j+fyk;i=i+fxk;j=j+fyk;if(i8 or j8)/if(i8 or j8)/是否在迷宫内是否在迷宫内/flag=0;flag=0;else else if(mazeij0)/if(mazeij0)/是否可行是否可行/flag=0;flag=0;return(flag);return(flag);4、算法说明：1）和广度优先算法一样每个方格有四个方）和广度优先算法一样每个方格有四个方向可以进行搜索，这样一点结点（方格）向可以进行搜索，这样一点结点（方格）就可多次成为就可多次成为“活结点活结点”，而在广度优先，而在广度优先算法一点结点（方格）就可一次成为算法一点结点（方格）就可
48、一次成为“活活结点结点”，一出队就成了死结点。，一出队就成了死结点。2）用广度优先算法，搜索出的是一条最短）用广度优先算法，搜索出的是一条最短的路径，而用深度优先搜索则只能找出一的路径，而用深度优先搜索则只能找出一条可行的路径，而不能保证是最短的路径。条可行的路径，而不能保证是最短的路径。3）在空间效率上二者相近。都需要辅助空）在空间效率上二者相近。都需要辅助空间。间。【例【例2】有如图有如图1所示的七巧板，试编写一所示的七巧板，试编写一源程序如下，使用至多四种不同颜色对七巧源程序如下，使用至多四种不同颜色对七巧板进行涂色板进行涂色(每块涂一种颜色每块涂一种颜色)，要求相邻区，要求相邻区域的颜
49、色互不相同，打印输出所有可能的涂域的颜色互不相同，打印输出所有可能的涂色方案。色方案。1、问题分析:为了让算法为了让算法能识别不同区域间的相邻关能识别不同区域间的相邻关系，我们把七巧板上每一个系，我们把七巧板上每一个区域看成一个顶点若两个区区域看成一个顶点若两个区域相邻，则相应的顶点间用域相邻，则相应的顶点间用一条边相连，这样该问题就一条边相连，这样该问题就转化为图一个图的搜索问题转化为图一个图的搜索问题了。了。2、算法设计:按顺序分别对号、号、按顺序分别对号、号、.、号区域、号区域进行试探性涂色，用、号代表种颜进行试探性涂色，用、号代表种颜色。色。则涂色过程如下：则涂色过程如下：1 1）对某
50、一区域涂上与其相邻区域不同的颜色。）对某一区域涂上与其相邻区域不同的颜色。2 2）若使用种颜色进行涂色均不能满足要求，）若使用种颜色进行涂色均不能满足要求，则回溯一步，更改前一区域的颜色。则回溯一步，更改前一区域的颜色。3 3）转步骤继续涂色，直到全部区域全部涂）转步骤继续涂色，直到全部区域全部涂色为止，输出结果。色为止，输出结果。已经有研究证明，对任意的平面图至少存在一已经有研究证明，对任意的平面图至少存在一种四色涂色法。种四色涂色法。3、数据采用的存储结构：邻接矩阵存储邻接矩阵存储 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1