图搜索基础课件.pptx

1树型结构树型结构(非线性结构非线性结构)结点之间有分支结点之间有分支 具有层次关系具有层次关系 例 自然界：树 人类社会 家谱 行政组织机构 计算机领域 编译：用树表示源程序的语法结构 数据库系统：用树组织信息 算法分析：用树描述执行过程 国务院 山东省 北京市 西藏自治区 济南市 青岛市 威海市 历下区 市中区 历城区 树的意义？1 树与图的回顾第1页/共84页2树的定义和基本术语 定义：定义：树(Tree)是n(n0)个结点的有限集。若n=0，称为空树；若n0，则它满足如下两个条件：(1)有且仅有一个特定的称为根根(Root)的结点；(2)其余结点可分为m(m0)个互不相交的有限集T1,T2,T3,Tm，其中每一个集合本身又是一棵树，并称为根的子树(SubTree)。树的定义是一个递归的定义。树的定义是一个递归的定义。第2页/共84页3树的逻辑结构：树的逻辑结构：树的逻辑结构：树的逻辑结构：树中任一结点都可以有零个或多个直接后继结点树中任一结点都可以有零个或多个直接后继结点但至多只能有一个直接前趋结点。但至多只能有一个直接前趋结点。T3T2T1基本术语：基本术语：结点的结点的度：度：度：度：结点拥有的子树数。结点拥有的子树数。度度=0叶子叶子叶子叶子终端结点终端结点终端结点终端结点 度度0分支结点分支结点分支结点分支结点 非终端非终端非终端非终端 结点结点结点结点 根结点以根结点以 外的分支外的分支 结点称为结点称为 内部结点内部结点内部结点内部结点 树的树的度：度：度：度：树内各结点的度的最大值。树内各结点的度的最大值。双亲双亲孩子孩子兄弟兄弟结点的结点的祖先：祖先：祖先：祖先：从根到该结点所经分支上的所有结点。从根到该结点所经分支上的所有结点。结点的结点的子孙：子孙：子孙：子孙：以某结点为根的子树中的任一结点。以某结点为根的子树中的任一结点。第第1层层第第2层层第第3层层第第4层层堂兄弟堂兄弟双亲在同一层的结点双亲在同一层的结点树的树的深度：深度：深度：深度：树中结点的最大层次。树中结点的最大层次。有序树：有序树：有序树：有序树：树中结点的各子树从左至右有次序树中结点的各子树从左至右有次序(最左边的为第一个孩子最左边的为第一个孩子)。无序树：无序树：无序树：无序树：树中结点的各子树无次序。树中结点的各子树无次序。结点：结点：数据元素数据元素+指向子树的分支指向子树的分支根结点：根结点：非空树中无前驱结点的结点非空树中无前驱结点的结点森林：森林：森林：森林：是是m(m0)棵互不相交的树的集合。棵互不相交的树的集合。一棵树可以看成是一个特殊的森林。一棵树可以看成是一个特殊的森林。把根结点删除树就变成了森林。把根结点删除树就变成了森林。给森林中的各子树加上一个双亲结点，森林就变成了树。给森林中的各子树加上一个双亲结点，森林就变成了树。树树森林森林一定是一定是 不一定是不一定是 E F G H I A B C D J K L M 第3页/共84页4定义：定义：图(Graph)是一种复杂的非线性数据结构，由顶点集合及顶点间的关系(也称弧或边)集合组成。可以表示为：G(V,VR)其中V是顶点的有穷非空集合；VR是顶点之间关系的有穷集合，也叫做弧或边集合。弧是顶点的有序对，边是顶点的无序对。图的定义和基本术语 第4页/共84页5图的意义图是一种限制最少的数据结构。更接近现实；实际问题中很多数据关系都可以抽象成图，相关问题则可利用图的基本算法进行求解，很早就有专门研究图的是一门数学学科“图论”。图论中著名算法：求最小生成树的Kruskal算法、求最短路径的Dijkstra算法和Floyd算法、求二分图最大匹配(指派问题)的匈牙利算法、求一般图最大匹配的Edmonds“花”算法、求网络最大流量和最小割集算法等。其中一些算法在数据结构课程中已经学习过。第5页/共84页6基本术语：基本术语：有向图有向图无向图无向图顶点：顶点：图中的数据元素。v2v1v3v4G1v2v1v3v4v5G2弧：弧：若 VR，则表示从v 到w 的一条弧，且称v为弧尾弧尾，称w为弧头弧头，此时的图称为有向图有向图。G1=(V1,A1)V1=v1,v2,v3,v4A1=,边：边：若 VR 必有 VR，则以无序对(v,w)代表这两个有序对，表示v 和w 之间的一条边，此时的图称为无向图无向图。G2=(V2,E2)V2=v1,v2,v3,v4,v5E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)第6页/共84页7无向图中边的取值范围：无向图中边的取值范围：0en(n-1)/2。(n 表示图中顶点数目，e表示边的数目，且不考虑顶点到自身的边)完全图：完全图：完全图：完全图：有 n(n-1)/2条边的无向图(即：无向图中每两个顶点间都存在一条边)称为完全图完全图完全图完全图。有向完全图：有向完全图：有向完全图：有向完全图：有n(n-1)条弧的有向图(即：有向图中每两个顶点间都存在着方向相反的两条弧)称为有向完全图有向完全图有向完全图有向完全图。v2v1v3v4v5有向图中弧的取值范围：有向图中弧的取值范围：0en(n-1)。(n 表示图中顶点数目，e表示弧的数目，且不考虑顶点到自身的弧)v2v1v3v4简单图简单图简单图简单图：没有环且每两个顶点间最多只有一条边相连的图。第7页/共84页8稀疏图：稀疏图：稀疏图：稀疏图：含有很少条边或弧的图。稠密图：稠密图：稠密图：稠密图：含有很多条边或弧的接近完全图的图。权：权：权：权：与图的边边或弧弧相关的数，这些数可以表示从一个顶点到另一个顶点的距离或耗费。网：网：网：网：带权的图。V1V2 1215V1 V27第8页/共84页9v3v4v5子图：子图：如果图G=(V,E)和G=(V,E)，满足：V V且E E，则称G为G的子图。v2v1v3v4v2v1v3v4v5v1v1v3v2v1v4v2v1v5v2v1v4v5v2v1v5邻接点：邻接点：若(v,v)是一条边，则称顶点v 和v互为邻接点，或称v 和v相邻接；称边(v,v)依附依附于顶点v和v，或称(v,v)与顶点v和v相关联相关联。若是一条弧，则称顶点v邻接到到v，顶点v邻接自自顶点v。并称弧与顶点v和v相关联相关联。v2v1v4第9页/共84页10度：度：度：度：无向图中顶点v的度是和v相关联的边的数目，记为TD(v)。v2v1v3v4v5入度：入度：入度：入度：有向图中以顶点v为终点的弧数目称为v的入度，记ID(v)。出度：出度：出度：出度：有向图中以顶点v为起点的弧数目称为v的出度，记OD(v)。度：度：度：度：入度和出度之和，即：TD(v)=ID(v)+OD(v)。v2v1v3v4如果顶点vi的度为TD(vi)，则一个有n个顶点e条边(弧)的图，满足如下关系：终端顶点终端顶点终端顶点终端顶点：有向图中把出度为0的顶点称为终端顶点。第10页/共84页11路径：路径：路径：路径：从顶点v到v的路径是一个顶点序列(v=vi,0,vi,1,vi,m=v)，满足(vi,j-1,vi,j)VR或 VR(1 j m)。对于有向图，路径也是有向的。对于有向图，路径也是有向的。v2v1v3v4v5v2v1v3v4路径长度：路径长度：路径长度：路径长度：路径上边或弧的数目。回路回路回路回路(环环环环)：第一个顶点和最后一个顶点相同的路径。简单路径：简单路径：简单路径：简单路径：序列中顶点(两端点除外)不重复出现的路径。简单回路简单回路简单回路简单回路(简单环简单环简单环简单环)：前后两端点相同的简单路径。连通：连通：连通：连通：无向图中从顶点v到v有路径，则说v和v是连通的。连通图：连通图：连通图：连通图：无向图中任意两个顶点都是连通的。v2v1v3v4v5第11页/共84页12连通分量：连通分量：连通分量：连通分量：无向图的极大连通子图；任何连通图的连通分量只有一个，即其本身；非连通图有多个连通分量(非连通图的每一个连通部分)。v2v1v3v4v5v2v1v3v4v5强连通图：强连通图：强连通图：强连通图：有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。v2v1v3v4强连通分量：强连通分量：强连通分量：强连通分量：有向图的极大强连通子图；任何强连通图的强连通分量只有一个，即其本身；非强连通图有多个强连通分量。v2v1v3v4v2v1v3v4第12页/共84页13 对于一个具有n个顶点的图，可用两个数组存储。其中一个一维数组存储数据元素(顶点)的信息，另一个二维数组(图的邻接矩阵)存储数据元素之间的关系(边或弧)信息。邻接矩阵：邻接矩阵：邻接矩阵：邻接矩阵：设G=(V,VR)是具有n个顶点的图，顶点的顺序依次为v1,v2,vn，则G 的邻接矩阵是具有如下性质的n阶方阵：图的存储结构之数组表示法(邻接矩阵表示法)第13页/共84页14v2v1v3v4G1v2v1v3v4v5G2v1v2v3v4v1v2v3v4v5v1v2v3v4v1v2v3v4v5特点：特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n-1)/2。有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n，空间复杂度O(n2)，用于稀疏图时空间浪费严重。无向图中顶点vi的度TD(vi)是邻接矩阵中第i行1的个数。有向图中顶点vi的出度出度是邻接矩阵中第i行行1的个数。顶点vi的入入度度是邻接矩阵中第i列列1的个数。第14页/共84页15网的邻接矩阵可定义为：网的邻接矩阵可定义为：v2v1v3v4v5v65489755613v1v2v3v4v5v6v1v2v3v4v5v6第15页/共84页16顶点表结点顶点表结点 data firstarc 边表结点边表结点 adjvex nextarc info v2v1v3v4v5G2v1v3v4v2v501234314204312021链域链域链域链域，指示下一条边或弧。，指示下一条边或弧。特点：特点：若无向图中有若无向图中有n个顶点、个顶点、e条边，则其邻接表需条边，则其邻接表需n个顶点表结个顶点表结点和点和2e个边表结点。适宜存储稀疏图。个边表结点。适宜存储稀疏图。无向图中顶点无向图中顶点vi的度为第的度为第i个单链表中的结点数。个单链表中的结点数。邻接点域邻接点域邻接点域邻接点域，存放与，存放与vi邻接的邻接的结结点在表头数组中的位置。点在表头数组中的位置。图的存储结构之邻接表(类似于树的孩子链表表示法)第16页/共84页17v2v1v3v4G101232130v1v3v4v20123302v1v3v4v20邻接表邻接表 逆邻接表逆邻接表 顶点顶点vi的的出度出度出度出度为第为第i个单链个单链表中的结点个数。表中的结点个数。特点：特点：顶点顶点vi 的的入度入度入度入度为整个为整个单链表单链表中邻接点域值是中邻接点域值是i-1的结点的结点个数个数。找出度易，找入度难。找出度易，找入度难。找入度易，找出度难。找入度易，找出度难。顶点顶点vi的的入度入度入度入度为第为第i个单链个单链表中的结点个数。表中的结点个数。顶点顶点vi 的的出度出度出度出度为整个为整个单链表单链表中邻接点域值是中邻接点域值是i-1的结点的结点个数个数。第17页/共84页18方法：方法：根结点根结点 左子树左子树 右子树右子树 依次遍历二叉树中的三个组成 部分，从而遍历整个二叉树。假设：L：遍历左子树D：遍历根结点R：遍历右子树则遍历整个二叉树方案共有：DLR、LDR、LRD、DRL、RDL、RLD六种。目的：目的：得到树中所有结点的一个得到树中所有结点的一个线性线性排列。排列。二叉树的遍历第18页/共84页19若规定先左后右，则只有前三种情况：DLRDLR先(根)序遍历LDRLDR中(根)序遍历LRDLRD后(根)序遍历ABDELHMIJ递归的定义ABC第19页/共84页201、先根、先根(次序次序)遍历遍历:2、后根、后根(次序次序)遍历遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵子树，然后访问根结点。遍历结果：遍历结果：先根遍历：先根遍历：ABCDE后根遍历：后根遍历：BDCEA3、按层次遍历、按层次遍历:若树不空，则自上而下自左至右访问树中每个结点。按层次遍历：按层次遍历：ABCEDACBED一般树的遍历第20页/共84页21从图的任意指定顶点出发，依照某种规则去访问图中所有顶点，且每个顶点仅被访问一次，此过程叫做图的遍历图的遍历。图的遍历按照广度优先和深度优先规则去实施，通常有广度优先遍历法广度优先遍历法(Breadth_FristSearchBFS)和深度优深度优先遍历法先遍历法(Depth_FirstSearchDFS)两种。V1V2V4V5V3V7V6V8图的遍历第21页/共84页22方法：方法：从图的某一结点出发，首先依次访问该结点的所有邻接顶点Vi1,Vi2,Vin,再依次访问与Vi1,Vi2,Vin 相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。例：V1V2V4V5V3V7V6V8广度优先遍历：广度优先遍历：V1 V2V3V4V5V6V7V8V1 V3V2V7V6V5V4V8V1 V2V3V5V4V7V6V8图的遍历之广度优先遍历(BFS)第22页/共84页23 V2V4V5V1V1 V2V3V4V5V6实现：实现：V1V2V4V5V3V7V6V801234567V1V2V3V4V5V6V7V8210101223354677654 0 0 0 0 0 0 0 0 0123456711111V3V71V6V811FRRFRRFRRFV7V8FFFFFRRR第23页/共84页24方法：方法：首先访问指定的起始顶点，然后在与该顶点邻接的顶点中选择一个未被访问的顶点进行访问，接着再从现在访问的顶点的邻接顶点中任意选择一个未被访问的顶点任意选择一个未被访问的顶点进行访问，如此继续，若到达无未被访问的邻接顶点的顶点时，则退回退回到最近访问过的那个顶点，若它还有未被访问的邻接顶点，则选择一个进行访问。重复上述过程，直到全部顶点都访问完毕。例：V1V1V2V4V5V3V7V6V8深度优先遍历：深度优先遍历：V2V4V8V5V3V6V7V1 V2V5V8V4V3V6V7V1 V2V4V8V5V3V7V6V1 V2V5V8V4V3V7V6V1 V3V6V7V2V4V8V5图的遍历之深度优先遍历(DFS)第24页/共84页25 V2V4V8V5V1V1 V2V4V8V5V3实现：实现：V1V2V4V5V3V7V6V801234567V1V2V3V4V5V6V7V8210101223354677654 0 0 0 0 0 0 0 0 0123456711111V3V61V6V71V71第25页/共84页26 V2V4V8V1V1 V2V4V8V5V301234567V1V2V3V4V5V6V7V8213156776 0 0 0 0 0 0 0 0 0123456711111V3V61V6V71V71V1V2V4V5V3V7V6V8V5第26页/共84页272 显式图&隐式图在路径问题、连通性问题和网络优化等问题中，图的结构是显式给出的，包括图中的顶点、边及权重，这类图称为显式图，即一般意义上的图。n隐式图是由问题的初始结点，为了求解或求证问题，根据问题的规则(一般是由题目的意思隐含给出的)，也就是生成子结点的约束条件，逐步扩展结点，直至得到目标结点为止的一个隐式的图。q两种典型的隐式图：子集树，排列树第27页/共84页282 显式图&隐式图-子集树n当要求解的问题需要在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)。第28页/共84页292 显式图&隐式图-子集树共2n 个状态。若表示为树形结构就是一棵有2n个叶结点的二叉树，对树中所有分支进行遍历的算法都必须耗时O(2n)第29页/共84页302 显式图&隐式图-排列树当要求解的问题需要在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种选择，第二个元素有n-1种选择，第三个元素有n-2种选择，第n个元素有1种选择，共计n!个状态。若表示为树形就是一个n度树，这样的树有n!个叶结点，所以每一个遍历树中所有节点的算法都必须耗时O(n!)第30页/共84页312 显式图&隐式图-排列树第31页/共84页323 图搜索术语&方法分类穷举搜索（盲目搜索）是对图的最基本的搜索算法，是蛮力策略的一种表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规则，盲目搜索的方法。q启发式搜索是利用一些启发信息，提前判断出先搜索哪些状态可能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性质，选用合适的细则，提高搜索的效率。n搜索分为两大类：隐含地检查所有可能情况第32页/共84页333 图搜索术语&方法分类问题状态:树中的每一个结点确定所求解问题的一个问题状态。状态空间:由根结点到其它结点的所有路径（分支），就确定了这个问题的状态空间。解状态:是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了该解空间中的一个元组。答案状态:是这样一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解（即它满足隐式约束条件）。状态空间树:解空间的树结构，又称隐式图。第33页/共84页343 图搜索术语&方法分类n活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。nE-结点：当前正在生成其儿子结点的活结点叫E-结点（正在扩展的结点）。n死结点：不再进一步扩展或者其儿子结点已全部生成的结点就是死结点。第34页/共84页353 图搜索术语&方法分类nn n皇后问题q要在n*nn*n的国际象棋棋盘中放n n个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解。问题状态状态空间解状态答案状态第35页/共84页363 图搜索术语&方法分类显式图的穷举搜索：广度优先搜索深度优先搜索n隐式图的穷举搜索：q回溯算法q分支算法n在这些算法中都可以加入“启发信息”，将算法优化为对应的启发式搜索，如分支限界算法。第36页/共84页37二、广度优先搜索1 图的广度优先遍历/搜索算法2 广度优先搜索的应用例7.1 求经过城市最少的路线问题例7.2 走迷宫问题第37页/共84页381 广度优先遍历/搜索遍历/搜索二叉树：先/中/后序(根)，层次；树和森林：先根/后根，层次；图：深度/广度优先；n算法的推广/退化q二叉树是特殊的树；q树是特殊的图。V1V6V5V4V3V2n遍历所有结点的目的是对结点进行各种操作。第38页/共84页391 广度优先搜索n广度优先搜索q首先访问出发点V，接着依次访问V的所有邻接点Wi，再依次访问分别与Wi邻接的所有未曾访问过的顶点，直至与V相通的顶点都已访问，若此时还有未访问的顶点，则按相同的过程继续。q活结点的扩展是按先来先处理的原则进行。“先被访问的顶点”的邻接点先于“后被”被访问V1V2V4V5V3V7V6V8第39页/共84页401 广度优先搜索-算法要素广度优先搜索：活结点的扩展是按先来先处理的原则进行；但搜索过程中还需暂时保存部分活结点。在算法中用“队”来存储每个E-结点扩展出的活结点。实际应用中，用数组或链表实现队列。开辟数组visited 记录结点的搜索情况。第40页/共84页41 V2V4V5V1V1 V2V3V4V5V6实现：实现：V1V2V4V5V3V7V6V801234567V1V2V3V4V5V6V7V8210101223354677654 0 0 0 0 0 0 0 0 0123456711111V3V71V6V811FRRFRRFRRFV7V8FFFFFRRR第41页/共84页422 广度优先搜索-算法的基本思路n算法设计的基本步骤q1）确定图的存储方式；q2）图的遍历过程中的操作，其中包括为输出问题解而进行的存储操作；q3）输出问题的结论。第42页/共84页431 广度优先搜索-一般算法n图的搜索的不同实现q图：邻接表/邻接矩阵q队列：链表/数组q机制：递归/非递归广度优先搜索用非 递归实现方便。/从顶点v 开始的广度优先搜索把顶点v标记为已到达顶点；初始化队列Q，其中仅包含一个元素v;while(Q不空)从队列中删除顶点w;令u 为邻接于w 的顶点;while(u)if(u 尚未被标记)把u 加入队列；把u 标记为已到达顶点；u=邻接于w 的下一个顶点；第43页/共84页441 广度优先搜索-邻接表表示图的算法intvisitedn;/n为结点个数bfs(intk,graphhead)inti;queueQ;edgenode*p;/定义队列InitQueue(Q)；/队列初始化print(“visitvertex”,k);visitedk=1;/访问源点vkEnQueue(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);/访问vjvisitedp-adjvex=1;EnQueue(Q,p-adjvex);/访问过的vj入队p=p-next;/找vi的下一邻接点第44页/共84页451 广度优先搜索-邻接矩阵表示图的算法bfsm(intk,graphg100,intn)inti,j;queueQ;InitQueue(Q);print(“visitvertex”,k);/访问源点vkvisitedk=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);/访问过的vj入队第45页/共84页46例7.1 已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少。2 广度优先搜索的应用-例7.1如上图表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现要找出一条经过城市最少的一条路线并输出该路线。第46页/共84页472 广度优先搜索的应用-例7.1-分析 图的广度优先搜索类似与树的层次遍历，逐层搜索正好可以尽快找到一个结点与另一个结点相对而言最直接的路径。0000000001111010000010100100001001011010010000110100100001111110ABCDEFGHABCDEFGH城市交通图对应的邻接距阵 第47页/共84页481)将城市A（编号1）入队，队首qh置0，队尾qe置1。2)将队首所指的城市所有可直通的城市入队(如果这个城市在队中出现过就不入队),然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。3)输出最少城市线路。2 广度优先搜索的应用-例7.1-分析设计0000000001111010000010100100001001011010010000110100100001111110ABCDEFGHABCDEFGH第48页/共84页491）二维数组jz作为邻接矩阵的存储空间。2）数组sq作为活结点队的存储空间。3）队列的每个结点有两个成员：sqi.city记录入队的城市，sqi.pre记录该城市的前趋城市在队列中的下标，这样通过sqi.pre就可以倒推出最短线路。4）设置数组visited记录已搜索过的城市。2 广度优先搜索的应用-例7.1-数据结构设计第49页/共84页502 广度优先搜索的应用-例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.”);第50页/共84页51算法分析：时间复杂度是O(n)；空间复杂性为(n2)，包括图本身的存储空间和搜索时辅助空间“队”的存储空间。out()/输出路径print(sqqe.city);while(sqqe.pre0)qe=sqqe.pre;print(-,sqqe.city);2 广度优先搜索的应用-例7.1-算法设计第51页/共84页52回顾显式图&隐式图q两种典型的隐式图：子集树，排列树n图搜索分类q穷举搜索和启发式搜索第52页/共84页53回顾p活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。pE-结点：当前正在生成其儿子结点的活结点叫E-结点（正在扩展的结点）。p死结点：不再进一步扩展或者其儿子结点已全部生成的结点就是死结点。n图搜索术语第53页/共84页54例7.2 迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的“1”），有的是路（图中的“0”）。走迷宫就是从一个小方格沿上、下、左、右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)，出口是右下角(8,8)。根据给定的迷宫，找出一条从入口到出口的路径。2 广度优先搜索的应用-例7.2第54页/共84页552 广度优先搜索的应用-例7.2-分析(1,1)(3,3)确定图结构本问题的原始描述，与显式图的标准形象有差别。n从入口开始出发，广度优先搜索所有可到达的方格入队，再扩展队首的方格，直到搜索到出口时，便得到一条通路。第55页/共84页562 例7.2-分析设计n问题1：如何用所学过的知识来表示现实中的迷宫？0 0 0 00 0 0 00 1 1 11 0 1 00 0 0 01 0 1 00 1 0 00 0 1 00 1 0 11 0 1 00 1 0 00 0 1 10 1 0 01 0 0 00 1 1 11 1 1 0(1,1)(3,3)q邻接表？q邻接矩阵？q利用原有的迷宫数据，检查两点之间是否存在边相连；这样就不必查询任何其他的存储结构了。二维数组第56页/共84页572 例7.2-分析设计q对于迷宫中任意一点A(X,Y)，有四个扩展方向：n问题2：在寻找路径过程中，活结点的扩展？0 0 0 00 0 0 00 1 1 11 0 1 00 0 0 01 0 1 00 1 0 00 0 1 00 1 0 11 0 1 00 1 0 00 0 1 10 1 0 01 0 0 00 1 1 11 1 1 0向上A(X1,Y+0)向下A(X+1,Y+0)向左A(X+0,Y1)向右A(X+0,Y+1)当对应方格值为0，就扩展为活结点。规律性强，验证简单p为了构造循环体，用数组fx=-1,10,0,fy=0,0,-1,1模拟上下左右搜索时下标的变化过程。p函数check，检查当前状态是否合理。第57页/共84页582 例7.2-分析设计n问题3：在寻找路径过程中，如何实现所遇到的寻找策略和返回策略的解决？0 0 0 00 0 0 00 1 1 11 0 1 00 0 0 01 0 1 00 1 0 00 0 1 00 1 0 11 0 1 00 1 0 00 0 1 10 1 0 01 0 0 00 1 1 11 1 1 0队的实现：数组q队中结点有三个成员：行号、列号、前一个方格在队列中的下标。qstructintx,y,pre;sq100;为了能够倒推出路径第58页/共84页592 例7.2-分析设计q另开辟visited数组记录已搜索过的路径。q用迷宫原有的存储空间置元素值为“-1”时，标识已经访问过该方格。n问题4：在搜索路径过程中，对搜索过的路径如何标记？0 0 0 00 0 0 00 1 1 11 0 1 00 0 0 01 0 1 00 1 0 00 0 1 00 1 0 11 0 1 00 1 0 00 0 1 10 1 0 01 0 0 00 1 1 11 1 1 0第59页/共84页60intmaze88=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;intfx4=-1,1,0,0,fy4=0,0,-1,1,;structintx,y,pre;sq100;intqh,qe,i,j,k;main()search();2 广度优先搜索的应用-例7.2-算法设计第60页/共84页61search()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=8andsqqe.y=8)out();return;print(“Noavaliableway.”);check()intflag=1;if(i8orj8)flag=0;/是否在迷宫内if(mazeij=1ormazeij=-1)flag=0;/是否可行return(flag);第61页/共84页62out()/输出路径 print(“(”sqqe.x,“,”,sqqe.y,“)”);while(sqqe.pre0)qe=sqqe.pre;print(-,“,”,sqqe.x,“,”,sqqe.y,“)”);算法分析：时间复杂度是O(n)；空间复杂性为(n2)，包括图本身的存储空间和搜索时辅助空间“队”的存储空间。2 例7.2-算法设计及分析第62页/共84页63三、深度优先搜索n1图的深度优先遍历/搜索算法n2深度优先搜索的应用q例7.2走迷宫问题q例7.3七巧板涂色问题q例7.4割点的判断及消除第63页/共84页641 深度优先搜索n首先访问出发点V1，然后依次搜索其每个邻接点W。若W为曾访问过，则以W为新的出发点继续深度优先搜索，直至和V有路径相通的点全部访问。若此时还有未访问点，则以此作新出发点继续。V1V2V4V5V3V7V6V8第64页/共84页65 V2V4V8V5V1V1 V2V4V8V5V3实现：实现：V1V2V4V5V3V7V6V801234567V1V2V3V4V5V6V7V8210101223354677654 0 0 0 0 0 0 0 0 0123456711111V3V61V6V71V71第65页/共84页66深度优先与广度优先的策略比较：区别在于扩展结点的过程；广度优先搜索，扩展E-结点的所有邻接点，E-结点就成为一个死结点。一个结点只有一次成为“活结点”。深度优先搜索，扩展的是E-结点的邻接结点中的一个，并将其作为新的E-结点继续扩展；当前E-结点仍为活结点，待搜索完其子结点后，回溯到该结点扩展它的其它未搜索的邻接结点。一个结点可能多次成为“活结点”。1 深度优先搜索第66页/共84页672 深度优先搜索的应用-例7.2-分析2(1,1)(3,3)确定图结构本问题的原始描述，与显式图的标准形象有差别。n从始点出发，按深度优先搜索方式搜索该图，一直向着可通行的下一个方格行进，直到搜索到终点时，便得到一条通路。若行不通时，则返回上一个方格，继续搜索其他方向。n有没有其他方法？第67页/共84页682 深度优先搜索的应用-例7.2-分析2n数据结构设计：用迷宫本身的存储空间除了记录走过的信息，还要标识是否可行：qmazeij=3标识走过的方格；qmazeij=2标识走入死胡同的方格；n当一个方格四个方向都搜索完还没有走到出口(存储为2)，说明该方格或无路可走或只能走入了“死胡同”。最后存储为“3”的方格为可行的方格。n函数check，检查当前状态是否合理。约束条件第68页/共84页692 深度优先搜索的应用-例7.2-算法2int 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);/统计总步数第69页/共84页70search(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第70页/共84页71Out()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-算法2check(inti,intj,intk)intflag=1;i=i+fxk;j=j+fyk;/是否在迷宫内if(i8orj8)flag=0;elseif(mazeij0)/是否可行flag=0;return(flag);第71页/共84页722 深度优先搜索的应用-例 7.2-算法说明2注意：用广度优先策略，搜索出的是一条最短的路径，而用深度优先搜索则只能找出一条可行的路径，而不能保证是最短的路径。n在空间效率上二者相近。都需要辅助空间。n用深度优先策略如何得到最短路径？第72页/共84页732 深度优先搜索的应用-例7.3例7.3 有如下图所示的七巧板，试设计算法，使用至多4种不同颜色对七巧板进行涂色(每块涂一种颜色)，要求相邻区域的颜色互不相同，打印输出所有可能的涂色方案。第73页/共84页742 深度优先搜索的应用-例7.3-问题分析 问题分析:为了让算法能识别不同区域间的相邻关系，把七巧板上每一个区域看成一个顶点，若两个区域相邻，则相应的顶点间用一条边相连，这样该问题就转化为一个图的搜索问题。010010110010100001001011001110000010101000101110012345671234567n考虑：能否将七巧板转化为平面图？如何转