图是一种善于处理关系型数据的数据结构，使用它可以很轻松地表示数据之间是如何关联的
图的实现形式有很多，简单的方法之一就是用散列表
背景
图有两种经典的遍历方式：广度优先搜索和深度优先搜索。两者是相似的。
实现
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) > : # 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"]}<br>#从A出发找Bb=Bfs("A",json)b.searchV("B") |
