两节点之间的距离，使用Python的广度优先搜索算法，两节点之间的距离。

Question

如何使用BFS算法只得到图中任意两个节点之间的距离（边数）？

我不想把路径信息保存为一个列表（像下面的代码）以减少代码的运行时间。(为了提高性能)

def check_distance(self, satrt, end, max_distance):
    queue = deque([start])
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == end:
            return len(path)
        elif len(path) > max_distance:
            return False
        else:
            for adjacent in self.graph.get(node, []):
                queue.append(list(path) + [adjacent])

Answer 1

你可以通过两个改变来提高性能。

• 就像你说的，用距离代替路径。这样可以节省内存，当距离很大的时候更是如此。
• 保持一组已经看到的节点。这将大大减少可能的路径数量，特别是当每个节点有多条边时。如果你不这样做，那么算法就会在节点之间绕圈和来回走动。

我会尝试这样的做法。

from collections import deque

class Foo:

    def __init__(self, graph):
        self.graph = graph

    def check_distance(self, start, end, max_distance):
        queue = deque([(start, 0)])
        seen = set()
        while queue:
            node, distance = queue.popleft()
            if node in seen or max_distance < distance:
                continue
            seen.add(node)
            if node == end:
                return distance
            for adjacent in self.graph.get(node, []):
                queue.append((adjacent, distance + 1))

graph = {}
graph[1] = [2, 3]
graph[2] = [4]
graph[4] = [5]
foo = Foo(graph)
assert foo.check_distance(1, 2, 10) == 1
assert foo.check_distance(1, 3, 10) == 1
assert foo.check_distance(1, 4, 10) == 2
assert foo.check_distance(1, 5, 10) == 3
assert foo.check_distance(2, 2, 10) == 0
assert foo.check_distance(2, 1, 10) == None
assert foo.check_distance(2, 4, 10) == 1