搜索
第五章图的搜索算法5．1图搜索概述5.1.1图及其术语5.1.2图搜索及其术语5．2广度优先搜索5.2.1算法框架5.2.2广度优先搜索的应用5.3深度优先搜索图是一种限止最少的数据结构，因此更接近现实，实际问题中很多数据关系都可以抽象成图，相关问题则可利用图的基本算法进行求解，很早就有专门研究图的是一门数学学科“图论”；其中的计算问题包括图的搜索、路径问题、连通性问题、可平面性检验、着色问题、网络优化等。图论中的著名算法有：求最小生成树的Kruskal算法、求最短路径的Dijkstra算法和Floyd算法、求二部图最大匹配（指派问题）的匈牙利算法、求一般图最大匹配的Edmonds“花”算法、求网络最大流和最小割的算法等。其中的一些算法在数据结构课程中已经学习过了。1．显式图与隐式图在路径问题、连通性问题、可平面性检验、着色问题和网络优化等问题中，图的结构是显式给出的，包括图中的顶点、边及权重，这类图我们称为显式图，也就是一般意义上的图。隐式图是由问题的初始结点，为了求解或求证问题，根据题目的规则（一般是由题目的意思隐含给出的），也就是生成子结点的约束条件，逐步扩展结点，直到得到目标结点为止的一个隐式的图。5．1．1图及其术语2.显式图的常用术语如图5-1所示的⑴，⑵，⑶均为显式图(Graph)。图中的这些点(v1,v2,…,vn)被称为顶点(vertex)或结点，连接顶点的曲线或直线称为边(edge)。通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为图，顶点通常被称作是图中的数据元素.v1v2v3v4v1v3v2v4⑴⑵v1v2v3v4v5⑶图5-1v1v3v2v434296图5-2带权图：j即图5-2给图5-1中各图的边上附加一个代表性数据(比如表示长度、流量或其他)，则称其为带权图。环(cycle)：图5-1中⑶图中的v1点本身也有边相连，这种边称为环。有限图：顶点与边数均为有限的图，如图5-1中的三个图均属于有限图。简单图：没有环且每两个顶点间最多只有一条边相连的图，如图5-1中的⑴图。邻接与关联：当（v1，v2）∈E，或v1，v2∈E，即v1，v2间有边相连时，则称v1和v2是相邻的，它们互为邻接点（adjacent），同时称（v1，v2）或v1，v2是与顶点v1、v2相关联的边。顶点的度数(degree)：从该顶点引出的边的条数，即与该顶点相关联的边的数目，简称度。入度（indegree）：有向图中把以顶点v为终点的边的条数称为是顶点v的入度。出度（outdegree）：有向图中把以顶点v为起点的边的条数称为是顶点v的出度。终端顶点：有向图中把出度为0的顶点称为终端顶点，如图5-1中⑵图的v3。路径与路长：在图G=(V，E)中，如果存在由不同的边(vi0，vi1)，(vi1，vi2)，…，(vin-1，vin)或是vi0，vi1，vi1，vi2，…，vin-1，vin)组成的序列，则称顶点vi0，vin是连通的，顶点序列（vi0，vi1，vi2，…，vin）是从顶点vi0到顶点vin的一条道路。路长是道路上边的数目，vi0到vin的这条道路上的路长为n。连通图：对于图中任意两个顶点vi、vj∈V，vi、vj之间有道路相连，则称该图为连通图。如5-1中的⑴图。网络：带权的连通图，如图5-2所示。3．隐式图术语1）子集树当要求解的问题需要是在n个元素的子集中进行搜索，其搜索空间树被称作子集树（subsettree）。这n个元素都有在子集中或被选取记为1，不在子集中或被舍去记为0，这样搜索空间为：（0，0，……，0，0），（0，0，……，0，1），（0，0，……，1，0），（0，0，……，1，1），……（1，1，……，1，1）。共2n个状态。若表示为树形结构就是一棵有2n个叶结点的二叉树，对树中所有分支进行遍历的算法都必须耗时O（2n）。图5-3n=3的子集树当要求解的问题需要在n元素的排列中搜索问题的解时，解空间树被称作排列树（permutationtree）。搜索空间为：（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!)2）排列树图5-3n=4的部分子集树12503418X1=115121o75173133282623211383292419454035615651141196416303227252220234X2=234134124123X3=31143423243443423243413x4=1…………4．图的存储1）邻接矩阵法邻接矩阵是表示顶点之间相邻关系的矩阵，设G=(V,E)是具有n个顶点的图，则G的邻接矩阵可定义为：A[i,j]=1,若（Vi,Vj)或Vi,Vj是E(G)中的边。A[i,j]=0,若(Vi,Vj)或Vi,Vj不是E(G)中的边。若G是网络，则邻接矩阵可定义为：A[i,j]=Wij若（Vi,Vj)或Vi,Vj属于E(G);A[i,j]=0或∞若（Vi,Vj）或Vi,Vj不属于E(G);其中，Wij表示边上的权值，∞表示一个计算机允许的，大于所有边上权值的数；2）邻接表对于图G中的每个结点Vi,把所有邻接于Vi的顶点Vj链成一个单链表，这个单链表就称为顶点Vi的邻接表。邻接表由边表和顶点两部分组成。边表为一个单链表，每个表结点均有两个域：①邻接点域adjvex，存放与vi相邻接的顶点vj的序号j。②链域next，将邻接表的所有表结点链在一起。顶点表为一数组，每个元素均有两个域：①顶点域vertex，存放顶点vi的信息②指针域firstedge，vi的边表的头指针。对于无向图来说，Vi的邻接表中每个表结点都对应于与Vi相关联的一条边，对于有向图来说，Vi的邻接表中每个表结点对应于Vi为始点射出的一条边。图7.1图5-5图5-1中（1）图的邻接表5．1．2图搜索及其术语1．穷举搜索与启发式搜索穷举搜索是对图的最基本的搜索算法，是蛮力策略的一种表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规则，盲目搜索的方法。启发式搜索是利用一些启发信息，提前判断出先搜索哪些状态可能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性质，选用合适的细则，提高搜索的效率。2．相关概念和术语问题状态:树中的每一个结点确定所求解问题的一个问题状态。状态空间:由根结点到其它结点的所有路径（分支），就确定了这个问题的状态空间。解状态:是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。答案状态:是这样的一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解状态空间树:解空间的树结构,又称隐式图。活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。E-结点：当前正在生成其儿子结点的活结点叫E-结点（正扩展的结点）。死结点：不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点。5．2．1算法框架1．算法的基本思路算法设计的基本步骤为：1）确定图的存储方式；2）图的遍历过程中的操作，其中包括为输出问题解而进行的存储操作；3）输出问题的结论。2．算法框架从广度优先搜索定义可以看出活结点的扩展是按先来先处理的原则进行的，所以在算法中要用“队”来存储每个E-结点扩展出的活结点。为了算法的简洁，抽象地定义：queue为队列类型，InitQueue()为队列初始化函数，EnQueue(Q，k)为入队函数，QueueEmpty(Q)为判断队空函数，DeQueue(Q)为出队函数。实际应用中，用数组或链表实现队列。开辟数组visited记录visited结点的搜索情况。在算法框架中以输出结点值表示“访问”。1）邻接表表示图的广度优先搜索算法intvisited[n];/n为结点个数/bfs(intk,graphhead[]){inti；queueQ；edgenode*p；/定义队列/InitQueue(Q)；/队列初始化/print(“visitvertex”，k)；/访问源点vk/visited[k]=1；EnQueue(Q，k)；/vk已访问，将其入队。/while(!QueueEmpty(Q))/队非空则执行/{i=DeQueue(Q)；/vi出队为E-结点/p=head[i].firstedge；/取vi的边表头指针/while(pnull)/扩展E-结点/{if(visited[p-adjvex]=0)/若vj未访问过/{print(“visitvertex”，p-adjvex)；/访问vj/visited[p-adjvex]=1；EnQueue(Q，p-adjvex)；}/访问过的vj人队/p=p-next；}/找vi的下一邻接点/}2）邻接矩阵表示的图的广度优先搜索算法bfsm(intk,graphg[][100]，intn){inti，j；CirQueueQ；InitQueue(Q)；print(visitvertex，k)；/访问源点vk/visited[k]=1；EnQueue(Q，k)；while(notQueueEmpty(Q)){i=DeQueue(Q)；/vi出队/for(j=0;jG-n;j++)/扩展结点/if(g[i][j]==1andvisited[j]=0){print(visitvertex，j)；visited[j]=1；EnQueue(Q，j)；}/访问过的vj人队/}}5．2．2广度优先搜索的应用【例1】已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少【例2】走迷宫问题【例1】已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少。算法设计：图的广度优先搜索类似与树的层次遍历，逐层搜索正好可以尽快找到一个结点与另一个结点相对而言最直接的路径。如图5-6表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现要找出一条经过城市最少一条路线。图5-6表5-1图5-6的邻接距阵具体过程如下：1）将城市A（编号1）入队，队首qh置为0、队尾qe置为1。2）将队首所指的城市所有可直通的城市入队(如果这个城市在队中出现过就不入队),然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。3）输出最少城市线路。数据结构设计：1）线性数组a作为活结点队的存储空间。2）队列的每个结点有两个成员：a[i].city记录入队的城市，a[i].pre记录该城市的前趋城市在队列中的下标，这样通过a[i].pre就可以倒推出最短线路。3）设置数组visited[]记录已搜索过的城市。算法如下：search(){qh=0;qe=1;sq[1].city=1;sq[1].pre=0;visited[1]=1;while(qhqe)/当队不空/{qh=qh+1;/结点出队/for(i=1;i=n,i++)/扩展结点/if（jz[sq[qh].city][i]=1andvisited[i]=0）{qe=qe+1;/结点入队/sq[qe].city=i;sq[qe].pre=qh;visited[qe]=1;if(sq[qe].city=8)out();}}print(“Noavaliableway.”);}算法分析：时间复杂度是O（n）；空间复杂性为（n2），包括图本身的存储空间和搜索时辅助空间“队”的存储空间。out();/输出路径/{print(sq[qe].city);while(sq[qe].pre0){qe=sq[qe].p