广度搜索优先

Myth丶恋晨 2022-05-09 07:52 253阅读 0赞

广度优先搜索的通俗化定义

所谓广度，就是**一层一层的，向下遍历，层层堵截**，还是这幅图，我们如果要是广度优先遍历的话，我们的结果是V1 V2 V3 V4 V5 V6 V7 V8。

[![e1fe9925bc315c6040f8459481b1cb134954775f.jpg][]][e1fe9925bc315c6040f8459481b1cb134954775f.jpg 1]

1、访问顶点vi ；

2、访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ；

3、依次从这些邻接点（在步骤②中访问的顶点）出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；

广度优先搜索的用途和注意事项：

 广度优先搜索指出是否有从A到B的路径。  
 如果有，广度优先搜索将找出最短路径。  
 面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来  
解决问题。  
 有向图中的边为箭头，箭头的方向指定了关系的方向，例如，rama→adit表示rama欠adit钱。  
 无向图中的边不带箭头，其中的关系是双向的，例如，ross - rachel表示“ross与rachel约  
会，而rachel也与ross约会”。  
 队列是先进先出（FIFO）的。  
 栈是后进先出（LIFO）的。  
 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必  
须是队列。  
 对于检查过的人，务必不要再去检查，否则可能导致无限循环。

广度优先搜索的实现代码：

def search(name):
        search_queue = deque()
        search_queue += graph[name]
        searched = []   <-------------------------这个suzuki用于记录检查过的人
        while search_queue:
            person = search_queue.popleft()  <----------取出队列中的第一个
            if not person in searched:   <-------------仅当这个没检查过时才检查
                if person_is_seller(person):
                    print person + " is a mango seller!"
                    return True
                else:
                    search_queue += graph[person]  <----------将和person有关的人加入对列
                    searched.append(person)   <--------------将这个人记为检查过
        return False
    
    
    search("you")

## 与深度优先搜索的对比 ##

深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形：（结合栈的先进后出特性）

1、把根节点压入栈中。

2、每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。

3、找到所要找的元素时结束程序。

4、如果遍历整个树还没有找到，结束程序。

广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形：（结合队列的先进先出特性）

1、把根节点放到队列的末尾。

2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。

3、找到所要找的元素时结束程序。

4、如果遍历整个树还没有找到，结束程序。

广度优先搜索会从根节点开始，一级级往下进行，上一级没有搜索完毕不会进行下一级搜索，这是因为，下一级称之为上一级的子节点，所有的下一级子节点在队列里的位置放在上一级节点的后面，根据队列先进先出的特点，上一级所有元素必须全部取出以后才能去取下一级节点。

[e1fe9925bc315c6040f8459481b1cb134954775f.jpg]: https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D220/sign=78878a689bdda144de096bb082b6d009/e1fe9925bc315c6040f8459481b1cb134954775f.jpg
[e1fe9925bc315c6040f8459481b1cb134954775f.jpg 1]: https://baike.baidu.com/pic/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E7%AE%97%E6%B3%95/5724468/0/e1fe9925bc315c6040f8459481b1cb134954775f?fr=lemma&ct=single