图的搜索算法1

《图的搜索算法1》由会员分享，可在线阅读，更多相关《图的搜索算法1（167页珍藏版）》请在装配图网上搜索。

1、第五章第五章 图的搜索算法图的搜索算法 5 5.1 1 图搜索概述图搜索概述 5.1.1 5.1.1 图及其术语图及其术语 5.1.2 5.1.2 图搜索及其术语图搜索及其术语5.2 5.2 广度优先搜索广度优先搜索 5 5.2.1 .2.1 算法框架算法框架 5 5.2.2.2.2 广度优先搜索的广度优先搜索的应用应用 上一页 下一页 返回首页 图图是一种限止最少的数据结构，因此更接近现实，实是一种限止最少的数据结构，因此更接近现实，实际问题中很多数据关系都可以抽象成图，相关问题则可利际问题中很多数据关系都可以抽象成图，相关问题则可利用图的基本算法进行求解，很早就有专门研究图的是一门用图的基

2、本算法进行求解，很早就有专门研究图的是一门数学学科数学学科“图论图论”；其中的计算问题包括图的搜索、路径；其中的计算问题包括图的搜索、路径问题、连通性问题、可平面性检验、着色问题、网络优化问题、连通性问题、可平面性检验、着色问题、网络优化等。图论中的著名算法有：求最小生成树的等。图论中的著名算法有：求最小生成树的Kruskal算法、算法、求最短路径的求最短路径的Dijkstra算法和算法和Floyd算法、求二部图最算法、求二部图最大匹配（指派问题）的匈牙利算法、求一般图最大匹配的大匹配（指派问题）的匈牙利算法、求一般图最大匹配的Edmonds“花花”算法、求网络最大流和最小割的算法等。算法、求

3、网络最大流和最小割的算法等。其中的一些算法在数据结构课程中已经学习过了。其中的一些算法在数据结构课程中已经学习过了。1显式图与显式图与隐式图隐式图 在在路径问题、连通性问题、可平面性检验、着色路径问题、连通性问题、可平面性检验、着色问题和网络优化等问题中，图的结构是显式给出的，问题和网络优化等问题中，图的结构是显式给出的，包括图中的顶点、边及权重，这类图我们称为包括图中的顶点、边及权重，这类图我们称为显式图显式图，也就是一般意义上的也就是一般意义上的图图。隐式图隐式图是由问题的初始结点，为了求解或求证是由问题的初始结点，为了求解或求证问题，根据题目的规则（一般是由题目的意思隐含问题，根据题目的

4、规则（一般是由题目的意思隐含给出的），也就是生成子结点的约束条件，逐步扩给出的），也就是生成子结点的约束条件，逐步扩展结点，直到得到目标结点为止的一个展结点，直到得到目标结点为止的一个隐式的图隐式的图。5.1.1 5.1.1 图及其术语图及其术语2.显式图的常用术语 如图如图5-1所示的所示的，均为显式图均为显式图(Graph)。图。图中的这些点中的这些点(v1,v2,(v1,v2,vn,vn)被称为被称为顶点顶点(vertex)或或结点结点，连，连接顶点的曲线或直线称为接顶点的曲线或直线称为边边(edge)。通常将这种由若干个顶点以及连接某些顶点的边所组通常将这种由若干个顶点以及连接某些顶点

5、的边所组成的图形称为成的图形称为图图，顶点通常被称作是图中的，顶点通常被称作是图中的数据元素数据元素.上一页 下一页 返回首页v1v2v3v4v1v3v2v4v1v2v3v4v5图图 5-1 v1v3v2v434296图图 5-2 图 带权图带权图：j即图即图5-2给图给图 5-1中各图的边上附加一个代表性数中各图的边上附加一个代表性数据据(比如表示长度、流量或其他比如表示长度、流量或其他)，则称其为带权图，则称其为带权图。环环(cycle)：图：图5-1中中 图中的图中的 v 1点本身也有边相连，这种点本身也有边相连，这种边称为环。边称为环。有限图有限图：顶点与边数均为有限的图，如图：顶点与

6、边数均为有限的图，如图 5-1中的三个图均中的三个图均属于有限图。属于有限图。简单图简单图：没有环且每两个顶点间最多只有一条边相连的图，：没有环且每两个顶点间最多只有一条边相连的图，如图如图 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)：从该顶点引

