题目
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
网友评论