【引言】我们生活中都会有过“找人”的经历。比如，我们想简单的找一个医生来咨询一些事情，或者找一个律师或者是老师。我们会怎么找呢？怎么才能找到呢？我们往往希望找到的这个人是跟我们关系最近的那一个，或者是朋友，或者是朋友的朋友，如果是朋友的朋友的朋友，我们的信任感或者说觉得这个关系就不那么牢靠了。这个过程就是一个搜索的过程，而我们的人际关系网就是一个 图。

广度优先搜索就是一个首先搜索自己身边最近的人，如果没有，我们再扩大搜索范围的一种搜索方法。

算法过程

图

我们可以想象，我们在找人的过程，实际上就是我们搜索我们人际关系关系网中的人的过程，而这个人际关系网，就是由一个个朋友、朋友的朋友……来构建的，我们可以把这种关系看做是一个 图：

我的人际关系图tx~.png

图是有方向的，箭头的方向表示的是从属关系，被指的人是前者的朋友，其实应该是互相指的双向箭头，但是因为我的存在，我只能通过一个人来找到他的朋友，所以有了单向的方向。即使是这样，也会存在一个人同时是几个人的朋友这种情况，可能会出现一个环，如上图，这个环也可能是来回循环的。

广度优先搜索

广度优先搜索，顾名思义，就是尽量的先 广泛 的来搜索。

比如，我要买房子，我就要要找到我身边人际网中的一个搞房地产的人。我该怎么办呢？按照广度优先搜索的话，我应该这么办：
首先，我遍寻我身边的朋友，也就是直接跟我是朋友的人，看看他们是不是搞房地产的人，如果有搞房地产的人，我就算是以一个比较短的路径，一个比较短的时间找到了我所需要的人（黑圈中的人）：

我的朋友们.png

然后，当我遍寻我身边直接的朋友没有找到搞房地产的人的时候，此时我就知道，我身边朋友这个范围已经找不到了，此时我就要增加我的搜索范围，来找我的朋友的朋友了（红圈之内，黑圈之外）：

遍寻朋友的朋友.png

如果我找到了，那么这个搜索过程就结束了，如果没有找到，我再继续搜索朋友的朋友的朋友……，一次次的增加搜索的范围。

这就是广度优先搜索的过程，所谓广度，就是每一次搜索的范围要尽量的广泛，比如，我第一次搜索，范围就是最广泛的，我 遍寻 了我身边所有的 朋友；第二次搜索，我 遍寻 了我身边 朋友的朋友 ；如果有第三次，我就继续遍寻我朋友的朋友的朋友……，很幸运，我在我的朋友的朋友中，找到了我要找的人，这样就以广度优先的搜索方式完成了我找人的目的！

具体的实现逻辑是，我借助一个队列，首先把我所有的朋友加入队列，从队列头一个个的来查看我的朋友是不是我要找的人，如果某个朋友不是我要找的，那么我就把他的朋友继续加入队列的末尾，把他从队列头中拿走，继续的查看队列中第二个朋友，重复这个过程，直到我的队列中的所有人都被我查看过了，没有找到，那我身边就没有这样的人。

队列的示意图.png

算法实现

#coding:utf-8

# 引入队列，实际上用数组也是完全没问题的，有这个就用这个
from collections import deque

# 广度优先搜索的过程
def breadth_first_search(career, name):
    search_queue = deque()
    search_queue += friends[name]
    searched = []
    # 只要待查找的数组不为空，就一直搜索下去
    while search_queue:
        # 从队列的头找出一个朋友
        person = search_queue.popleft()
        # 如果这个朋友没有在已查找的数组中，就确认他的身份（为了防止几个人都互相是朋友的死循环，如果查过这个人，就不再查了）
        if person not in searched:
            # 如果这个人是要找的人，直接返回
            if careers[person] == career:
                return person
            # 如果这个人不是要找的人，就把这个人的朋友放入带查找的队列的末尾
            else:
                search_queue.extend(friends[person])
                searched.append(person)
    # 如果关系网上所有的人中都没有要找的人，就直接返回没有
    return False

# 构建人物的基本职业信息以及朋友网
careers = {"我": "屌丝",
          "吕志安": "医生",
          "李小飞": "律师",
          "林连杰": "老总",
          "王洲": "房地产",
          "王忠义": "护士",
          "封赵蒙": "保险"}

friends = {"我": ["吕志安", "李小飞", "林连杰"],
          "吕志安": ["封赵蒙"],
          "李小飞": ["王洲", "王忠义"],
          "林连杰": [],
          "王洲": ["王忠义"],
          "王忠义": [],
          "封赵蒙": []}

# 进行广度优先搜索，来查找 我 的身边做 房地产 的朋友
searched_man = breadth_first_search("房地产", "我")
if searched_man:
    print("你身边做“房地产”的朋友是： {}".format(searched_man))
else:
    print("你身边没有做“房地产”的朋友")

结果是：

我身边做房地产的朋友是王洲，我二哥.png

上一篇：写给媳妇儿的算法（十）——斐波那切数列
下一篇：写给媳妇儿的算法（十二）——狄克斯特拉算法