《图搜索基础》PPT课件.ppt

《《图搜索基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图搜索基础》PPT课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图搜索基础图搜索基础1树的定义和基本术语树的定义和基本术语 定义：定义：树树(Tree)是是n(n0)个结点的有限集。个结点的有限集。若若n=0，称称为空树；为空树；若若n0，则，则它满足如下两个条件：它满足如下两个条件：(1)有且仅有一个特定的称为有且仅有一个特定的称为根根根根(Root)的结点；的结点；(2)其余结点可分为其余结点可分为m(m0)个互不相交的有限集个互不相交的有限集T1,T2,T3,Tm，其中每一个集合本身又是一棵树，并称为，其中每一个集合本身又是一棵树，并称为根的根的子树子树(SubTree)。树的定义是一个递归的定义。树的定义是一个递归的定义。2树的逻辑结构：树的逻辑结

2、构：树的逻辑结构：树的逻辑结构：树中任一结点都可以有零个或多个直接后继结点树中任一结点都可以有零个或多个直接后继结点但至多只能有一个直接前趋结点。但至多只能有一个直接前趋结点。T3T2T1基本术语：基本术语：结点的结点的度：度：度：度：结点拥有的子树数。结点拥有的子树数。度度=0叶子叶子叶子叶子终端结点终端结点终端结点终端结点 度度0分支结点分支结点分支结点分支结点 非终端非终端非终端非终端 结点结点结点结点 根结点以根结点以 外的分支外的分支 结点称为结点称为 内部结点内部结点内部结点内部结点 树的树的度：度：度：度：树内各结点的度的最大值。树内各结点的度的最大值。双亲双亲孩子孩子兄弟兄弟结

3、点的结点的祖先：祖先：祖先：祖先：从根到该结点所经分支上的所有结点。从根到该结点所经分支上的所有结点。结点的结点的子孙：子孙：子孙：子孙：以某结点为根的子树中的任一结点。以某结点为根的子树中的任一结点。第第1层层第第2层层第第3层层第第4层层堂兄弟堂兄弟双亲在同一层的结点双亲在同一层的结点树的树的深度：深度：深度：深度：树中结点的最大层次。树中结点的最大层次。有序树：有序树：有序树：有序树：树中结点的各子树从左至右有次序树中结点的各子树从左至右有次序(最左边的为第一个孩子最左边的为第一个孩子)。无序树：无序树：无序树：无序树：树中结点的各子树无次序。树中结点的各子树无次序。结点：结点：数据元素

4、数据元素+指向子树的分支指向子树的分支森林：森林：森林：森林：是是m(m0)棵互不相交的树的集合。棵互不相交的树的集合。一棵树可以看成是一个特殊的森林。一棵树可以看成是一个特殊的森林。把根结点删除树就变成了森林。把根结点删除树就变成了森林。给森林中的各子树加上一个双亲结点，森林就变成了树。给森林中的各子树加上一个双亲结点，森林就变成了树。树树森林森林一定是一定是 不一定是不一定是 E F G H I A B C D J K L M 3定义：定义：图图(Graph)是是一种复杂的非线性数据结构，由顶一种复杂的非线性数据结构，由顶点集合及顶点间的关系点集合及顶点间的关系(也称弧或边也称弧或边)集合

5、组成。可集合组成。可以表示为：以表示为：G(V,VR)其中其中V是是顶点顶点的有穷非空集合；的有穷非空集合；VR是是顶点之间关系顶点之间关系的有穷集合，也叫做的有穷集合，也叫做弧弧或或边边集合。弧集合。弧是顶点的有序对，是顶点的有序对，边是顶点的无序对。边是顶点的无序对。图的定义和基本术语图的定义和基本术语 4度：度：度：度：无向图无向图中顶点中顶点v的度是和的度是和v相关联的边的数目，记为相关联的边的数目，记为TD(v)。v2v1v3v4v5入度：入度：入度：入度：有向图有向图中以顶点中以顶点v为终点的弧数目称为为终点的弧数目称为v的入度，记的入度，记ID(v)。出度：出度：出度：出度：有向

