计算与人工智能概论（第2版）（微课版）课件 第5章 算法设计4 DFS与BFS

计算与人工智能概论第5章算法思维第四节DFS与BFS

深度优先遍历

DFS1PART深度优先遍历（DeepFirstSearch），简称DFS，是一种用于在树型结构（树，tree）或网状结构（图，graph）中进行搜索的有效算法。什么是DFS树是由结点和边组成的不存在任何环的一种数据结构。一棵树可以看成由根结点和子树构成，因此，树具有天然的递归结构。没有结点的树称为空树。假设某个班有10位同学，李明是班长，班级下面有3个小组，小组长分别为张华、马芳和赵杰，每个小组又包含若干同学，对于这种结构，我们可以用一颗树来进行表达树（tree）这颗树可分解为如下4个部分，其中，子树又可以继续分解下去。根结点李明以张华为根结点的子树以马芳为根结点的子树以赵杰为根结点的子树树的分解可以用Python语言的嵌套列表来表达这颗树，一颗树由根结点以及各个子树构成，子树的结构和原树相同：tree=['李明',#根节点['张华',['朱丽'],['王晓']],#子树1['马芳',['李欣']],#子树2['赵杰',['刘密'],['马津'],['陈希']]#子树3]树的表达如果要求输出班级中所有同学的姓名，需要对整颗树进行遍历，访问每个节点。对一颗树进行遍历的方法有两大类，一类是深度优先遍历（DeepFirstSearch，DFS），另一类是广度优先遍历（BreadthFirstSearch，BFS）。树的遍历沿着树的边一直往下走，直到最底层的某个叶子结点，然后再往回走，从枝桠处继续往下走，一直这样下去，直到将所有的节点都访问一次。可以按照树的分解方式依次访问这颗树的不同部分，其中子树的访问方式和原树一样，以递归的方式进行访问：访问根结点访问以张华为根结点的子树访问以马芳为根结点的子树访问以赵杰为根结点的子树树的DFSdefdfs(tree):forindex,iteminenumerate(tree):ifindex==0:print(item)else:dfs(item)

#递归访问子树dfs(tree)设树中的节点总数为n，由于每个节点都会被访问且只访问1次，因此，dfs的时间复杂度为O(n)。树的DFS源代码图（Graph）是另一种经常使用dfs进行搜索的结构。图由一系列的顶点构成，这些顶点之间存在一些连线，称之为边，边可以具有权重的属性。

地图就是一种典型的图结构，地图中的地名是顶点，边是两个地点之间的路径，边的权重就是路径的距离（或者通行时间等）。图（graph）湖南大学地图的抽象对湖南大学地图进行抽象抽取若干重要地点作为「顶点」将这些地点之间的道路用线条标注出来形成「边」得到右边的「图」湖南大学地图的抽象假设有一台机器人，要设计一个寻路算法，从天马公寓出发，找到一条有效的路径，最后到达图书馆。可行的路径：路线1：天马公寓->五食堂->体育馆->图书馆路线2：天马公寓->五食堂->逸夫楼->东方红广场->图书馆路线3：天马公寓->综合楼->图书馆路线4：天马公寓->综合楼->逸夫楼->东方红广场->图书馆路线5：天马公寓->综合楼->逸夫楼->五食堂->体育馆->图书馆机器人寻路问题用邻接矩阵来存储图的信息，邻接矩阵是一个表格，表格中标注为1的格子表示行和列所示地名之间存在一条直接路径。图的表达

天马公寓综合楼超算中心逸夫楼东方红广场图书馆体育馆五食堂天马公寓

1

1综合楼1

11

1

超算中心

1

逸夫楼

1

1

1东方红广场

1

1

图书馆

1

1

1

体育馆

1

1五食堂1

1

1

用Python语言的嵌套列表来表达邻接矩阵：map=[[0,1,0,0,0,0,0,1], [1,0,1,1,0,1,0,0], [0,1,0,0,0,0,0,0], [0,1,0,0,1,0,0,1], [0,0,0,1,0,1,0,0], [0,1,0,0,1,0,1,0], [0,0,0,0,0,1,0,1], [1,0,0,1,0,0,1,0]]图的表达天马公寓、综合楼、超算中心、逸夫楼、东方红广场、图书馆、体育馆、五食堂的编号分别为0、1、2...7从天马公寓到图书馆的寻路问题，转化为从编号0到编号5的寻路问题。地名对应的编号可当作索引号对map中的元素进行索引，元素值为1表示有一条路径，为0表示没有路径，例如，map[1][0]为1，表示综合楼和天马公寓之间有一条路径。将图看成一颗特殊的树，以起点天马公寓为根结点，其子节点是通过边连接到的各个顶点。由于图的特性，树中很多结点都是重复的将图看作树对图进行DFS和树的DFS的基本原理是一样的，但由于图存在回路，导致对应的树存在重复结点，需要对已访问过的结点进行标记，递归时根据标记避开已经访问过的结点。访问根结点，如果是终点，算法结束将根结点的状态标记为已访问依次递归访问未访问过的子树问题分解机器人位于地点P1时，对所有和P1连接的其他地点进行循环若某个地点没有访问过，就控制机器人走过去，并且标记为已访问对于连接到P1的其他地点，依次进行尝试如果没有地方可去了，就退回去，再看看有没有其他地方可走。路径选择路径选择源代码name=['天马公寓','综合楼','超算中心','逸夫楼','东方红广场','图书馆','体育馆','五食堂']visited=[0]*8

#记录顶点是否访问path=[]#保存路径的列表def

dfs(start,end):#返回True表示已找到终点

path.append(name[start])#将顶点加入路径

visited[start]=1

#标记该顶点已访问

ifstart==end:return

True

fori,xin

enumerate(map[start]):

ifx==1

andvisited[i]==0:

ifdfs(i,end):#对新的未访问顶点递归

return

True

#循环完，没有新的路可走，删除路径中最后的一个顶点

path.pop()

return

Falsedfs(0,5)#0，5分别是起点和终点的编号print(path)

广度优先遍历

BFS2PART栈是一种常用的数据结构，主要特点是后进先出（LastInFirstOut，LIFO）。例如：把书一本接一本的放到桌上，拿的时候只能先拿上面的。栈（stack）假设桌面一开始是空的，每次只往桌上放一本书。如此堆叠，便能构建出一个栈。取书的顺序正好与放书的顺序相反，即：元素的插入顺序正好与移除顺序相反。这就是栈的反转特性。栈的反转特性模块fromqueueimportLifoQueue定义栈（0表示容量无穷大）stack_=LifoQueue(maxsize=0)

将元素压入栈顶stack_.put(x)从栈顶弹出元素x=stack_.get()

栈中元素数目stack_.qsize():实际上，python的栈叫做后进先出队列，和后面介绍的队列，拥有完全相同的使用方式。python的栈LifoQueue栈是一种后进先出的数据结构，而队列与之相反，是一种先进先出(FirstInFirstOut，FIFO)的数据结构。顾名思义，队列就是排队，好比到食堂打饭，排在前面的人先打饭，然后出队列；新来的人排到队列的末尾。队列（queue）模块fromqueueimportQueue定义队列（0表示容量无穷大）queue1=Queue(maxsize=0)

将元素追加入队列末尾queue1.put(x)从队列的最前面弹出元素x=queue1.get()

队列中元素数目queue1.qsize():

python的队列QueueBFS，即BreadthFirstSearch，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中，队列中的元素再以FIFO的顺序取出并进行处理。通常，处理过的元素要进行标记。广度优先搜索(BFS)给定给定一个M×N的迷宫图、入口与出口、行走规则。求一条从指定入口到出口的最短路径。所求路径必须是简单路径，即路径不重复。如有多条最短路径，优先顺序为右、下、左、上。为了求解问题的方便，在数组的周围加上围墙，即在周围加上两行和两列。形成M+2行，N+2列的迷宫数组。迷宫问题解题思路从入口节点开始，寻找所有下一个能继续走的点，根据下一个的点继续寻找所有能走的点，直到该点等于出口。实现方法：创建一个空队列，将起点位置放入队列。在队列不为空的时候循环：出队一次。如果当前位置为出口，则结束算法；否则找出当前方块的4个相邻方块中可走的方块（走过的方块进行标记，以后遇到不能再走），加入队列。迷宫问题解题思路地图信息保存在嵌套列表中，1表示墙，0表示通道。maze=[[1,1,1,1,1,1,1,1,1,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,0,0,1,1,0,0,1],[1,0,1,1,1,0,0,0,0,1],[1,0,0,0,1,0,0,0,0,1],[1,0,1,0,0,0,1,0,0,1],[1,0,1,1,1,0,1,1,0,1],[1,1,0,0,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1],]迷宫问题解题思路如何找到并输出最短路径？定义一个列表path，每次从队列中取出一个位置时，将该位置放入列表；加入队列的位置信息，除了这个位置的坐标之外，额外再记录该坐标上一个位置的坐标在列表path中的索引号。到达终点后，从path最后一个元素出发，沿着上一位置信息，可以溯源到起点；将溯源信息倒着输出，就是要找的最短路径。因此，BFS从起点开始一圈圈往外扩，见到终点即结束遍历，因此，可以高效地找到最短路径。迷宫问题maze=[[1,1,1,1,1,1,1,1,1,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,0,0,1,1,0,0,1],[1,0,1,1,1,0,0,0,0,1],[1,0,0,0,1,0,0,0,0,1],[1,0,1,0,0,0,1,0,0,1],[1,0,1,1,1,0,1,1,0,1],[1,1,0,0,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1],]dirs=[lambdax,y:(x+1,y),lambdax,y:(x,y+1),lambdax,y:(x-1,y),lambdax,y:(x,y-1),]实现代码迷宫问题#通过path找到最短路径defshortest_path(path):shortestpath=[]curNode=path[-1]whilecurNode!=path[0]:shortestpath.append(curNode)curNode=path[curNode[2]]#找到前一个位置

shortestpath.append(path[0])shortestpath.reverse()returnshortestpath迷宫问题defgo_maze(x1,y1,x2,y2):

queue=Queue()

path=[]

queue.put((x1,y1,-1))#起点

maze[y1][x1]=-1#标记起点已经走过

whilequeue.qsize()>0:

curNode=queue.get()

path.append(curNode)ifcurNode[0]==x2andcurNode[1]==y2:forx,y,_inshortest_path(path):print('%d%d'%(x,y))returnTruefordirindirs:#找四个方向

nextN