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

- boralim

---

我会尝试使用 NetworkX 库。 - Math chiller

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

- fafl

---

谢谢分享你的代码 :) 它真的很有帮助。 - boralim