改进的广度优先搜索在图中找到最高分离度

Question

输入图：我有一个表示有向图的字典，其中键是一个节点，值是它所指向的节点。

输入英雄：所有节点的集合

该方法用于寻找所有节点组合之间的最大分离度。

def largestDegreeOfSeparation(graph, heroes):
    q = deque()
    currentHighestDoS = 0
    DoS = 0
    for hero in heroes:
        path = (hero,)
        q.append(path)
        visited = set([hero])
        while q:
            path = q.popleft()
            last_node = path[-1]
            for node in graph[last_node]:
                if node not in visited:
                    visited.add(node)
                    q.append(path + (node,))
        DoS = len(path) - 1
        if DoS > currentHighestDoS:
            currentHighestDoS = DoS
            currentHero = path[0]
            currentHerosDestination = last_node
            print str(currentHero) + '\t' + str(path) + '\t' + str(currentHighestDoS)

这个程序找到了一个分离度为4，然后是5，然后继续运行，我想是因为它花费了太长时间。有没有办法让这个方法运行得更快？

Answer 1

您可以使用每个英雄的位置创建一个numpy（np）数组，以与包含heros对象的另一个数组相同的顺序存储。假设你有英雄坐标：

 pos_heros   = np.array( [hero.coordinates for hero in heros], dtype='float64' )
 array_heros = np.array( [hero for hero in heros], dtype = object )

然后计算距离矩阵：

^{pr2}$

现在，您将通过获取对距离矩阵排序的索引来找到每个最近的Hero：

 a = np.argsort( dist, axis=1 )

您可以使用np.take来有效地获取排序的pos\u heros矩阵：

 matrix_heros = np.take( array_heros, a )

矩阵中的每一行都代表一个英雄，第一列是最接近的英雄，第二列是第二列，以此类推。。。在

例如，要让第一个和第二个英雄最接近第10列的英雄：

 matrix_heros[9,0]  # 9 > hero    0 >  first closest hero
 matrix_heros[9,1]  # 9 > hero    1 > second closest hero

要找到你想要的，最遥远的英雄是：

 ans = matrix_heros[:,-1]

ans将按照您创建的顺序包含最远的hero。在