用Python实现广度优先搜索

图是一种善于处理关系型数据的数据结构，使用它可以很轻松地表示数据之间是如何关联的

图的实现形式有很多，最简单的方法之一就是用散列表

背景

图有两种经典的遍历方式：广度优先搜索和深度优先搜索。两者是相似的。

实现

1广度优先搜索算法需要用队列来记录后续要处理哪些顶点。

2该队列最初只含有起步的顶点

3处理顶点。我们将其移出队列，标为“已访问”，并记为当前顶点

?

1 2 3 4 5 6 7 8 9

class Bfs:     def __init__(self,from_v,json):         # 最初的顶点         self.from_v = from_v         # 已访问         self.visitList = [self.from_v]         # 需要一个队列来记录后续需要处理哪些顶点         self.vertexQ = queue.Queue()         self.json = json

 核心步骤

(1) 找出当前顶点的所有邻接点。如果有哪个是没访问过的，就把它标为“已访问”，并且将它入队。（尽管该顶点并未作为“当前顶点”被访问过。）

(2) 如果当前顶点没有未访问的邻接点，且队列不为空，那就再从队列中移出一个顶点作为当前顶点。

(3) 如果当前顶点没有未访问的邻接点，且队列里也没有其他顶点，那么算法完成。

图解

 

1首先A会作为顶点，A被访问

2再去寻找A领接点B、D，依次加入队列

3A所有领接点都访问完成，开始访问B的领接点

4知道队列为空，算法结束

代码展示

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Bfs:     def __init__(self,from_v,json):         # 最初的顶点         self.from_v = from_v         # 已访问         self.visitList = [self.from_v]         # 需要一个队列来记录后续需要处理哪些顶点         self.vertexQ = queue.Queue()         self.json = json       def find_neighbor(self,currentVertex):         #寻找领接点         for neighbor in self.json[currentVertex]:             if neighbor not in self.visitList:                 self.visitList.append(neighbor)                 self.vertexQ.put(neighbor)       def checkTOV(self,currentVertex,to_v):         #检测要寻找的值（to_v）是否已经在当前currentVertex中         return to_v in self.json[currentVertex]       def searchV(self,to_v):         reverseList = [self.from_v]         self.find_neighbor(self.from_v)         while not self.vertexQ.empty():             currentVertex = self.vertexQ.get()             reverseList.append(currentVertex)             tmp_path = Reverse(currentVertex,self.json).reverseOrder(reverseList,currentVertex)             if currentVertex == to_v:                 print(tmp_path)             else:                 self.find_neighbor(currentVertex)                 if self.checkTOV(currentVertex,to_v):                     tmp_path.append(to_v)                     print(tmp_path)

 此外我们额外写了一个向上反向找寻路径的工具类（主要代码写好，不想动原来的结构了）

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Reverse:     def __init__(self,from_v,json):         self.from_v = from_v         self.json = json     def reverseOrder(self,reverseList:list,current_v):         indexReverseList = self.indexReverseList(reverseList)         res = [self.from_v]         tmp = current_v         while len(reverseList) > 0 :             # for _key in self.value2Key(current_v):             _key = self.value2Key(reverseList,tmp)             res.append(_key)             reverseList = reverseList[:indexReverseList[_key]]             tmp = _key         return res[::-1]       def value2Key(self,reverseList:list,current_v):         #根据值找json中的key         #这里我们每次都只取离我们最近的一个key         indexReverseList = self.indexReverseList(reverseList)         tmp = -1         for _key, _value in self.json.items():             if current_v in _value and _key in reverseList and (index := indexReverseList[_key]) > tmp:                 tmp = index         return reverseList[tmp]       def indexReverseList(self,reverseList:list):         return {value: index for index, value in enumerate(reverseList)}

 运行结果

?

1 2 3

json = {"A":["B","D"],"B":["C"],"C":["E","D"],"D":["E"],"E":["B"]} #从A出发找B b=Bfs("A",json) b.searchV("B")