7、出的边的条数，即与该顶点相：从该顶点引出的边的条数，即与该顶点相关联的边的数目，简称度。关联的边的数目，简称度。入度（入度（indegree）：有向图中把以顶点：有向图中把以顶点 v为终点的边的条数称为为终点的边的条数称为是顶点是顶点 v的入度。的入度。出度（出度（outdegree）：有向图中把以顶点：有向图中把以顶点 v为起点的边的条数称为起点的边的条数称为是顶点为是顶点 v的出度。的出度。终端顶点终端顶点：有向图中把出度为：有向图中把出度为 0的顶点称为终端顶点，如图的顶点称为终端顶点，如图 5-1中中 图的图的 v 3。路径与路长：路径与路长：在图在图 G=(V，E)中，如果存在由不同

8、的边中，如果存在由不同的边(v i0，v i1)，(v i1，v i2)，(v in-1，v in)或是或是，)组成的序列，则称顶点组成的序列，则称顶点 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之间有之间有道路相连，则称该图为连通图。如道路相连，则称该图为连通图。如

9、 5-1中的中的 图。图。网络：网络：带权的连通图，如图带权的连通图，如图 5-2所示。所示。3 3隐式图术语隐式图术语 1 1）子集树子集树 当要求解的问题需要是在当要求解的问题需要是在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

10、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 个状态。若表示为个状态。若表示为树形结构树形结构就是一棵有就是一棵有2 2n n个叶结点的二个叶结点的二叉树，叉树，对树中所有分支进行遍历的算法都必须耗时对树中所有分支进行遍历的算法都必须耗时O（2n）。上一页上一页 下一页下一页 返回首返回首页页图图5-3 n=3的子集树的子集树 上一页 下一页 返回首页2）排列树）排列树 上一上一页页 下一页下一页 返回首返回首页页 当要求解的问题需要在当要求解的问题需要在n n 元素的排列中搜索问题的解元素的排列中搜索问题

11、的解时，解空间树被称作时，解空间树被称作排列树（排列树（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!个状态

12、。若表示为树形就是一个个状态。若表示为树形就是一个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）邻

13、接矩阵法邻接矩阵法 上一上一页页 下一下一页页 返回首返回首页页 邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵，是表示顶点之间相邻关系的矩阵，设设G=(V,E)G=(V,E)是具有是具有n n个顶点的个顶点的图图，则，则G G的邻接矩阵可定义为：的邻接矩阵可定义为：Ai,j=1,Ai,j=1,若（若（Vi,Vj)Vi,Vj)或或Vi,Vj 是是E(G)E(G)中的边。中的边。Ai,j=0,Ai,j=0,若若 (Vi,Vj)(Vi,Vj)或或Vi,Vj 不是不是E(G)E(G)中的边。中的边。若若G G是是网络网络，则邻接矩阵可定义为：，则邻接矩阵可定义为：Ai,j=WAi,j=Wijij 若（

14、若（Vi,Vj)Vi,Vj)或或Vi,Vj 属于属于E(G);E(G);Ai,j=0或或 若（若（Vi,Vj）或）或 不属于不属于E(G);其中，其中，Wij表示边上的权值，表示边上的权值，表示一个计算机允许的，大于表示一个计算机允许的，大于所有边上权值的数；所有边上权值的数；上一页上一页 下一下一页页 返回首返回首页页2 2）邻接表）邻接表 上一页上一页 下一页下一页 返回首页返回首页 例例1 1 对于图对于图G G中的每个结点中的每个结点Vi,Vi,把所有邻接于把所有邻接于ViVi的顶点的顶点VjVj链成一个链成一个单链表，这个单链表就称为顶点单链表，这个单链表就称为顶点ViVi的邻接表。

15、的邻接表。邻接表由边表和顶点两部分组成。邻接表由边表和顶点两部分组成。边表边表为一个为一个单链表单链表，每个表结点均有两个域：每个表结点均有两个域：邻接点域邻接点域adjvexadjvex，存放与，存放与vivi相邻接的顶点相邻接的顶点v vj j的序号的序号j j。链 域链 域 n e x tn e x t，将 邻 接 表 的 所 有 表 结 点 链 在 一 起。，将 邻 接 表 的 所 有 表 结 点 链 在 一 起。顶 点 表顶 点 表 为 一 数 组，为 一 数 组，每 个 元 素 均 有 两 个 域：每 个 元 素 均 有 两 个 域：顶 点 域顶 点 域 v e r t e xv

16、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 图搜索及其术语1

17、 1穷举搜索与穷举搜索与启发式搜索启发式搜索 穷举搜索穷举搜索是对图的最基本的搜索算法，是蛮力策略的一种是对图的最基本的搜索算法，是蛮力策略的一种表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规则，盲目搜索的方法。依次运用规则，盲目搜索的方法。启发式搜索启发式搜索是利用一些是利用一些启发信息启发信息，提前判断出先搜索哪些，提前判断出先搜索哪些状态可能尽快找到问题的解或某些情况不可能取到最优解，从状态可能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍弃对这些状态的尝试。即而可以提前舍弃对这些状态的尝试。即考虑给

