python - Kevin Bacon 游戏的最短路径图遍历

Question

我一直在尝试为流行的 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

Answer 1

1. 找 Actor
2. 检查 Actor 是不是凯文培根
3. 如果 Actor 是 Kevin Bacon，请沿着您走过的路返回
4. 如果该 Actor 不是 Kevin Bacon，则找到与该 Actor 有关联但您尚未检查的所有 Actor 。
5. 将与该 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 可以保持列表以更高效的方式排序，但是没有关键方法来获取我们添加的列表的最小值，因此我们需要使用元组来伪造它。元组中的第一个值是路径的实际成本，而第二个值只是一个“决胜局”，这样我们就不会尝试比较顶点(它们没有排序，如果我们尝试这样做会引发异常).