参考自 MOOC数据结构与算法Python版

目录

一、广度优先搜索1.1 BFS算法过程1.2 广度优先搜索算法分析二、深度优先搜索2.1 骑士周游2.1.1 问题定义2.1.2 构建骑士周游图2.1.3 构建走棋关系图2.1.4 骑士周游问题算法实现2.1.5 骑士周游问题算法分析与改进2.2 通用的深度优先搜索2.3 通用的深度优先搜索算法分析

一、广度优先搜索

在单词关系图建立完成以后， 需要继续在图中寻找词梯问题的最短序列，即要用到“广度优先搜索Breadth First Search”算法对单词关系图进行搜索。BFS是搜索图的最简单算法之一， 也是其它一些重要的图算法的基础

给定图G， 以及开始搜索的起始顶点sBFS搜索所有从s可到达顶点的边，距离为1在达到更远的距离k+1的顶点之前， BFS会找到全部距离为k的顶点

可以想象为以s为根，构建一棵树的过程，从顶部向下逐步增加层次，广度优先搜索能保证在增加层次之前，添加了所有兄弟节点到树中

1.1 BFS算法过程

为了跟踪顶点的加入过程， 并避免重复顶点， 要为顶点增加以下属性：

距离distance：从起始顶点到此顶点路径长度；前驱顶点predecessor：可反向追溯到起点；颜色color：标识了此顶点是尚未发现（白色）、已经发现（灰色）、还是已经完成探索（黑色）队列Queue来对已发现的顶点进行排列，决定下一个要探索的顶点（队首顶点）

步骤：

1.从起始顶点s开始， 作为刚发现的顶点，标注为灰色， 距离为0， 前驱为None，

加入队列， 接下来是个循环迭代过程：

2.从队首取出一个顶点作为当前顶点；

3.遍历当前顶点的邻接顶点，如果是尚未发现的白色顶点，则将其颜色改为灰色（已发现），距离增加1，前驱顶点为当前顶点，加入到队列中

4.遍历完成后，将当前顶点设置为黑色（已探索过），循环回到步骤2的队首取当前顶点

def bfs(g, start):start.setDistance(0)start.setPred(None)vertQueue = Queue()vertQueue.enqueue(start)while vertQueue.size()>0:currentVert = vertQueue.dequeue() #取队首作为当前顶点for nbr in currentVert.getConnections(): #遍历邻接顶点if nbr.getColor() == 'white':nbr.setColor('gray')nbr.setDistance(currentVert.getDistance() + 1)nbr.setPred(currentVert)vertQueue.enqueue(nbr)currentVert.setColor('black') #当前顶点设置为黑色

在以FOOL为起始顶点， 遍历了所有顶点， 并为每个顶点着色、赋距离和前驱之后，即可以通过一个回途追溯函数来确定FOOL到任何单词顶点的最短词梯！

def traverse(y):x = ywhile x.getPred():print(x.getId())x = x.getPred()print(x.getId())wordGraph = buildGraph("test.txt")bfs(wordGraph, wordGraph.getVertex('FOOl'))traverse(wordGraph.getVertex)

1.2 广度优先搜索算法分析

BFS算法主体是两个循环的嵌套

while循环对每个顶点访问一次，所以是O(∣V∣)O(|V|)O(∣V∣)嵌套在while中的for，由于每条边只有在其起始顶点u出队的时候才会被检查一次,而每个顶点最多出队1次，所以边最多被检查1次，一共是O(∣E∣)O(|E|)O(∣E∣)

综合起来BFS的时间复杂度为O(∣V∣+∣E∣)O(|V|+|E|)O(∣V∣+∣E∣)

词梯问题还包括两个部分算法:

建立BFS树之后， 回溯顶点到起始顶点的过程，最多为O(|V|)创建单词关系图也需要时间，最多为O(|V|2)

二、深度优先搜索

2.1 骑士周游

2.1.1 问题定义

在一个国际象棋棋盘上， 一个棋子“马”（骑士） ， 按照“马走日”的规则， 从一个格子出发， 要走遍所有棋盘格恰好一次。把一个这样的走棋序列称为一次“周游”

在8×8的国际象棋棋盘上， 合格的“周游”数量有1.305×1035这么多， 走棋过程中失败的周游就更多了

采用图搜索算法， 是解决骑士周游问题最容易理解和编程的方案之一.解决方案还是分为两步：

首先将合法走棋次序表示为一个图采用图搜索算法搜寻一个长度为（行×列-1）的路径，路径上包含每个顶点恰一次

2.1.2 构建骑士周游图

将棋盘和走棋步骤构建为图的思路：

将棋盘格作为顶点按照“马走日”规则的走棋步骤作为连接边建立每一个棋盘格的所有合法走棋步骤能够到达的棋盘格关系图

def genLegalMoves(x, y, bdSize):newMoves = []# 马走日的八个格子，“-”表示向左moveOffsets = [(-1,-2),(-1,2),(-2,-1),(-2,-1),(1, -2),(1, 2),(2, -1),(2, 1)]for i in moveOffsets:newX = x + i[0]newY = y = i[1]if legalCoord(newX, bdSize) and legalCoord(newY, bdSize):newMoves.append((newX,newY))return newMovesdef legalCoord(x, bdSize): #确定不会走出棋盘if 0< x < bdSize:return Trueelse: return False

2.1.3 构建走棋关系图

def knightGraph(bdSize): #bdSize表示正方形棋盘边的大小ktGraph = Graph()for row in range(bdSize): #遍历每个格子for col in range(bdSize):nodeId = posToNodeId(row,col,bdSize)newPositions = genLegalMoves(row,col,bdSize)for e in newPositions:nid = posToNodeId(e[0],e[1],bdSize)ktGraph.addEdge(nodeId,nid) #添加边及顶点return ktGraphdef posToNodeId(row, col, bdSize): #每个格子生成一个Idreturn row*bdSize + col

