记录BFS算法中的所有直接前辈

Question

我的任务是在给定图形中执行BFS搜索后，打印出连接到当前顶点的所有前置。然而，我在代码中遇到了一个问题，在这个问题中，它只打印出最后一个探索的前置程序

pred = {}
level = {}

def bfs(G, S):
    kyu = deque([S])
    pred[S] = []
    level[S] = 0
    while len(kyu) > 0:
        curr = kyu.popleft()
        neighbors = G[curr]
        for neighbor in neighbors:
            if neighbor not in pred:
                pred[neighbor] = curr
                level[neighbor] = level[curr] + 1  # added
                kyu.append(neighbor)


def bfs_runner(G):
    components = 0
    for v in G:
        if v not in pred:
            components += 1
            bfs(G, v)
    return components

样本输入：

G = {
     'A': ['B'],
     'B': ['A', 'C', 'D'],
     'C': ['B', 'E'],
     'D': ['B', 'E'],
     'E': ['C', 'D']
}

所需输出：

pred = {
      'A': [],
      'B': ['A'],
      'C': ['B'],
      'D': ['B'],
      'E': ['C', 'D']
}

我的输出：

pred = {
      'A': [],
      'B': ['A'],
      'C': ['B'],
      'D': ['B'],
      'E': ['C']
}

Answer 1

您可以按如下方式修改代码：

from collections import defaultdict
pred = defaultdict (list)
level = defaultdict (lambda: 0)

def bfs(G, S):
    kyu = deque([S])
    while len(kyu) > 0:
        curr = kyu.popleft()
        neighbors = G[curr]
        for neighbor in neighbors:
            if neighbor not in pred:
                pred[neighbor].append(curr)
                level[neighbor] = level[curr] + 1  # added
                kyu.append(neighbor)

说明：您正在覆盖pred[neighbor]的值，而不是附加到它defaultdict(list)如果邻居尚未在pred中，则自动将pred[neighbor]初始化为空列表。同样地，对于级别

注意：从我的手机完成。没有测试

编辑：

完全重写：

from collections import deque, defaultdict
   
def get_predecessors(G, S):
    visited = set()
    predecessors = defaultdict(set)
    kyu = deque([S])
    while len(kyu) > 0:
        current_node = kyu.popleft()
        if current_node in visited:
            continue
        
        visited.add(current_node)
        nodes = G[current_node]
        for node in nodes:
            predecessors[node].add(current_node)
            if not node in visited:
                kyu.append(node)
                
    return predecessors

if __name__ == '__main__':
    
    G = {
         'A': ['B'],
         'B': ['A', 'C', 'D'],
         'C': ['B', 'E'],
         'D': ['B', 'E'],
         'E': ['C', 'D']
    }
    
    result = get_predecessors(G, 'A')
    print(dict(result))

输出：

{'B': {'A', 'C', 'D'},
 'A': {'B'},
 'C': {'B', 'E'},
 'D': {'B', 'E'},
 'E': {'C', 'D'}}