6、图有向图中以顶点中以顶点v为起点的弧数目称为为起点的弧数目称为v的出度，记的出度，记OD(v)。度：度：度：度：入度和出度之和，即：入度和出度之和，即：TD(v)=ID(v)+OD(v)。v2v1v3v4如果顶点如果顶点vi的度为的度为TD(vi)，则一个有，则一个有n个顶点个顶点e条边条边(弧弧)的图，满足如下关系：的图，满足如下关系：终端顶点终端顶点终端顶点终端顶点：有向图中把出度为：有向图中把出度为0的顶点称为终端顶点。的顶点称为终端顶点。5路径：路径：路径：路径：从顶点从顶点v到到v的路径是一个顶点序列的路径是一个顶点序列(v=vi,0,vi,1,vi,m=v)，满足满足(vi,j-1

7、,vi,j)VR或或 VR(1 j m)。对于有向图，路径也是有向的。对于有向图，路径也是有向的。v2v1v3v4v5v2v1v3v4路径长度：路径长度：路径长度：路径长度：路径上边或弧的数目。路径上边或弧的数目。回路回路回路回路(环环环环)：第一个顶点和最后一个顶点相同的路径。第一个顶点和最后一个顶点相同的路径。简单路径：简单路径：简单路径：简单路径：序列中顶点序列中顶点(两端点除外两端点除外)不重复出现的路径。不重复出现的路径。简单回路简单回路简单回路简单回路(简单环简单环简单环简单环)：前后两端点相同的简单路径。前后两端点相同的简单路径。连通：连通：连通：连通：无向图中从顶点无向图中从顶

8、点v到到v有路径，则说有路径，则说v和和v是连通的。是连通的。连通图：连通图：连通图：连通图：无向图中任意两个顶点都是连通的。无向图中任意两个顶点都是连通的。v2v1v3v4v56连通分量：连通分量：连通分量：连通分量：无向图的极大连通子图；任何连通图的连通无向图的极大连通子图；任何连通图的连通分量只有一个，即其本身；非连通图有多个连通分量分量只有一个，即其本身；非连通图有多个连通分量(非连非连通图的每一个连通部分通图的每一个连通部分)。v2v1v3v4v5v2v1v3v4v5强连通图：强连通图：强连通图：强连通图：有向图有向图G中，若对于中，若对于V(G)中任意两个不同的中任意两个不同的顶点

9、顶点vi和和vj，都存在从，都存在从vi到到vj以及从以及从vj到到vi的路径，则称的路径，则称G是是强连通图。强连通图。v2v1v3v4强连通分量：强连通分量：强连通分量：强连通分量：有向图的极大强连通子图；任何强连通图的有向图的极大强连通子图；任何强连通图的强连通分量只有一个，即其本身；非强连通图有多个强连通分强连通分量只有一个，即其本身；非强连通图有多个强连通分量。量。v2v1v3v4v2v1v3v47 对于一个具有对于一个具有n个顶点的图，可用两个数组存储。其中一个顶点的图，可用两个数组存储。其中一个一维数组存储数据元素个一维数组存储数据元素(顶点顶点)的信息，另一个二维数组的信息，另

10、一个二维数组(图图的邻接矩阵的邻接矩阵)存储数据元素之间的关系存储数据元素之间的关系(边或弧边或弧)信息。信息。邻接矩阵：邻接矩阵：邻接矩阵：邻接矩阵：设设G=(V,VR)是具有是具有n个顶点的图，顶点个顶点的图，顶点的顺序依次为的顺序依次为v1,v2,vn，则，则G 的邻接矩阵是具有如下的邻接矩阵是具有如下性质的性质的n阶方阵：阶方阵：图的存储结构之数组表示法图的存储结构之数组表示法(邻接矩阵表示法邻接矩阵表示法)8v2v1v3v4G1v2v1v3v4v5G2v1v2v3v4v1v2v3v4v5v1v2v3v4v1v2v3v4v5特点：特点：无向图的邻接矩阵对称，可压缩存储；有无向图的邻接矩