骑士周游图： 8×8棋盘生成的图，具有336条边， 相比起全连接的4096条边， 仅8.2%， 还是稀疏图

2.1.4 骑士周游问题算法实现

用于解决骑士周游问题的图搜索算法是深度优先搜索（Depth First Search）,相比前述的广度优先搜索， 其特点是逐层建立搜索树，深度优先搜索是沿着树的单支尽量深入向下搜索，如果到无法继续的程度还未找到问题解，就回溯上一层再搜索下一支。

DFS的两个实现算法

一个DFS算法用于解决骑士周游问题，其特点是每个顶点仅访问一次另一个DFS算法更为通用，允许顶点被重复访问，可作为其它图算法的基础

深度优先搜索解决骑士周游的关键思路：

如果沿着单支深入搜索到无法继续（所有合法移动都已经被走过了）时，路径长度还没有达到预定值（8×8棋盘为63）那么就清除颜色标记，返回到上一层换一个分支继续深入搜索

引入一个栈来记录路径，并实施返回上一层的回溯操作

def knightTour(n,path,u,limit): #层次，路径，当前顶点，搜索总深度u.setColor('grey')path.append(u) #将当前顶点加入路径if n < limit:nbrList = list(u.getConnections()) #对所有合法移动逐一深入i = 0done = Falsewhile i < len(nbrList) and not done:if nbrList[i].getColor() == "while": #选择未经过的顶点done = knightTour(n+1, path, nbrList[i], limit)#层次加1，递归深入i += 1if not done: #都无法完成总深度，回溯path.pop()u.setColor("white")else: done = Truereturn done

2.1.5 骑士周游问题算法分析与改进

上述算法的性能高度依赖于棋盘大小：就5×5棋盘，约1.5秒可以得到一个周游路径，但8×8棋盘，则要半个小时以上才能得到一个解，目前实现的算法， 其复杂度为O(kn)O(k^n)O(kn)， 其中n是棋盘格数目.

对nbrList的灵巧构造，以特定方式排列顶点访问次序，可以使得8×8棋盘的周游路径搜索时间降低到秒级！这个改进算法被特别以发明者名字命名：Warnsdorff算法。

初始算法中nbrList， 直接以原始顺序来确定深度优先搜索的分支次序新的算法， 仅修改了遍历下一格的次序

将u的合法移动目标棋盘格排序为：具有最少合法移动目标的格子优先搜索,（先周边再中间）

def orderByAvail(n):resList = []for v in n.getConnections():if v.getColor() == "white":c = 0for w in v.getConnections():if w.getColor() == 'white':c += 1resList.append((c,v))resList.sort(key = lambda x: x[0])return [y[1] for y in resList]

2.2 通用的深度优先搜索

骑士周游问题是一种特殊的对图进行深度优先搜索，其目的是建立一个没有分支的最深的深度优先树，表现为一条线性的包含所有节点的退化树。

一般的深度优先搜索目标是在图上进行尽量深的搜索， 连接尽量多的顶点， 必要时可以进行分支（创建了树），有时候深度优先搜索会创建多棵树，称为“深度优先森林”。深度优先搜索同样要用到顶点的“前驱”属性， 来构建树或森林，另外要设置“发现时间”和“结束时间”属性，这两个新属性对后面的图算法很重要 前者是在第几步访问到这个顶点（设置灰色）后者是在第几步完成了此顶点探索（设置黑色） 带有DFS算法的图实现为Graph的子类 顶点Vertex增加了成员Discovery及Finish图Graph增加了成员time，用于记录算法执行的步骤数目

BFS采用队列存储待访问顶点

DFS则是通过递归调用，隐式使用了栈

form pythonds.graphs import Graphclass DFSGraph(Graph):def __init__(self):super().__init__()self.time = 0def dfs(self):for aVertex in self: #颜色初始化aVertex.setColor('white')aVertex.setPred(-1)for aVertex in self:if aVertex.getColor() == 'white':self.dfsvisit(aVertex)#只要未访问，则建立单棵森林def dfsvisit(self,startVertex):startVertex.setColor('gray') #设置开始顶点为灰色self.time += 1 #算法的步数startVertex.setDiscovery(self.time)for nextVertex in startVertex.getConnections():if nextVertex.getColor() == 'white':nextVertex.setPred(startVertex)#只要未访问，则下一步以该节点为顶点self.dfsvisit(nextVertex)startVertex.setColor('black')self.time += 1startVertex.setFinish(self.time) #深度优先递归访问

DFS构建的树， 其顶点的“发现时间”和“结束时间”属性， 具有类似括号的性质

即一个顶点的“发现时间”总小于所有子顶点的“发现时间而“结束时间”则大于所有子顶点“结束时间”比子顶点更早被发现，更晚被结束探索

2.3 通用的深度优先搜索算法分析

DFS运行时间同样也包括了两方面：

dfs函数中有两个循环，每个都是|V|次，所以是O(∣V∣)O(|V|)O(∣V∣)而dfsvisit函数中的循环则是对当前顶点所连接的顶点进行，而且仅有在顶点为白色的情况下才进行递归调用，所以对每条边来说只会运行一步，所以是O(∣E∣)O(|E|)O(∣E∣)

加起来就是和BFS一样的O(∣V∣+∣E∣)O(|V|+|E|)O(∣V∣+∣E∣)

数据结构与算法（python）：广度优先搜索（Breadth First Search BFS）和深度优先算法（Depth First Search DFS）