我希望创建一个简单的广度优先搜索算法,该算法返回最短路径。
演员信息字典将演员映射到演员出现的电影列表:
actor_info = { "act1" : ["movieC", "movieA"], "act2" : ["movieA", "movieB"],
"act3" :["movieA", "movieB"], "act4" : ["movieC", "movieD"],
"act5" : ["movieD", "movieB"], "act6" : ["movieE"],
"act7" : ["movieG", "movieE"], "act8" : ["movieD", "movieF"],
"KevinBacon" : ["movieF"], "act10" : ["movieG"], "act11" : ["movieG"] }
这个的反函数将电影映射到出现在它们中的演员列表:
movie_info = {'movieB': ['act2', 'act3', 'act5'], 'movieC': ['act1', 'act4'],
'movieA': ['act1', 'act2', 'act3'], 'movieF': ['KevinBacon', 'act8'],
'movieG': ['act7', 'act10', 'act11'], 'movieD': ['act8', 'act4', 'act5'],
'movieE': ['act6', 'act7']}
所以针对一个调用
shortest_dictance("act1", "Kevin Bacon", actor_info, movie_info)
我应该得到 3
,因为act1
出现在movieC
中,并与出现在movieD
中的Act4
一起出现,而Act8
又出现在与KevinBacon
一起出现的movie F
中。所以最短距离是3。
到目前为止,我有以下内容:
def shotest_distance(actA, actB, actor_info, movie_info):
'''Return the number of movies required to connect actA and actB.
If theres no connection return -1.'''
# So we keep 2 lists of actors:
# 1.The actors that we have already investigated.
# 2.The actors that need to be investigated because we have found a
# connection beginning at actA. This list must be
# ordered, since we want to investigate actors in the order we
# discover them.
# -- Each time we put an actor in this list, we also store
# her distance from actA.
investigated = []
to_investigate = [actA]
distance = 0
while actB not in to_investigate and to_investigate!= []:
for actor in to_investigate:
to_investigated.remove(actA)
investigated.append(act)
for movie in actor_info[actor]:
for co_star in movie_info[movie]:
if co_star not in (investigated and to_investigate):
to_investigate.append(co_star)
....
....
return d
我想不出一个合适的方法来跟踪代码每次迭代中发现的距离。另外,代码在时间上似乎非常低效。