图算法——广度优先搜索（breadth-first search，BFS）

解决最短路径问题的算法被称为广度优先搜索。

图是什么？图模拟一组连接，由节点（node）和边（edge）组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

问题：假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。在通讯录中，你与芒果销售商有联系吗？为此，你可在朋友中查找。

找橘子商示例代码：

from collections import deque

def search(name):    
    search_queue = deque()
    search_queue += graph[name]
    #这个数组用于记录检查过的人
    searched = []
    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:
                #继续搜索s_q = s_q + graph[person] 后面一项是person的邻居
                search_queue +=graph[person]
                #将这个人标记为检查过
                searched.append(person)
    print("not found")
    return False
    
def person_is_seller(name):
    return name[-1] == 'm'

#测试
graph ={}
graph["you"] = ["alice","bob","c"]
graph["alice"] =[]
graph["bob"] = []
graph["c"] = []
search("you")

运行时间

广度优先搜索的运行时间为O(人数 + 边数)，这通常写作O(V + E)，其中V为顶点（vertice）数，E为边数。

小结

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