Breadth first Search Python Program Error : Key Error 3

Question

enter image description here I have written following python program to perform a BFS for the given graph, but after execution it gives the error : Key Error 3. What is wrong in my code?

output=[]
graph = {
            1:[2,3,4],
            2:[5,6],
            5:[9,10],
            4:[7,8],
            7:[11,12]
        }

def bfs(graph,root):
    queue = []
    visited=set()

    queue.append(root)
    visited.add(root)
    output.append(str(root))

    while not(queue==[]):
        for item in graph[root]:
            if item not in visited:
                queue.append(item)
                output.append(str(item))
                visited.add(item)
        root=queue.pop(0)

bfs(graph,1)
print(" ".join(output))

Wooble · Accepted Answer · 2014-04-04 11:54:14Z

2

You're adding nodes to your queue to search from that aren't in graph, and not checking they're in graph before trying to look them up. You can fix this by rewriting your while loop as:

while not(queue==[]):
    for item in graph[root]:
        if item not in visited:
            if item in graph:
                queue.append(item)
            output.append(str(item))
            visited.add(item)
    root=queue.pop(0)

(Alternatively, you could pre-populate graph with all of the unused keys from 1-12 with an empty list as the value.)

answered Apr 4, 2014 at 11:54

Wooble

90.5k12 gold badges111 silver badges132 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Breadth first Search Python Program Error : Key Error 3

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related