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

Question

我一直在尝试为流行的 kevin bacon 游戏创建图形表示。我已经创建了图和顶点 classes，但是在创建广度优先搜索方法来遍历图并找到从 Kevin Bacon 到演员的最短路径并在途中打印出边时遇到了一些麻烦。用户应该输入一个演员，程序应该找到从 kevin bacon 到那个演员的最短路径。然后用户将继续输入演员，将采用到该演员的最短路径，并打印出 kevin bacon 编号，否则将打印出 none.

有一个顶点和图class。顶点 class 是一个字典，其中包含它所连接的其他顶点和边。

我正在处理的数据如下所示：

顶点：

["Kevin Bacon", "actor1", "actor2", "actor3", "actor4", "actor5", "actor6"]

边：

("Kevin Bacon", "actor1", "movie1")

("Kevin Bacon", "actor2", "movie1")

("actor1", "actor2", "movie1")

("actor1", "actor3", "movie2")

("actor3", "actor2", "movie3")

("actor3", "actor4", "movie4")

("actor5", "actor6", "movie5")

其中电影是边名或权重，元组的其他部分是顶点。我希望 BFS 算法打印出所有的边和 kevin bacon 编号，或者打印出如果无法到达演员是不可能的。

这是目前为止的代码。感谢任何建议和帮助。

感谢您的宝贵时间

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

获取演员
检查演员是否是 Kevin Bacon
如果演员是 Kevin Bacon，请沿原路返回
如果该演员不是 Kevin Bacon，则查找您尚未检查过的与该演员有关的所有演员。
将与此演员有联系的所有演员添加到您的列表中进行检查。

你在这里遇到的最困难的问题是记录你已经访问过的顶点。因此，我认为您的算法应该检查顶点列表。一些假设：

每个顶点只列出一次。
顶点只有一个方向。这意味着如果您想从 Actor 1 到 Actor 2 以及从 Actor 2 到 Actor 1，您需要两个顶点，每个顶点一个。
你有权重，但我看不出它们与此有什么关系。不过，我会尝试实施它们。此外，您的默认权重不应为 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!")

您还应该为您的顶点 class 实现一个 __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 可以保持列表以更高效的方式排序，但是没有关键方法来获取我们添加的列表的最小值，因此我们需要使用元组来伪造它。元组中的第一个值是路径的实际成本，而第二个值只是一个 "tie breaker" 这样我们就不会尝试比较顶点（它们没有排序，如果我们尝试这样做会引发异常所以）。

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

Shortest Path Graph Traversal for Kevin Bacon Game

python

algorithm

graph-theory

shortest-path

breadth-first-search