18、定问题的特有性考虑给定问题的特有性质，选用合适的细则，提高搜索的效率质，选用合适的细则，提高搜索的效率。上一页 下一页 返回首页2相关概念和术语 上一页上一页 下一页下一页 返回首返回首页页 问题状态问题状态:树中的每一个结点确定所求解问题的一个问题状态树中的每一个结点确定所求解问题的一个问题状态。状态空间状态空间:由根结点到其它结点的所有路径（分支），就确定由根结点到其它结点的所有路径（分支），就确定 了这个问题的状态空间了这个问题的状态空间。解状态解状态:是这样一些问题状态是这样一些问题状态S，对于这些问题状态，由根到，对于这些问题状态，由根到S 的那条路径确定了这解空间中的一个元组。的那

19、条路径确定了这解空间中的一个元组。答案状态答案状态:是这样的一些解状态是这样的一些解状态S，对于这些解状态而言，由，对于这些解状态而言，由 根到根到S的这条路径确定了这问题的一个解的这条路径确定了这问题的一个解状态空间树状态空间树:解空间的树结构又称隐式图解空间的树结构又称隐式图。活结点活结点：如果已生成一个结点而它的所有儿子结点还没有：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。全部生成，则这个结点叫做活结点。E-结点结点：当前正在生成其儿子结点的活结点叫：当前正在生成其儿子结点的活结点叫E-结点（正结点（正 扩展的结点）。扩展的结点）。死结点死结点：不再进一步

20、扩展或者其儿子结点已全部生成的生：不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点成结点就是死结点。5.2.1 算法框架 1算法的基本思路算法的基本思路 算法设计的基本步骤为：算法设计的基本步骤为：1）确定图的存储方式；确定图的存储方式；2）图的遍历过程中的操作，其中包括为输出问题解图的遍历过程中的操作，其中包括为输出问题解而进行的存储操作；而进行的存储操作；3 3）输出问题的结论。输出问题的结论。上一页 下一页 返回首页5.2 广度优先搜索 2 2算法框架算法框架 上一页上一页 下一页下一页 返回首页返回首页 例例1 1 从从广度优先搜索定义可以看出活结点的扩展是按先来先处广度优先

