qinggeouye
https://github.com/qinggeouye/GeekTime/blob/master/MathematicProgrammer/14_breadthFirstSearch/lesson14_1.py
两个预留方法的 python 实现:
get_next_degree_friend(user_nodes, que, visited) 去掉了 user_id_a 和 degree_a 两个参数。
如果把 user_id_a 看作圆心,它的一度好友看作第一层节点,二度好友看作第二层节点 .... ,que 队列只保留某一层的节点即可,visited 仍保存所有访问过的节点。
def get_next_degree_friend(user_nodes, que, visited):
"""
:param user_nodes: 用户节点网络
:param que: 某一层用户节点 即第几度好友
:param visited: 已访问的所有用户节点
:return:
"""
que_return = queue.Queue() # 只保存某个用户的第几度好友
visited_return = set() # 保存从某个用户开始到第几度好友
while not que.empty():
current_user_id = que.get()
if user_nodes[current_user_id] is None:
continue
for friend_id in user_nodes[current_user_id].friends:
if user_nodes[friend_id] is None:
continue
if friend_id in visited:
continue
que_return.put(friend_id)
visited_return.add(friend_id) # 记录已经访问过的节点
return que_return, visited_return
def has_overlap(visited_a, visited_b):
# 两个 set() 的交集
return len(visited_a & visited_b) > 0
#测试结果:
if __name__ == "__main__":
user_nodes_list = set_user_relation(10, 20)
for i in range(len(user_nodes_list)):
print("用户 %s 的好友: %s" % (user_nodes_list[i].user_id, user_nodes_list[i].friends))
print("---------双向广度优先搜索---------")
print("两个用户节点 1和2 之间的最短路径长度:", bi_bfs(user_nodes_list, 1, 2))
用户 0 的好友: {8, 2, 3, 6}
用户 1 的好友: {8, 3, 5}
用户 2 的好友: {0, 4}
用户 3 的好友: {0, 1, 4, 5, 8, 9}
用户 4 的好友: {2, 3}
用户 5 的好友: {9, 3, 6, 1}
用户 6 的好友: {0, 8, 5}
用户 7 的好友: {9}
用户 8 的好友: {0, 1, 3, 6, 9}
用户 9 的好友: {8, 3, 5, 7}
---------双向广度优先搜索---------
两个用户节点 1和2 之间的最短路径长度: 3
作者回复: 思路是对的,使用set实现代码也很简洁