11、阵对称，可压缩存储；有n个顶点的无向图个顶点的无向图需存储空间为需存储空间为n(n-1)/2。有向图邻接矩阵不一定对称；有有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空个顶点的有向图需存储空间为间为n，空间复杂度空间复杂度O(n2)，用于稀疏图时空间浪费严重。，用于稀疏图时空间浪费严重。无向图中顶点无向图中顶点vi的度的度TD(vi)是邻接矩阵中第是邻接矩阵中第i行行1的个数。的个数。有向图中有向图中顶点顶点vi的的出度出度出度出度是邻接矩阵中第是邻接矩阵中第i行行行行1的个数。的个数。顶点顶点vi的的入入入入度度度度是邻接矩阵中第是邻接矩阵中第i列列列列1的个数。的个数。9网的邻接矩阵

12、可定义为：网的邻接矩阵可定义为：v2v1v3v4v5v65489755613v1v2v3v4v5v6v1v2v3v4v5v610顶点表结点顶点表结点 data firstarc 边表结点边表结点 adjvex nextarc info v2v1v3v4v5G2v1v3v4v2v501234314204312021链域链域链域链域，指示下一条边或弧。，指示下一条边或弧。特点：特点：若无向图中有若无向图中有n个顶点、个顶点、e条边，则其邻接表需条边，则其邻接表需n个顶点表结个顶点表结点和点和2e个边表结点。适宜存储稀疏图个边表结点。适宜存储稀疏图。无向图中顶点无向图中顶点vi的度为第的度为第i个单

13、链表中的结点数。个单链表中的结点数。邻接点域邻接点域邻接点域邻接点域，存放与，存放与vi邻接的邻接的结点在表头数组中的位置。结点在表头数组中的位置。图的存储结构之邻接表图的存储结构之邻接表(类似于树的孩子链表表示法类似于树的孩子链表表示法)11v2v1v3v4G101232130v1v3v4v20123302v1v3v4v20邻接表邻接表 逆邻接表逆邻接表 顶点顶点vi的的出度出度出度出度为第为第i个单链个单链表中的结点个数。表中的结点个数。特点：特点：顶点顶点vi 的的入度入度入度入度为整个为整个单链表单链表中邻接点域值是中邻接点域值是i-1的结点的结点个数个数。找出度易，找入度难。找出度易

14、，找入度难。找入度易，找出度难。找入度易，找出度难。顶点顶点vi的的入度入度入度入度为第为第i个单链个单链表中的结点个数。表中的结点个数。顶点顶点vi 的的出度出度出度出度为整个为整个单链表单链表中邻接点域值是中邻接点域值是i-1的结点的结点个数个数。12从图的任意指定顶点出发，依照某种规则去访问图中所从图的任意指定顶点出发，依照某种规则去访问图中所有顶点，且每个顶点仅被访问一次，此过程叫做有顶点，且每个顶点仅被访问一次，此过程叫做图的遍历图的遍历图的遍历图的遍历。图的遍历按照广度优先和深度优先规则去实施，通常有图的遍历按照广度优先和深度优先规则去实施，通常有广度优先遍历法广度优先遍历法广度优

15、先遍历法广度优先遍历法(Breadth_FristSearchBFS)和和深度优先深度优先深度优先深度优先遍历法遍历法遍历法遍历法(Depth_FirstSearchDFS)两种。两种。V1V2V4V5V3V7V6V8图的遍历图的遍历13方法：方法：方法：方法：从图的某一结点出发，首先依次访问该结点的从图的某一结点出发，首先依次访问该结点的所有邻接顶点所有邻接顶点Vi1,Vi2,Vin,再依次访问与再依次访问与Vi1,Vi2,Vin 相邻接的所有未被访问的顶点，重复此过程，直至所有相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。顶点均被访问为止。例：例：V1V2V4V5V3V