21、搜索定义可以看出活结点的扩展是按先来先处理的原则进行的，所以在算法中要用理的原则进行的，所以在算法中要用“队队”来存储每个来存储每个E-E-结点结点扩展出的活结点。为了算法的简洁，抽象地定义：扩展出的活结点。为了算法的简洁，抽象地定义：queuequeue为队列类型，为队列类型，InitQueueInitQueue()()为队列初始化函数，为队列初始化函数，EnQueue(QEnQueue(Q，k)k)为入队函数，为入队函数，QueueEmpty(QQueueEmpty(Q)为判断队空函数，为判断队空函数，DeQueue(QDeQueue(Q)为出队函数。为出队函数。实际应用中，用数组或链表实

22、现队列。实际应用中，用数组或链表实现队列。开辟开辟数组数组visitedvisited记录记录visitedvisited结点的搜索情况。结点的搜索情况。在算法框架中以输出结点值表示在算法框架中以输出结点值表示“访问访问”。1 1）邻接表表示图的广度优先搜索算法）邻接表表示图的广度优先搜索算法 int visitedn;/n visitedn;/n 为结点个数为结点个数/bfs(int k,graph head)int i；queue Q；edgenode*p；/定义队列定义队列/InitQueue(Q)；/队列初始化队列初始化/print(“visit vertex”，k)；/访问源点访问源

23、点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(“visitvertex”，p-adjvex)；/访问访问vj/visitedp-adjvex=1；EnQueue(Q，p-adjvex)；/访问过的访问过的vj人队人队/

24、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)；while(not QueueEmpty(Q)i=DeQueue(Q)；/vi出队出队/for(j=0;jn;j+)/扩展结点扩展结点/if(gij=1 and visitedj=0)pri

25、nt(visit vertex，j)；visitedj=1；EnQueue(Q，j)；/访问过的访问过的vj人队人队/5.2.2 广度优先搜索的应用 【例1】已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少 【例2】走迷宫问题 上一页 下一页 返回首页【例1】已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少。算法设计：上一页 下一页 返回首页 例2 例3 图的广度优先搜索类似与树的层次遍图的广度优先搜索类似与树的层次遍历，逐层搜索正好可以尽快找到一个结点历，逐层搜索正好可以尽快找到一个结点与另一个结点相对而言最直接的路径。与另一个结点

26、相对而言最直接的路径。如图如图5-6表示的是从城市表示的是从城市A到城市到城市H的交通的交通图。从图中可以看出，从城市图。从图中可以看出，从城市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）将队首所指的城市所有可直通的城将队首所指的城市所有可直通的城市入队市入队(如果这

27、个城市在队中出现过就不如果这个城市在队中出现过就不入队入队),),然后将队首加然后将队首加1 1，得到新的队首城，得到新的队首城市。重复以上步骤，直到城市市。重复以上步骤，直到城市H H入队为止。入队为止。当搜到城市当搜到城市H H时，搜索结束。时，搜索结束。3）输出最少城市线路输出最少城市线路。上一页 下一页 返回首页 例2 例3数据结构设计：1 1）线性线性数组数组a作为活结点队的存储空间。作为活结点队的存储空间。2 2）队列的每个结点有两个成员：队列的每个结点有两个成员：ai.city记记录入队的城市，录入队的城市，ai.pre记录该城市的前趋城记录该城市的前趋城市在队列中的下标，这样通

28、过市在队列中的下标，这样通过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.pre=0;visited1=1;while(qhqe while(qhqe)/)/当队不空当队不空/qhqh=qh+1;/=qh+1;/结点出队结点出队/for(i=1;i=n,i+)/for(i=1;i=n,i+)/扩展结点扩展结点/

29、if if（jzsqqh.cityi=1 and visitedi=0jzsqqh.cityi=1 and visitedi=0）qe qe=qe+1;/=qe+1;/结点入队结点入队/sqqe.city=i;sqqe.pre=qh;visitedqe=1;sqqe.city=i;sqqe.pre=qh;visitedqe=1;if(sqqe.cityif(sqqe.city=8)out();=8)out();printprint(“No avaliable(“No avaliable way.”);way.”);上一页 下一页 返回首页 例2 例3算法分析算法分析：时间复杂度是：时间复杂度是

30、O（n）；空间复杂性为）；空间复杂性为（n2），包括图本身的存储空间和搜索时辅助空间），包括图本身的存储空间和搜索时辅助空间“队队”的存储空间。的存储空间。out();/out();/输出路径输出路径/print(sqqe.city);print(sqqe.city);while(sqqe.prewhile(sqqe.pre0)0)qe=sqqe.pre;print(-,sqqe.city);【例2】走迷宫问题 上一页 下一页 返回首页 例1 例3 迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的“1”1”）有的是路（图中的）

31、有的是路（图中的“0”0”）。走迷宫就是从一个小方格沿上、下、左、）。走迷宫就是从一个小方格沿上、下、左、右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)(1,1)，出口是右下角出口是右下角(8,8)(8,8)。根据给定的迷宫，找出一条从入口到出口的路径。根据给定的迷宫，找出一条从入口到出口的路径。算法设计：上一页 下一页 返回首页 例1 例3 从入口开始广度优先搜索可到达的方格入队，再扩展从入口开始广度优先搜索可到达的方格入队，再扩展 队首的方格，直到搜索到出口时算法结束。队首的方格，直到搜索到出口时算法结束。

32、对于迷宫中任意一点对于迷宫中任意一点A（Y，X），有四个搜索方向：），有四个搜索方向：向上向上A（Y-1，X）向下向下A（Y+1，X）向左向左A（Y，X-1）向右向右A（Y，X+1）当对应方格可行（值为当对应方格可行（值为0），就扩展为活结点。），就扩展为活结点。数据结构设计：数据结构设计：上一页 下一页 返回首页 例1 例3 用用数组数组做队的存储空间，队中结点有三个做队的存储空间，队中结点有三个成员：行号、列号、前一个方格在队列中的成员：行号、列号、前一个方格在队列中的下标。搜索过的方格不另外开辟空间记录其下标。搜索过的方格不另外开辟空间记录其访问的情况，而是用迷宫原有的存储空间置访问的情

33、况，而是用迷宫原有的存储空间置元素值为元素值为“-1”-1”时，标识已经访问过该方格。时，标识已经访问过该方格。为了构造循环体，用数组为了构造循环体，用数组fxfx=1,-1,0,0=1,-1,0,0、fyfy=0,0,-1,1=0,0,-1,1 模拟上下左右搜索时的下标模拟上下左右搜索时的下标的变化过程。的变化过程。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;str

34、uct 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;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

