Record all the immediate predecessors in the BFS algorithm

user_14963049 0
Viewed 320

I'm tasked to print out all the predecessors that is connected to the current vertex after executing a BFS search in a given graph. However, I encountered a problem in my code in which it only prints out the last explored predecessor.

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

SAMPLE INPUT:

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

DESIRED OUTPUT:

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

MY OUTPUT:

pred = {
      'A': [],
      'B': ['A'],
      'C': ['B'],
      'D': ['B'],
      'E': ['C']
}
breadth-first-search python
1 Answers

You can modify your code as follows:

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)

Explanation: You were overwriting the value of pred[neighbor] instead of appending to it. defaultdict(list) automatically initializes pred[neighbor] to an empty list if neighbor is not yet in pred. Similarly for level.

Note: Done from my mobile. Did not test.

EDIT:

Complete rewrite:

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

Output:

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