16、7V6V8广度优先遍历：广度优先遍历：V1V2V3V4V5V6V7V8V1V3V2V7V6V5V4V8V1V2V3V5V4V7V6V8图的遍历之广度优先遍历图的遍历之广度优先遍历(BFS)14方法：方法：方法：方法：首先访问指定的起始顶点，然后在与该顶点邻接的首先访问指定的起始顶点，然后在与该顶点邻接的顶点中选择一个未被访问的顶点进行访问，接着再从现在访问顶点中选择一个未被访问的顶点进行访问，接着再从现在访问的顶点的的顶点的邻接顶点中邻接顶点中任意选择一个未被访问的顶点任意选择一个未被访问的顶点任意选择一个未被访问的顶点任意选择一个未被访问的顶点进行访问，进行访问，如此继续，若如此继续，若到达

17、无未被访问的邻接顶点的顶点时，则到达无未被访问的邻接顶点的顶点时，则退回退回退回退回到到最近访问过的那最近访问过的那个顶点，若它还有未被访问的邻接顶点，则选个顶点，若它还有未被访问的邻接顶点，则选择一个进行访问。重复上述过程，直到全部顶点都访问完毕择一个进行访问。重复上述过程，直到全部顶点都访问完毕。例：例：V1V1V2V4V5V3V7V6V8深度优先遍历：深度优先遍历：V2V4V8V5V3V6V7V1V2V5V8V4V3V6V7V1V2V4V8V5V3V7V6V1V2V5V8V4V3V7V6V1V3V6V7V2V4V8V5图的遍历之深度优先遍历图的遍历之深度优先遍历(DFS)152 显式图显

18、式图&隐式图隐式图n在路径问题、连通性问题和网络优化等问题中，在路径问题、连通性问题和网络优化等问题中，图的结构图的结构是显式给出是显式给出的，包括图中的顶点、边及权重，这类图称为的，包括图中的顶点、边及权重，这类图称为显式图显式图，即一般意义上的图。，即一般意义上的图。n隐式图隐式图是由问题的初始结点，为了求解或求证问题，是由问题的初始结点，为了求解或求证问题，根据根据问题的规则问题的规则(一般是由题目的意思隐含给出的一般是由题目的意思隐含给出的)，也就是生，也就是生成子结点的约束条件，成子结点的约束条件，逐步扩展结点逐步扩展结点，直至得到目标结点，直至得到目标结点为止的一个隐式的图。为止的

19、一个隐式的图。q两种典型的隐式图：子集树，排列树两种典型的隐式图：子集树，排列树162 显式图显式图&隐式图隐式图-子集树子集树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)。172 显式图显式图&隐式图隐式图-子集树子集树n共共2

