python - 实现具有最大深度并打印所有最短路径的 BFS 算法

Question

这是我想出的 BFS 算法，用于打印图中从根节点到任何其他节点的所有最短路径:

d = deque()
d.append(root)
level = 0
while len(d) >= 0 and level <= max_depth:
    u = d.popleft()
    print(adjacency_list[u])
    for v in adjacency_list[u]:
        if visited[v] == 'N':
            if nodes2distances[u] + 1 <= nodes2distances[v]:
                nodes2distances[v] = nodes2distances[u] + 1
                node2parents[v].append(u)
                d.extend(v)
    level += 1
    visited[u] = 'Y'

当我没有指定最大级别条件时，上面的代码工作正常，但是，每次我运行这个算法时，输出都会有所不同。

1) 你能解释一下我如何用级别限制(即指定最大级别)实现这个算法吗？

2)另外，请问我解决问题的方法是否可以更好？

编辑: 好的!!对不起，我之前没有这样做!! 假设我在未加权图中有以下边:

('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'),('D' , 'E'), ('D', 'F'), ('D', 'G'), ('E', 'F'), ('G', 'F')

在不受深度限制的情况下实现我的代码后，当我为节点 'B' 调用算法时，我得到以下输出，

[('A', ['B']), ('C', ['B']), ('D', ['B']), ('E', ['D']), ('F', ['D']), ('G', ['D'])]

但是，当我调用级别限制为 2 的同一函数时，即 myFunction(graph,'E',2)，我得到以下输出:

[('A', ['B']), ('C', ['B']), ('D', ['B'])]

然而，预期的输出是

[('A', ['B']), ('C', ['B']), ('D', ['B']),('E',['D']),('F', ['D']),('G',['D'])]

Answer 1

你在错误的地方增加了等级。每个节点的级别等于其父级别加 1。您不应在 while 循环中全局递增级别。相反，您应该存储放入队列中的每个节点的级别。像这样:

d = deque()
          #node,level
d.append( (root,0   ) )
while len(d) >= 0:
    front = d.popleft()
    u = front[0]
    level = front[1]
    if level >= max_depth:
        break
    print(adjacency_list[u])
    for v in adjacency_list[u]:
        if visited[v] == 'N':
            if nodes2distances[u] + 1 <= nodes2distances[v]:
                nodes2distances[v] = nodes2distances[u] + 1
                node2parents[v].append(u)
                d.append( (v,level+1) )
    visited[u] = 'Y'