1

我有一个表示有向图的字典。例如...

myDict = {'foo': ['hello', 'stack'], 'bar' : ['over', 'flow']}

这意味着'foo'节点指向'hello'和'stack'而'bar'节点指向'over'和'flow'。

我还编写了用于执行广度优先搜索以找到任何两个节点之间的最短路径的代码......

from collections import deque

def breadthFirstSearch(graph, start, end):
    q = deque()
    path = (start, )
    q.append(path)
    visited = set([start])
    while q:
        path = q.popleft()
        last_node = path[-1]
        if last_node == end:
            return path
        for node in graph[last_node]:
            if node not in visited:
                visited.add(node)
                q.append(path + (node,))
    print 'There is no path from ' + start + ' to ' + end + '.'
    return None

我的问题是：是否可以修改此广度优先搜索，以便为我提供最大的最短路径以及该路径的起始节点和结束节点？

4

1 回答 1

1

您的问题称为“图形直径问题”。

广度优先搜索创建一个广度优先搜索树。由于存在非树边，两个节点之间的最长树路径通常比它们之间的最长路径要长。所以不，你不能让 BFS 直接这样做。

BFS 将把它钉在树上，但它有点不平凡。

有一种称为“词典广度优先搜索”的变体，可以找到某些受限类图的直径。我在 LBFS 工作的地方遇到的那些图形类看起来很像树。

编辑：当然，您可以从每个节点开始运行一次 BFS，并找出 BFS 报告的最长路径。或者您可以使用极其优雅的Floyd-Warshall 算法。

于 2013-05-26T02:03:16.690 回答