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])

标签： pythonbreadth-first-search

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