20、n个状态。若表示为树形结构就是一棵有个状态。若表示为树形结构就是一棵有2n个叶结点的个叶结点的二叉树，对树中所有分支进行遍历的算法都必须耗时二叉树，对树中所有分支进行遍历的算法都必须耗时O(2n)182 显式图显式图&隐式图隐式图-排列树排列树n当要求解的问题需要在当要求解的问题需要在n个元素的个元素的排列排列中搜索问题的解时，中搜索问题的解时，解空间树被称作解空间树被称作排列树排列树(permutationtree)。n搜索空间为：搜索空间为：(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第一

21、个元素有第一个元素有n种选择，第二个种选择，第二个元素有元素有n-1种选择，第三个元素种选择，第三个元素有有n-2种选择，种选择，第，第n个元素个元素有有1种选择，共计种选择，共计n!个状态。若个状态。若表示为树形就是一个表示为树形就是一个n度树，这度树，这样的树有样的树有n!个叶结点，所以每一个叶结点，所以每一个遍历树中所有节点的算法都必个遍历树中所有节点的算法都必须耗时须耗时O(n!)192 显式图显式图&隐式图隐式图-排列树排列树203 图搜索术语图搜索术语&方法分类方法分类q穷举搜索（盲目搜索）穷举搜索（盲目搜索）是对图的最基本的搜索算法，是对图的最基本的搜索算法，是蛮力策略的一种表现

22、形式。即不考虑给定问题的特是蛮力策略的一种表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规则，盲目搜有性质，按事先定好的顺序，依次运用规则，盲目搜索的方法。索的方法。q启发式搜索启发式搜索是利用一些启发信息，提前判断出先搜索是利用一些启发信息，提前判断出先搜索哪些状态可能尽快找到问题的解或某些情况不可能取哪些状态可能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍弃对这些状态的尝试。即到最优解，从而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性质，选用合适的细则，提高搜考虑给定问题的特有性质，选用合适的细则，提高搜索的效率。索的效率。n搜索分为两大类：搜索分为

23、两大类：隐含地检查所有可能情况隐含地检查所有可能情况213 图搜索术语图搜索术语&方法分类方法分类n问题状态问题状态:树中的每一个结点确定所求解问题的一个问题树中的每一个结点确定所求解问题的一个问题状态。状态。n状态空间状态空间:由根结点到其它结点的所有路径（分支），就由根结点到其它结点的所有路径（分支），就确定了这个问题的状态空间。确定了这个问题的状态空间。n解状态解状态:是这样一些问题状态是这样一些问题状态S，对于这些问题状态，由，对于这些问题状态，由根到根到S的那条路径确定了该解空间中的一个元组。的那条路径确定了该解空间中的一个元组。n答案状态答案状态:是这样一些解状态是这样一些解状态S

24、，对于这些解状态而言，对于这些解状态而言，由根到由根到S的这条路径确定了这问题的一个解（即它满足隐的这条路径确定了这问题的一个解（即它满足隐式约束条件）。式约束条件）。n状态空间树状态空间树:解空间的树结构，又称隐式图。解空间的树结构，又称隐式图。223 图搜索术语图搜索术语&方法分类方法分类n活结点：活结点：如果已生成一个结点而它的所有儿子结点还没如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。有全部生成，则这个结点叫做活结点。nE-结点：结点：当前正在生成其儿子结点的活结点叫当前正在生成其儿子结点的活结点叫E-结点结点（正在扩展的结点）。（正在扩展的结点）。n死结

25、点死结点：不再进一步扩展或者其儿子结点已全部生成的不再进一步扩展或者其儿子结点已全部生成的结点就是死结点结点就是死结点。233 图搜索术语图搜索术语&方法分类方法分类nn n皇后问题皇后问题q要在要在n*nn*n的国际象棋棋盘中放的国际象棋棋盘中放n n个皇后，使任意两个皇后个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解。同一对角线的任意棋子。求所有的解。问题状态问题状态状态空间状态空间解状态解状态答案状态答案状态24二、广度优先搜索二、广度优先搜索n1图的广度优先遍历图的广度优先遍历/搜索

26、算法搜索算法n2广度优先搜索的应用广度优先搜索的应用q例例7.1求经过城市最少的路线问题求经过城市最少的路线问题q例例7.2走迷宫问题走迷宫问题251 广度优先搜索广度优先搜索n广度优先搜索广度优先搜索q首先访问出发点首先访问出发点V，接着依次访问，接着依次访问V的所有邻接点的所有邻接点Wi，再依次访问分别与，再依次访问分别与Wi邻接的所有未曾访问过邻接的所有未曾访问过的顶点，的顶点，直至与，直至与V相通的顶点都已访问，若相通的顶点都已访问，若此时还有未访问的顶点，则按相同的过程继续。此时还有未访问的顶点，则按相同的过程继续。q活结点的扩展是按先来先处理的原则进行。活结点的扩展是按先来先处理的

27、原则进行。“先被访问的顶点先被访问的顶点”的邻的邻接点先于接点先于“后被后被”被被访问访问V1V2V4V5V3V7V6V8261 广度优先搜索广度优先搜索-算法要素算法要素n广度优先搜索：活结点的扩展是按先来先处理的原则进行；广度优先搜索：活结点的扩展是按先来先处理的原则进行；但搜索过程中还需暂时保存部分活结点。但搜索过程中还需暂时保存部分活结点。q在算法中用在算法中用“队队”来存储每个来存储每个E-结点扩展出的活结点。结点扩展出的活结点。实际应用中，用数组或链表实现队列。实际应用中，用数组或链表实现队列。n开辟数组开辟数组visited记录结点的搜索情况。记录结点的搜索情况。272 广度优先

28、搜索广度优先搜索-算法的基本思路算法的基本思路n算法设计的基本步骤算法设计的基本步骤q1）确定图的存储方式；）确定图的存储方式；q2）图的遍历过程中的操作，其中包括为输出问题解）图的遍历过程中的操作，其中包括为输出问题解而进行的存储操作；而进行的存储操作；q3）输出问题的结论。）输出问题的结论。281 广度优先搜索广度优先搜索-一般算法一般算法n图的搜索的不同实现图的搜索的不同实现q图：邻接表图：邻接表/邻接矩阵邻接矩阵q队列：链表队列：链表/数组数组q机制：递归机制：递归/非递归非递归n广度优先搜索用非广度优先搜索用非递归实现方便。递归实现方便。/从顶点从顶点v 开始的广度优先搜索开始的广度

29、优先搜索把顶点把顶点v标记为已到达顶点；标记为已到达顶点；初始化队列初始化队列Q，其中仅包含一个元素，其中仅包含一个元素v;while(Q不空不空)从队列中删除顶点从队列中删除顶点w;令令u 为邻接于为邻接于w 的顶点的顶点;while(u)if(u 尚未被标记尚未被标记)把把u 加入队列；加入队列；把把u 标记为已到达顶点；标记为已到达顶点；u=邻接于邻接于w 的下一个顶点；的下一个顶点；291 广度优先搜索广度优先搜索-邻接表表示图的算法邻接表表示图的算法intvisitedn;/n为结点个数为结点个数bfs(intk,graphhead)inti;queueQ;edgenode*p;/定

30、义队列定义队列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);/访问访问vjvi

