用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，依次加入队列