35、=1;if(sqqe.city=8)out();print(“No avaliable way.”);out();/输出路径输出路径/print(sqqe.city);while(sqqe.pre0)qe=sqqe.pre;print(-,sqqe.city);算法分析算法分析：算法算法的时间复杂度并不复杂是的时间复杂度并不复杂是O O（n n），算法的空间复杂性），算法的空间复杂性为为O O（n n2 2），包括图本身的存储空间和搜索时辅助空间），包括图本身的存储空间和搜索时辅助空间“队队”的的存储空间。存储空间。上一页 下一页 返回首页 例1 例3 深度优先遍历深度优先遍历首先访问出发点首

36、先访问出发点v v，并将其标记为，并将其标记为已访问过；然后依次从已访问过；然后依次从v v出发搜索出发搜索v v的每个邻接点的每个邻接点w w。若若w w未曾访问过，则以未曾访问过，则以w w为新的出发点继续进行深度为新的出发点继续进行深度优先遍历，直至图中所有和源点优先遍历，直至图中所有和源点v v有路径相通的顶点有路径相通的顶点均已被访问为止。均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。中所有顶点均已被访问为止。5.3 5.

37、3 深度优先搜索深度优先搜索 深度搜索与广度搜索的相近，最终都要深度搜索与广度搜索的相近，最终都要扩展一个结点的所有子结点扩展一个结点的所有子结点.区别在于对扩展结点过程，深度搜索扩区别在于对扩展结点过程，深度搜索扩展的是展的是E-E-结点的邻接结点中的一个，并将其结点的邻接结点中的一个，并将其作为新的作为新的E-E-结点继续扩展，当前结点继续扩展，当前E-E-结点仍为结点仍为活结点，待搜索完其子结点后，回溯到该结活结点，待搜索完其子结点后，回溯到该结点扩展它的其它未搜索的邻接结点。而广度点扩展它的其它未搜索的邻接结点。而广度搜索，则是扩展搜索，则是扩展E-E-结点的所有邻接结点，结点的所有邻

38、接结点，E-E-结点就成为一个死结点。结点就成为一个死结点。5.3.1 5.3.1 算法框架算法框架 1算法的基本思路算法的基本思路 2算法框架算法框架1 1算法的基本思路算法的基本思路 算法设计的基本步骤为：算法设计的基本步骤为：1 1）确定图的存储方式；）确定图的存储方式；2 2）遍历过程中的操作，其中包括为输出）遍历过程中的操作，其中包括为输出问题解而进行的存储操作；问题解而进行的存储操作；3 3）输出问题的结论。）输出问题的结论。4 4）一般在回溯前的应该将结点状态恢复）一般在回溯前的应该将结点状态恢复为原始状态，特别是在有多解需求的问题中。为原始状态，特别是在有多解需求的问题中。2算

39、法框架算法框架 1）用邻接表存储图的搜索算法）用邻接表存储图的搜索算法 2）用邻接矩阵存储图的搜索算法）用邻接矩阵存储图的搜索算法graph head100graph head100；dfs(intdfs(int k)/head k)/head图的顶点数组图的顶点数组/edgenode edgenode*ptr /ptrptr /ptr图的边表指针图的边表指针/visitedk=1;/visitedk=1;/*记录已遍历过记录已遍历过 */print(“print(“访问访问 ”,k);/,k);/*印出遍历顶点值印出遍历顶点值 */ptr=headk.firstedge ptr=headk.

40、firstedge;/;/*顶点的第一个邻接点顶点的第一个邻接点 */while(ptr while(ptr NULL)/NULL)/*遍历至链表尾遍历至链表尾 */if(visitedptr if(visitedptr-vertex=0)/-vertex=0)/*如过没遍历过如过没遍历过 */dfs(ptr dfs(ptr-vertex);/-vertex);/*递归遍历递归遍历 */ptr=ptr-nextnode ptr=ptr-nextnode;/;/*下一个顶点下一个顶点 */算法分析：n n图中有图中有 n n 个顶点，个顶点，e e 条边。扫描边的时间为条边。扫描边的时间为O(e

41、)O(e)。遍历图的时间复杂性为遍历图的时间复杂性为O(n+e)O(n+e)。返回返回 graph g100100,int ngraph g100100,int n；dfsm(int k)dfsm(int k)int int j 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)Ev

42、j)E，且，且vjvj未访问过，故未访问过，故vjvj为新出发点为新出发点 算法分析：查找每一个顶点的所有的边，所需时间为查找每一个顶点的所有的边，所需时间为O(n)O(n)，遍，遍历图中所有的顶点所需的时间为历图中所有的顶点所需的时间为O(n2)O(n2)。返回返回5.3.2 5.3.2 深度优先搜索的应用深度优先搜索的应用【例【例1】走迷宫问题：问题同】走迷宫问题：问题同5.2.2【例【例2】1、算法设计：深度优先搜索，就是一直向深度优先搜索，就是一直向着可通行的下一个方格行进，直到搜索到出着可通行的下一个方格行进，直到搜索到出口就找到一个解。若行不通时，则返回上一口就找到一个解。若行不通

