python - 使用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