从如何最快找到男(女)朋友说起 (BFS 最短路径，几度人脉问题

题目

520了，假如你还是单身，想利用自己的人脉关系，最快找到最心仪、一见钟情的他(她)。该怎么努力找到他(她)呢？

算法选定

最短路径问题的解法，最常见的办法就是BFS(广度优先搜索)

抽象模型

image.png

假设thon和jam都是你心仪的，并且和你一见钟情的。

代码关键逻辑

• 语言选择 python,原因：简单
• 图的表示 散列 原因：完整表达，存取时间复杂度为O(1)
• 搜索数据结构 队列 deqeue 原因：按人脉层级搜索，排序判定，先进先出
• 防止关系循环 数组 原因：查询快，不改变内容
• 人脉关系网记录 散列 原因：简单，效率高，作用和链表一致。懒得实现一个
  链表了。
• 判断是否为心仪的他(她) 简单以末尾'n'或'm'实现。 原因：简单，点到为止。

代码实现

# coding=UTF-8
from collections import deque

graph   = {}
graph["you"]        = ["alice", "bob", "Claire"]
graph["bob"]        = ["anuj", "peggy"]
graph["alice"]      = ["peggy"]
graph["claire"]     = ["thon", "jonny"]
graph["anuj"]       = []
graph["peggy"]      = []
graph["thon"]       = ["jam"]
graph["jonny"]      = ["jam"]
graph["jam"]        = []

print(graph)

parents             = {}

def isLove(name):
    if len(name) < 1:
        return False
    return name[-1] == 'n' or name[-1] == 'm'

def relations(name):
    num             = 0
    chain           = name
    while parents[name] != None:
        num         += 1
        name        = parents[name]
        chain       = name + "->" + chain
    return (str(num), chain)

def addParent(neighbors, parent):
    for n in neighbors:
        parents[n]      = parent

def search(name):
    parents[name]       = None
    search_queue        = deque()
    searched            = []
    neighbors           = graph[name]
    search_queue        += neighbors
    addParent(neighbors, name)

    while search_queue:
        top             = search_queue.popleft()
        if not top in searched:
            if isLove(top):
                relation = relations(top)
                print '我亲爱的他(她)，名叫' + top + "， 他(她)是我的" + relation[0] + "度人脉。" + "关系链条为：" + relation[1]
                return True
            else:
                neighbors    = graph[top]
                search_queue += neighbors
                searched.append(top)
                addParent(neighbors, top)
    return False


search("you")

运行结果 我亲爱的他(她)，名叫thon， 她是我的2度人脉。关系链条为：you->claire->thon

520,祝大家有情人终成眷属~

---

520分割线，以下已归正传

image.png

BFS

• 第一步：图结构字典化

graph   = {}
graph["A"]        = ["B", "C"]
graph["B"]        = ["A", "C"]
graph["C"]        = ["A", "B", "E"]
graph["D"]        = ["B","E","F"]
graph["E"]        = ["C", "D", "G"]
graph["G"]        = ["E"]
graph["F"]        = ["D", "H"]
graph["H"]        = ["F"]

• 第二步：定义函数，需要一个图和一个节点就可以了
  def bfs(graph, vertex):

• 第三步：构建搜索队列。队列先进先出，确定好进和出就可以了
  进：

queue       = deque()
queue.append(vertex)

出:

v       = queue.popleft()

依次出，在出的时候执行搜索的任务就行了，我们这里的任务是print()

• 第四步：构建已被搜索集合，上面找女朋友的例子，我们用了数组，这里我们用set（唯一性）。searched = set()效率更高一些，如果在数据量大时，更明显

第五步：循环搜索就可以了

    while queue:
        v       = queue.popleft()
        neibs   = graph[v]
        for n in neibs:
            if n not in searched:
                queue.append(n)
                searched.add(n)
        print("bfs-> " + v)

DFS

dfs其实只需要改一行即可。把先进先出，改为先进后出，每次取队列的尾部就可以了。v = queue.popleft()改为 v = queue.pop()

完整的代码贴给大家

# coding=UTF-8
from collections import deque

graph   = {}
graph["A"]        = ["B", "C"]
graph["B"]        = ["A", "C"]
graph["C"]        = ["A", "B", "E"]
graph["D"]        = ["B","E","F"]
graph["E"]        = ["C", "D", "G"]
graph["G"]        = ["E"]
graph["F"]        = ["D", "H"]
graph["H"]        = ["F"]




def bfs(graph, vertex):
    searched    = set()
    queue       = deque()
    queue.append(vertex)
    searched.add(vertex)
    while queue:
        v       = queue.popleft()
        neibs   = graph[v]
        for n in neibs:
            if n not in searched:
                queue.append(n)
                searched.add(n)
        print("bfs-> " + v)




def dfs(graph, vertex):
    searched    = set()
    stack       = deque()
    stack.append(vertex)
    searched.add(vertex)

    while stack:
        v       = stack.pop()
        neibs   = graph[v]
        for n in neibs:
            if n not in searched:
                stack.append(n)
                searched.add(n)
        print("dfs-> " + v)


def compareDBFS(graph, vertex):
    bfs(graph, vertex)
    print("-----------------------------")
    dfs(graph, vertex)



compareDBFS(graph, "E")

运行结果

bfs-> E
bfs-> C
bfs-> D
bfs-> G
bfs-> A
bfs-> B
bfs-> F
bfs-> H
-----------------------------
dfs-> E
dfs-> G
dfs-> D
dfs-> F
dfs-> H
dfs-> B
dfs-> A
dfs-> C