31、sitedp-adjvex=1;EnQueue(Q,p-adjvex);/访问过的访问过的vj入队入队p=p-next;/找找vi的下一邻接点的下一邻接点301 广度优先搜索广度优先搜索-邻接矩阵表示图的算法邻接矩阵表示图的算法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=1and

32、visitedj=0)print(“visitvertex”,j);visitedj=1;EnQueue(Q,j);/访问过的访问过的vj入队入队31例例7.1已知若干个城市的地图，求从一个城市到另一个城市已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少。的路径，要求路径中经过的城市最少。2 广度优先搜索的应用广度优先搜索的应用-例例如上图表示的是从城市如上图表示的是从城市A到城市到城市H的交通图。从图中可的交通图。从图中可以看出，从城市以看出，从城市A到城市到城市H要经过若干个城市。现要找出一要经过若干个城市。现要找出一条经过城市最少的一条路线并输出该路线。条经

33、过城市最少的一条路线并输出该路线。322 广度优先搜索的应用广度优先搜索的应用-例分析例分析图的广度优先搜索类似与树的层次遍历，逐层搜索图的广度优先搜索类似与树的层次遍历，逐层搜索正好可以尽快找到一个结点与另一个结点相对而言最直正好可以尽快找到一个结点与另一个结点相对而言最直接的路径。接的路径。0000000001111010000010100100001001011010010000110100100001111110ABCDEFGHABCDEFGH城市交通图对应的邻接距阵城市交通图对应的邻接距阵 331)将城市将城市A（编号（编号1）入队，队首）入队，队首qh置置0，队尾，队尾qe置置1。

34、2)将队首所指的城市所有可直通的城市入队将队首所指的城市所有可直通的城市入队(如果这个如果这个城市在队中出现过就不入队城市在队中出现过就不入队),然后将队首加然后将队首加1，得到新，得到新的队首城市。重复以上步骤，直到城市的队首城市。重复以上步骤，直到城市H入队为止。当入队为止。当搜到城市搜到城市H时，搜索结束。时，搜索结束。3)输出最少城市线路。输出最少城市线路。2 广度优先搜索的应用广度优先搜索的应用-例分析设计例分析设计0000000001111010000010100100001001011010010000110100100001111110ABCDEFGHABCDEFGH341）二

