我一直在尝试为流行的 kevin bacon 游戏创建图形表示。我已经创建了图形和顶点类，但在创建广度优先搜索方法来遍历图形并找到从 Kevin Bacon 到 Actor 的最短路径并在途中打印出边时遇到了一些麻烦。 用户应该输入一个 Actor ，程序应该找到从 kevin bacon 到那个 Actor 的最短路径。然后用户将继续输入 Actor ，将采用到该 Actor 的最短路径，并打印出 kevin bacon 编号，否则将打印出 none。
有一个顶点和图形类。顶点类是一个字典，其中包含它所连接的其他顶点和边。
我正在处理的数据如下所示:
顶点:
[“凯文培根”、“ Actor 1”、“ Actor 2”、“ Actor 3”、“ Actor 4”、“ Actor 5”、“ Actor 6”]
边缘:
("凯文培根", "actor1", "movie1")
("凯文培根", "actor2", "movie1")
(" Actor 1", " Actor 2", "电影 1")
(" Actor 1", " Actor 3", "电影 2")
(" Actor 3", " Actor 2", "电影3")
(" Actor 3", " Actor 4", "电影4")
(" Actor 5", " Actor 6", "电影5")
其中 movie 是边名称或权重，元组的其他部分是顶点。我希望 BFS 算法打印出所有边和 kevin bacon 编号，或者打印出如果无法到达 Actor 则不可能。
这是到目前为止的代码。感谢您提供任何建议和帮助。
谢谢你的时间
class Vertex:
'''
keep track of the vertices to which it is connected, and the weight of each edge
'''
def __init__(self, key):
'''
'''
self.ID = key
self.connected_to = {}
def add_neighbor(self, neighbor, weight=0):
'''
add a connection from this vertex to anothe
'''
self.connected_to[neighbor] = weight
def __str__(self):
'''
returns all of the vertices in the adjacency list, as represented by the connectedTo instance variable
'''
return str(self.ID) + ' connected to: ' + str([x.ID for x in self.connected_to])
def get_connections(self):
'''
returns all of the connections for each of the keys
'''
return self.connected_to.keys()
def get_ID(self):
'''
returns the current key id
'''
return self.ID
def get_weight(self, neighbor):
'''
returns the weight of the edge from this vertex to the vertex passed as a parameter
'''
return self.connected_to[neighbor]
class Graph:
'''
contains a dictionary that maps vertex names to vertex objects.
'''
def __init__(self):
'''
'''
self.vert_list = {}
self.num_vertices = 0
def __str__(self):
'''
'''
edges = ""
for vert in self.vert_list.values():
for vert2 in vert.get_connections():
edges += "(%s, %s)\n" %(vert.get_ID(), vert2.get_ID())
return edges
def add_vertex(self, key):
'''
adding vertices to a graph
'''
self.num_vertices = self.num_vertices + 1
new_vertex = Vertex(key)
self.vert_list[key] = new_vertex
return new_vertex
def get_vertex(self, n):
'''
'''
if n in self.vert_list:
return self.vert_list[n]
else:
return None
def __contains__(self, n):
'''
in operator
'''
return n in self.vert_list
def add_edge(self, f, t, cost=0):
'''
connecting one vertex to another
'''
if f not in self.vert_list:
nv = self.add_vertex(f)
if t not in self.vert_list:
nv = self.add_vertex(t)
self.vert_list[f].add_neighbor(self.vert_list[t], cost)
def get_vertices(self):
'''
returns the names of all of the vertices in the graph
'''
return self.vert_list.keys()
def __iter__(self):
'''
for functionality
'''
return iter(self.vert_list.values())
def bfs(self):
'''
Needs to be implemented
'''
pass
最佳答案
- 找 Actor
- 检查 Actor 是不是凯文培根
- 如果 Actor 是 Kevin Bacon，请沿着您走过的路返回
- 如果该 Actor 不是 Kevin Bacon，则找到与该 Actor 有关联但您尚未检查的所有 Actor 。
- 将与该 Actor 有联系的所有 Actor 添加到您的列表中以进行检查。
您在这里遇到的最困难的问题是记录您已经访问过的顶点。因此，我认为您的算法应该检查顶点列表。一些假设:
- 每个顶点只列出一次。
- 顶点只有一个方向。这意味着，如果您想从 Actor 1 转到 Actor 2，然后从 Actor 2 转到 Actor 1，则需要两个顶点，每个顶点基本上对应一个 Actor。
- 您有权重，但我看不出它们与此有什么关系。不过，我会尝试实现它们。此外，您的默认权重不应为 0，否则所有路径都将同样短 (0*n = 0)。
好的，我们走。
def bfs(self, actor):
from heapq import heappush, heappop
if actor == "Kevin Bacon":
return print("This actor is Kevin Bacon!")
visited = set()
checked = []
n = 0
heappush(checked, (0, n, [self.get_vertex(actor)]))
# if the list is empty we haven't been able to find any path
while checked:
# note that we pop our current list out of the list of checked lists,
# if all of the children of this list have been visited it won't be
# added again
current_list = heappop(checked)[2]
current_vertex = current_list[-1]
if current_vertex.ID == "Kevin Bacon":
return print(current_list)
for child in current_vertex.get_connections():
if child in visited:
# we've already found a shorter path to this actor
# don't add this path into the list
continue
n += 1
# make a hash function for the vertexes, probably just
# the hash of the ID is enough, ptherwise the memory address
# is used and identical vertices can be visited multiple times
visited.add(child)
w = sum(current_list[i].get_weight(current_list[i+1])
for i in range(len(current_list)-1))
heappush(checked, (w, n, current_list + [child]))
print("no path found!")
您还应该为您的顶点类实现一个 __repr__() 方法。使用我使用的那个，输出如下所示:
g = Graph()
for t in [("Kevin Bacon", "actor1", "movie1")
,("Kevin Bacon", "actor2", "movie1")
,("actor1", "actor2", "movie1")
,("actor1", "actor3", "movie2")
,("actor3", "actor2", "movie3")
,("actor3", "actor4", "movie4")
,("actor5", "actor6", "movie5")]:
g.add_edge(t[0],t[1],cost=1)
g.add_edge(t[1],t[0],cost=1)
g.bfs("actor4")
# prints [Vertex(actor4), Vertex(actor3), Vertex(actor2), Vertex(Kevin Bacon)]
我原本不打算使用 heapq这样做，但最后决定我也可以。本质上，您需要对检查列表进行排序以首先获得最短路径。最简单的方法是每次要从顶部弹出最小值时对列表进行排序，但是当列表变大时，这会变得非常慢。 Heapq 可以保持列表以更高效的方式排序，但是没有关键方法来获取我们添加的列表的最小值，因此我们需要使用元组来伪造它。元组中的第一个值是路径的实际成本，而第二个值只是一个“决胜局”，这样我们就不会尝试比较顶点(它们没有排序，如果我们尝试这样做会引发异常).
关于python - Kevin Bacon 游戏的最短路径图遍历，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47586428/