算法快学笔记（十二）：图的广度优先搜索(BFS-Breadth First Search)

女爷i 2022-03-14 17:10 201阅读 0赞

# 1. 介绍 #

广度优先搜索（BFS）是一个经典的图算法，该算法能够找出两样东西之间的最短距离！使用广度优先搜索可以：

*  编写国际跳棋AI，计算最少走多少步就可获胜；
 *  编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词，如将READED改为READER需要编辑一个地方；
 *  根据你的人际关系网络找到关系最近的医生。

要说明的是，广度优先搜索是一种用于图的查找算法，可帮助  
回答两类问题。

*  第一类问题：从节点A出发，有前往节点B的路径吗？
 *  第二类问题：从节点A出发，前往节点B的哪条路径最短？

# 2. 原理说明 #

假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。在Facebook，你与芒果销售商有联系吗？为此，你可在朋友中查找，这种查找很简单。首先，创建一个朋友名单，假设你没有朋友是芒果销售商，那么你就必须在朋友的朋友中查找,检查名单中的每个人时，你也都将其朋友加入名单

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]

这样一来，你不仅在朋友中查找，还在朋友的朋友中查找。别忘了，你的目标是在你的人际关系网中找到一位芒果销售商。因此，如果Alice不是芒果销售商，就将其朋友也加入到名单中。这意味着你将在她的朋友、朋友的朋友等中查找。使用这种算法将搜遍你的整个人际关系网，直到找到芒果销售商。这就是广度优先搜索算法。

对于BFS要解决的第一个问题很容易处理，只要遍历朋友列表，就能得知朋友圈中到底有没有芒果销售商，下面来看看如何找到哪个销售商和你的关系是最好的。

## 2.1 查找最亲密的销售商 ##

为了便于度量关系的亲密度，我们假设朋友是一度关系，朋友的朋友是二度关系…,一度关系胜过二度关系，二度关系胜过三度关系，以此类推.

为了确保找到的销售商关系是最亲密的，你应先在一度关系中搜索，确定其中没有芒果销售商后，才在二度关系中搜索。

BFS算法的执行流程也就是\*\*搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。\*\*

在查找列表的过程中，有点需要注意，因为1度关系比二度关系先添加，二度关系比三度关系先添加，因此只有按添加顺序查找，才能找到最短路径。此处可以使用队列实现。

# 3. 算法实现 #

# -*- coding:utf-8 -*-
    # @Author：sunaihua 
    from collections import deque
    
    graph = {}
    graph["you"] = ["alice", "bob", "claire"]
    graph["bob"] = ["anuj", "peggy"]
    graph["alice"] = ["peggy"]
    graph["claire"] = ["thom", "jonny"]
    graph["anuj"] = []
    graph["peggy"] = []
    graph["thom"] = []
    graph["jonny"] = ["bob"]
    
    # 节点对象，用来标识各个节点之间的父子关系
    # name:字符串类型，代表节点名称
    # parent:Node类型
    class Node:
        def __init__(self, name, parent):
            self.name = name
            self.parent = parent
    
        def __str__(self):
            return self.name
    
    
    def is_seller(friend):
        return friend.name[-1] == 'm'
    
    # 通过bfs找到最近的节点
    def bfs_search():
        search_queue = deque()
        # 初始化任务队列
        search_queue += [Node(name=friend, parent=Node(name='you', parent=None)) for friend in graph['you']]
        searchrd = []
        while search_queue:
            # 每次都弹出队列最左面的元素，且是关系最亲密的。
            friend = search_queue.popleft()
            # 防止重复搜索
            if friend not in searchrd:
                if is_seller(friend):
                    print "has seller,%s is seller" % (friend)
                    return friend
    
                else:
                    # 将当前friend的所有friend添加到队列的最右面
                    search_queue += [Node(name=f, parent=friend) for f in graph[friend.name]]
        return None
    
    # 根据超找到的对象，打印路径
    def print_path(node):
        node_name_stack = []
        node_name_stack.append(node.name)
        parent_node = node.parent
        # 生成节点名称列表
        while parent_node:
            node_name_stack.append(parent_node.name)
            parent_node = parent_node.parent
        # 反转列表
        node_name_stack.reverse()
        # 打印路径
        print "friends path:","--->".join(node_name_stack)
    
    
    if __name__ == '__main__':
        target = bfs_search()
        print_path(target)

# 4. 运行时间 #

如果你在你的整个人际关系网中搜索芒果销售商，就意味着你将沿每条边前行（记住，边是  
从一个人到另一个人的箭头或连接），因此运行时间至少为O(边数)。  
你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的，即为O(1)，因此对每个人都这样做需要的总时间为O(人数)。所以，广度优先搜索的运行时间为  
O(人数 + 边数)，这通常写作O(V + E)，其中V为顶点（vertice）数，E为边数

# 5. 总结 #

*  广度优先搜索主要用来解决最短路径问题
 *  FS算法的执行流程是搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系…
 *  时间复杂度为O(V + E)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]: /images/20220311/30051dfd8a2744c88e15b08814420bc0.png