35、维数组）二维数组jz作为邻接矩阵的存储空间。作为邻接矩阵的存储空间。2）数组）数组sq作为活结点队的存储空间。作为活结点队的存储空间。3）队队列列的的每每个个结结点点有有两两个个成成员员：sqi.city记记录录入入队队的的城城市市，sqi.pre记记录录该该城城市市的的前前趋趋城城市市在在队队列列中中的的下下标，这样通过标，这样通过sqi.pre就可以倒推出最短线路。就可以倒推出最短线路。4）设置数组）设置数组visited记录已搜索过的城市。记录已搜索过的城市。2 广度优先搜索的应用广度优先搜索的应用-例数据结构设计例数据结构设计352 广度优先搜索的应用广度优先搜索的应用-例算法设计例算

36、法设计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=1andvisitedi=0)qe=qe+1;/结点入队结点入队sqqe.city=i;sqqe.pre=qh;visitedi=1;if(sqqe.city=8)out();return;print(“Noavaliableway.”);36算法分析：算法分析：时间复杂度是时间复杂度是O(n)；空间复杂性为；空间复杂性为(n2)，包括图

37、本身的存储空间和搜索时辅助空间包括图本身的存储空间和搜索时辅助空间“队队”的存的存储空间。储空间。out()/输出路径输出路径print(sqqe.city);while(sqqe.pre0)qe=sqqe.pre;print(-,sqqe.city);2 广度优先搜索的应用广度优先搜索的应用-例算法设计例算法设计37n例例7.2迷宫是许多小方格构成的矩形，在每个小方格中有迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的的是墙（图中的“1”），有的是路（图中的），有的是路（图中的“0”）。走）。走迷宫就是从一个小方格沿上、下、左、右四个方向到邻近迷宫就是从一个小方格沿上、下、左、右四

38、个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)，出口是右下角，出口是右下角(8,8)。根据给定的迷宫，找出一条从入。根据给定的迷宫，找出一条从入口到出口的路径。口到出口的路径。2 广度优先搜索的应用广度优先搜索的应用-例例382 广度优先搜索的应用广度优先搜索的应用-例分析例分析(1,1)(3,3)n确定图结构确定图结构q本问题的原始描述，与显式图的标准形象有差别。本问题的原始描述，与显式图的标准形象有差别。n从入口开始出发，广度优先搜索所有可到达的方格入从入口开始出发，广度优先搜索所有可到达的方格入队，再扩展队首的方格，直到搜索

39、到出口时，便得到队，再扩展队首的方格，直到搜索到出口时，便得到一条通路。一条通路。392 例分析设计例分析设计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利用利用原有的迷宫数据原有的迷宫数据，检查两，检查两点之间是否存在边相连；这样点之间是否存在边相连；这样就不必查

40、询任何其他的存储结就不必查询任何其他的存储结构了。构了。二维数组二维数组402 例分析设计例分析设计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)当对

41、应方格值为当对应方格值为0，就扩，就扩展为展为活结点活结点。规律性强，规律性强，验证简单验证简单p为了构造循环体，用数组为了构造循环体，用数组fx=-1,10,0,fy=0,0,-1,1模拟上下左右搜索时下标的变化过程。模拟上下左右搜索时下标的变化过程。p函数函数check，检查当前状态是否合理。，检查当前状态是否合理。412 例分析设计例分析设计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

42、 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;为了能够倒推出路径为了能够倒推出路径422 例分析设计例分析设计q另开辟另开辟visited数组记录已数组记录已搜索过的路径。搜索过的路径。q用迷宫原有的存储空间置元素用迷宫原有的存储空间置元素值为值为“-1”时，标识已经访问过时，标识已经访问过该方格。该方格。n问题问题4：在搜索路径过程中，对

43、搜索过的路径如何标记？：在搜索路径过程中，对搜索过的路径如何标记？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 043intmaze88=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

44、,fy4=0,0,-1,1,;structintx,y,pre;sq100;intqh,qe,i,j,k;main()search();2 广度优先搜索的应用广度优先搜索的应用-例算法设计例算法设计44search()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

