最大深さを有する実装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'）、（ 'B'、 'C​​'）、（ 'B '、' D '、' D '、' D '、' F '、' D '、' G '、' E '、' F ' 」、 'B ' F' iのノードためのアルゴリズムを呼び出すときの深さの制限なしに私のコードを実行した後）

が、私は次の出力を得る' を、

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

しかし、ときに私レベル制限2の同じ関数、つまりを呼び出します、期待される出力が間違った場所で

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

Answer 1

あなたが増加しているレベルがある

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

に対し：、私は次の出力を取得します。各ノードのレベルは、その親レベルに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'