我一直在尝试为流行的凯文培根游戏创建一个图形表示 . 我已经创建了图形和顶点类，但是在创建宽度第一搜索方法来遍历图形并找到从凯文培根到演员的最短路径时遇到了一些麻烦，并在路上打印出边缘 . 用户应该输入一个演员，程序应该找到从凯文培根到该演员的最短路径 . 然后用户将继续进入演员，并且将获取到该演员的最短路径，并打印出凯文培根数字，否则它将打印出来 .
有一个顶点和图表类 . 顶点类是一个字典，它包含它连接到的其他顶点和边 .
我正在使用的数据如下所示：
顶点：
[“凯文培根”，“演员1”，“演员2”，“演员3”，“演员4”，“演员5”，“演员6”]
边：
（“凯文培根”，“演员1”，“movie1”）
（“凯文培根”，“演员2”，“movie1”）
（“actor1”，“actor2”，“movie1”）
（“actor1”，“actor3”，“movie2”）
（“actor3”，“actor2”，“movie3”）
（“actor3”，“actor4”，“movie4”）
（“actor5”，“actor6”，“movie5”）
电影是边缘名称或权重，而元组的其他部分是顶点 . 我希望BFS算法打印出所有边缘和凯文培根数字，或打印出如果无法到达演员则不可能 .
这是迄今为止的代码 . 任何建议和帮助表示赞赏 .
感谢您的时间
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
1 回答
找个演员
检查演员是否是Kevin Bacon
如果演员是凯文培根，请沿着你走的路走回来
如果演员不是Kevin Bacon，那么找到所有与你没有检查过的演员相关的演员 .
将此演员所连接的所有演员添加到您的列表中以进行检查 .
您将遇到的最难的问题是记录您已经访问过的顶点 . 因此，我认为您的算法应该检查顶点列表 . 一些假设：
每个顶点仅列出一次 .
顶点仅为单向 . 这意味着如果你想从Actor 1转到Actor 2，从Actor 2转到Actor 1，你需要两个顶点，每个顶点一个 .
你有重量，但我不相信这一点 . 我会尝试实现它们 . 此外，您的默认权重不应为0，否则所有路径将同样短（0 * n = 0） .
好的，我们走吧 .
您还应该为顶点类实现__repr __（）方法 . 使用我使用的那个，输出看起来像这样：
我本来不打算用heapq来做这件事，但最终决定我不妨 . 基本上，您需要对选中的列表进行排序，以便首先获得最短路径 . 最简单的方法是在每次要从顶部弹出最小值时对列表进行排序，但是当列表变大时，这可能会非常慢 . Heapq可以以更有效的方式对列表进行排序，但是没有关键方法来获取我们添加的列表的最小值，因此我们需要使用元组来伪造它 . 元组中的第一个值是路径的实际成本，而第二个值只是"tie breaker"，因此我们不会尝试比较Vertexes（它们没有排序，如果我们尝试这样做会引发异常） .