45、.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);45nout()/输出路径输出路径print(“(”sqqe.x,“,”,sqqe.y,“)”);while(sqqe.pre0)qe=sqqe.pre;print(-,“,”,sqqe.x,“,”,sqqe.y,“)”);算

46、法分析：算法分析：时间复杂度是时间复杂度是O(n)；空间复杂性为；空间复杂性为(n2)，包括图本身的存储空间和搜索时辅助空间包括图本身的存储空间和搜索时辅助空间“队队”的存的存储空间。储空间。2 例算法设计及分析例算法设计及分析46三、深度优先搜索三、深度优先搜索n1图的深度优先遍历图的深度优先遍历/搜索算法搜索算法n2深度优先搜索的应用深度优先搜索的应用q例例7.2走迷宫问题走迷宫问题q例例7.3七巧板涂色问题七巧板涂色问题q例例7.4割点的判断及消除割点的判断及消除471 深度优先搜索深度优先搜索n首先访问出发点首先访问出发点V1，然后依次搜索其每个邻接点，然后依次搜索其每个邻接点W。若若

47、W为曾访问过，则以为曾访问过，则以W为新的出发点继续深度优先为新的出发点继续深度优先搜索，直至和搜索，直至和V有路径相通的点全部访问。若此时还有有路径相通的点全部访问。若此时还有未访问点，则以此作新出发点继续。未访问点，则以此作新出发点继续。V1V2V4V5V3V7V6V848n深度优先与广度优先的策略比较：深度优先与广度优先的策略比较：q区别在于扩展结点的过程；区别在于扩展结点的过程；q广度优先搜索，扩展广度优先搜索，扩展E-结点的所有邻接点，结点的所有邻接点，E-结点就结点就成为一个死结点。成为一个死结点。一个结点只有一次成为一个结点只有一次成为“活结点活结点”。q深度优先搜索，扩展的是深

48、度优先搜索，扩展的是E-结点的邻接结点中的一个，结点的邻接结点中的一个，并将其作为新的并将其作为新的E-结点继续扩展；当前结点继续扩展；当前E-结点仍为活结点仍为活结点，待搜索完其子结点后，回溯到该结点扩展它的结点，待搜索完其子结点后，回溯到该结点扩展它的其它未搜索的邻接结点。其它未搜索的邻接结点。一个结点可能多次成为一个结点可能多次成为“活活结点结点”。1 深度优先搜索深度优先搜索492 深度优先搜索的应用深度优先搜索的应用-例分析例分析2(1,1)(3,3)n确定图结构确定图结构q本问题的原始描述，与显式图的标准形象有差别。本问题的原始描述，与显式图的标准形象有差别。n从始点出发，按深度优

49、先搜索方式搜索该图，一直向从始点出发，按深度优先搜索方式搜索该图，一直向着可通行的下一个方格行进，直到搜索到终点时，便着可通行的下一个方格行进，直到搜索到终点时，便得到一条通路。若行不通时，则返回上一个方格，继得到一条通路。若行不通时，则返回上一个方格，继续搜索其他方向。续搜索其他方向。n有没有其他方法？有没有其他方法？502 深度优先搜索的应用深度优先搜索的应用-例分析例分析2n数据结构设计：用迷宫本身的存储空间除了记录走过的数据结构设计：用迷宫本身的存储空间除了记录走过的信息，还要标识是否可行：信息，还要标识是否可行：qmazeij=3标识走过的方格；标识走过的方格；qmazeij=2标识

50、走入死胡同的方格；标识走入死胡同的方格；n当一个方格四个方向都搜索完还没有走到出口当一个方格四个方向都搜索完还没有走到出口(存储为存储为2)，说明该方格或无路可走或只能走入了，说明该方格或无路可走或只能走入了“死胡同死胡同”。最后存储为最后存储为“3”的方格为可行的方格。的方格为可行的方格。n函数函数check，检查当前状态是否合理。，检查当前状态是否合理。约束条件约束条件512 深度优先搜索的应用深度优先搜索的应用-例算法例算法2intmaze88=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