43、时，则返回上一个方格，继续搜索其它方向。个方格，继续搜索其它方向。2、数据结构设计：我们还是用迷宫本身的存储我们还是用迷宫本身的存储空间除了记录走过的信息，还要标识是否可行：空间除了记录走过的信息，还要标识是否可行：mazeij=3 mazeij=3 标识走过的方格标识走过的方格 ；mazeij=2 mazeij=2 标识走入死胡同的方格，标识走入死胡同的方格，这样，最后存储为这样，最后存储为“3”3”的方格为可行的方格。的方格为可行的方格。而当一个方格四个方向都搜索完还没有走到出口，而当一个方格四个方向都搜索完还没有走到出口，说明该方格或无路可走或只能走入了说明该方格或无路可走或只能走入了“

44、死胡同死胡同”。3、算法intint maze88=0,0,0,0,0,0,0,0,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,1,1,1,1,1,0;fx4=1,-1,0,0,0,1,1,1,1,1,1,0;

45、fx4=1,-1,0,0,fy4=0,0,-1,1;int fy4=0,0,-1,1;int i,j,k,total;i,j,k,total;main()main()int int total=0;total=0;maze11=3;/maze11=3;/入口坐标设置已走标志入口坐标设置已走标志/search(1,1);search(1,1);print(“Total is”,total);/print(“Total is”,total);/统计总步数统计总步数/search(int i,intsearch(int i,int j)j)int k,newi,newjint k,newi,newj

46、;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 mazenewinewj=3;/=3;/来到新位置后来到新位置后,设置已走过标志设置已走过标志/if(newi=8 and newj if(newi=8 and newj=8)/=8)/到出口则输出到出口则输出,否则下一步递归否则下一步递归/Out();Out();else search(newi,newj else

47、 search(newi,newj););mazeij=2;/mazeij=2;/某一方格只能走入死胡同某一方格只能走入死胡同/Out()Out()int int i,j;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,intc

48、heck(int i,int j,int k)k)intint flag=1;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(mazeij0)/if(mazeij0)/是否可行是否可行/flag=0;flag=0;return(flag);return(flag);4、算法说明：1）和广度优先算法一样每个方格有四个方）和广度优先算法一样每个方格有四个方向可以进行搜索，这样一点结点（方格）向可以进行搜索，这样一点结点（方格）就可多次成为

49、就可多次成为“活结点活结点”，而在广度优先，而在广度优先算法一点结点（方格）就可一次成为算法一点结点（方格）就可一次成为“活活结点结点”，一出队就成了死结点。，一出队就成了死结点。2）用广度优先算法，搜索出的是一条最短）用广度优先算法，搜索出的是一条最短的路径，而用深度优先搜索则只能找出一的路径，而用深度优先搜索则只能找出一条可行的路径，而不能保证是最短的路径。条可行的路径，而不能保证是最短的路径。3）在空间效率上二者相近。都需要辅助空）在空间效率上二者相近。都需要辅助空间。间。【例【例2】有如图有如图1所示的七巧板，试编写一所示的七巧板，试编写一源程序如下，使用至多四种不同颜色对七巧源程序如

50、下，使用至多四种不同颜色对七巧板进行涂色板进行涂色(每块涂一种颜色每块涂一种颜色)，要求相邻区域，要求相邻区域的颜色互不相同，打印输出所有可能的涂色的颜色互不相同，打印输出所有可能的涂色方案。方案。1、问题分析:为了让算法为了让算法能识别不同区域间的相邻关能识别不同区域间的相邻关 系，我们把七巧板上每一个系，我们把七巧板上每一个区域看成一个顶点若两个区区域看成一个顶点若两个区域相邻，则相应的顶点间用域相邻，则相应的顶点间用一条边相连，这样该问题就一条边相连，这样该问题就转化为图一个图的搜索问题转化为图一个图的搜索问题了。了。2、算法设计:按顺序分别对号、号、按顺序分别对号、号、.、号区、号区域

