用Python实现广度优先搜索

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

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

背景

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

实现

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

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

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

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知道队列为空，算法结束

代码展示

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)

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

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)}

 运行结果

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