51、进行试探性涂色，用、号代表种域进行试探性涂色，用、号代表种颜色。颜色。则涂色过程如下：则涂色过程如下：1 1）对某一区域涂上与其相邻区域不同的颜色。）对某一区域涂上与其相邻区域不同的颜色。2 2）若使用种颜色进行涂色均不能满足要求，）若使用种颜色进行涂色均不能满足要求，则回溯一步，更改前一区域的颜色。则回溯一步，更改前一区域的颜色。3 3）转步骤继续涂色，直到全部区域全部涂）转步骤继续涂色，直到全部区域全部涂色为止，输出结果。色为止，输出结果。已经有研究证明，对任意的平面图至少存在一已经有研究证明，对任意的平面图至少存在一种四色涂色法。种四色涂色法。3、数据采用的存储结构：邻接矩阵存储邻接矩阵

52、存储 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 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、算法如下:intint data77,n,color7,total;data77,n,color7,total;main()main()int int i,j;i,j;for(i=1;i=n;i+)for(i=1;

53、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();output();else else for(i=1;i=4;i+)for(i=1;i=4;i+)colors=i;colors=i;if if（colorsame(scolorsame(s)=0=0）try(s+1);try(s+1);output()output()int int i,;i,;print(print(换行符，换行符，serial numberserial numbe

54、r：,total);,total);for i:=1 to n do for i:=1 to n do print(colori);print(colori);total=total+1;total=total+1;colorsame(intcolorsame(int s)s)/判断相邻点是否同色判断相邻点是否同色/int int i,flag;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也是关结点。也是关结点。按后根次序访问深度优先生成树的结点，按后根次序访问

55、深度优先生成树的结点，可以很容易地算出可以很容易地算出L L（U U）。于是，为了确定）。于是，为了确定图图G G的关结点的关结点,必须既完成对必须既完成对G G的深度优先检索，的深度优先检索，产生产生G G的深度优先生成树的深度优先生成树T T，又要按后根次序，又要按后根次序访问树访问树T T的结点。的结点。算法ART计算DFN和L的算法如下：intint DFNn DFNn，LnLn，numnum，n n ART ART（u u，v v）/u/u是深度优先检索的开是深度优先检索的开始结点。在深度优先生成树中，始结点。在深度优先生成树中，u u若有父亲，那末若有父亲，那末v v就是它的父亲。

56、假设就是它的父亲。假设数组数组DFNDFN是全程量，并将其初始化为是全程量，并将其初始化为0 0。numnum是是全程变量，被初始化为全程变量，被初始化为 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

57、 G的深度优先检索；的深度优先检索；在检索期间，对每个新访问的结点赋予深度在检索期间，对每个新访问的结点赋予深度优先数；同时对这棵树中每个结点的优先数；同时对这棵树中每个结点的L L（i i）值也进行计算。值也进行计算。如果连通图如果连通图G G有有n n个结点个结点e e条边，且条边，且G G由邻由邻接表表示，那末接表表示，那末ARTART的计算时间为的计算时间为O O（n ne e）。）。识别关结点的总时间不超过识别关结点的总时间不超过O O（n ne e）。）。3 3非重连通图的加边策略非重连通图的加边策略 G=(V,E)G=(V,E)是是G G的最大重连通子图，的最大重连通子图，指的是

58、指的是G G中再没有这样的重连通子图中再没有这样的重连通子图G=(V,E)G=(V,E)存在，使得存在，使得VVVV且且EEEE。最大重连通子图称为重连通分图最大重连通子图称为重连通分图 图5-10 图5-6所示的重连通分图 两个重连通分图至多有一个公共结点，且这个结点就是割点。两个重连通分图至多有一个公共结点，且这个结点就是割点。因而可以推出任何一条边不可能同时出现在两个不同的重连通因而可以推出任何一条边不可能同时出现在两个不同的重连通分图中（因为这需要两个公共结点）。选取两个重连通分图中分图中（因为这需要两个公共结点）。选取两个重连通分图中不同的结点连结为边，则生成的新图为重连通的。多个重

59、连通不同的结点连结为边，则生成的新图为重连通的。多个重连通分图的情况依此类推。分图的情况依此类推。使用这个方法将图使用这个方法将图5-65-6变成重连通图，变成重连通图，需要对应于关结点需要对应于关结点3 3增加边（增加边（4 4，1010）和（）和（1010，9 9）；对应关结点）；对应关结点2 2增加边（增加边（1 1，5 5）；对应关）；对应关结点结点5 5增加（增加（6 6，7 7），结果如图），结果如图5-115-11。图5-11 (图5-6改进为重连通图）5.4 回 溯 法 回溯算法实际是一个类似枚举的搜索尝试方法，它的回溯算法实际是一个类似枚举的搜索尝试方法，它的主题思想是在搜索

60、尝试中找问题的解，当不满足求解条件主题思想是在搜索尝试中找问题的解，当不满足求解条件就就”回溯回溯”返回，尝试别的路径。回溯算法是尝试搜索算返回，尝试别的路径。回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种法中最为基本的一种算法，其采用了一种“走不通就掉头走不通就掉头”的思想，作为其控制结构。的思想，作为其控制结构。5.4.1 5.4.1 认识回溯法认识回溯法【例【例1 1】八皇后问题模型建立】八皇后问题模型建立 要在要在8 8*8 8的国际象棋棋盘中放八个皇后，的国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃掉。规则：皇使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同

61、一列、同一对角线的任后能吃掉同一行、同一列、同一对角线的任意棋子。如图意棋子。如图5-125-12为一种方案，求所有的解。为一种方案，求所有的解。模型建立 不妨设八个皇后为不妨设八个皇后为xixi，她们分别在第，她们分别在第i i行行（i=1i=1，2 2，3 3，4 4，8 8），这样问题的解空），这样问题的解空间，就是一个八个皇后所在列的序号，为间，就是一个八个皇后所在列的序号，为n n元元一维向量（一维向量（x1,x2,x3,x4,x5,x6,x7,x8x1,x2,x3,x4,x5,x6,x7,x8）,搜搜索空间是索空间是1xi81xi8（i=1i=1，2 2，3 3，4 4，8 8），

62、），共共8888个状态。约束条件是八个（个状态。约束条件是八个（1,x11,x1）,(2,x,(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)x7),(8,x8)不在同一行、同一列和同一对角不在同一行、同一列和同一对角线上。线上。虽然问题共有虽然问题共有8 88 8个状态，但算法不会真正地搜个状态，但算法不会真正地搜索这么多的状态，因为前面已经说明，回溯法采用索这么多的状态，因为前面已经说明，回溯法采用的是的是“走不通就掉头走不通就掉头”的策略，而形如的策略，而形如(1,1,x3

63、,x4,x5,x6,x7,x8(1,1,x3,x4,x5,x6,x7,x8）的状态共有）的状态共有8 86 6个，由个，由于于1 1，2 2号皇后号皇后在同一列不满足约束条件，回溯后这在同一列不满足约束条件，回溯后这8686个状个状态是不会搜索的。态是不会搜索的。算法设计1：加约束条件的枚举算法加约束条件的枚举算法 最简单的算法就是通过八重循环模拟搜索空最简单的算法就是通过八重循环模拟搜索空间中的间中的8 88 8个状态，按深度优先思想，从第一个皇后个状态，按深度优先思想，从第一个皇后从第一列开始搜索，每前进一步检查是否满足约束从第一列开始搜索，每前进一步检查是否满足约束条件条件,不满足时，用

64、不满足时，用continuecontinue语句回溯，满足满足语句回溯，满足满足约束条件，开始下一层循环，直到找出问题的解。约束条件，开始下一层循环，直到找出问题的解。约束条件不在同一列的表达式为约束条件不在同一列的表达式为xi xjxi xj；而；而在同一主对角线上时在同一主对角线上时xi-i=xj-jxi-i=xj-j,在同一负对角线在同一负对角线上时上时xi+i=xj+jxi+i=xj+j，因此，不在同一对角线上的约束，因此，不在同一对角线上的约束条件表示为条件表示为abs(xi-xjabs(xi-xj)abs(i-j)abs(i-j)（absabs（）取绝（）取绝对值）。对值）。算法1

65、：queen1queen1（）intint a9;a9;for(a1=1;a1=8;a1+)for(a1=1;a1=8;a1+)for(a2=1;a2=8;a2+)for(a2=1;a2=8;a2+)if if（check(a,2)check(a,2)=0=0）continue;continue;for(a3=1;a3=8;a3+)for(a3=1;a3=8;a3+)ifif（check(a,3)=0check(a,3)=0）continue;continue;for(a4=1;a4=8;a4+)for(a4=1;a4=8;a4+)if if （check(a,4)=0check(a,4)=0

66、）continue;continue;for(a5=1;a5=8;a5+)for(a5=1;a5=8;a5+)if if（check(a,5)=0check(a,5)=0）continue;continue;for(a6=1;a6=8;a6+)for(a6=1;a6=8;a6+)if if （check(a,6)=0check(a,6)=0）continue;continue;for(a7=1;a7=8;a7+)for(a7=1;a7=8;a7+)if if（check(a,7)=0check(a,7)=0）continue;continue;for(a8=1;a8=8;a8+)for(a8=1;a8=8;a8+)if if（check(a,8)=0check(a,8)=0）continue;continue;else else for(i=1;i=8;i+)for(i=1;i=8;i+)print(ai);print(ai);check(int a,intcheck(int a,int n)n)intint i;i;for(i=1;i=n-1;i+)for(i=1;i=n-1;i+)