Hello,

I have to implement Breadth First Search algorithm in Python.

The algorithm takes in a list of pairs where each pair is a node. We want to see the distance from one node to every other node. Consider the pairs of nodes that know each other. I converted the list of pairs to a dictionary where the key is the source node and the values is a list of nodes that the source node knows.

If I have a list

lst = [(0, 1), (0, 5), (2, 3), (2, 5), (3, 5), (4, 1), (4, 2)]

then

graph = {0: [1, 5],

1: [0, 4],

2: [3, 5, 4],

3: [2, 5],

4: [1, 2],

5: [0, 2, 3]}

The diagram will look something like this

Here is my code for Breadth First Search algorithm in Python

def bfs(graph, s):

visited = MyQueue()

visited.enqueue(s)

array = []

dist = 1

queue = MyQueue()

queue.enqueue(s)

visited.enqueue(s)

while not queue.emptyQueue():

s = queue.dequeue()

for i in graph[s]:

if i not in visited:

visited.enqueue(i)

queue.enqueue(i)

array.append({i : dist})

dist+=1

return array

print(array)

return array

print(bfs(graph, 3))

Where 3 is the starting node

queue is an object of MyQueue class that I created.

I get the following:

The key is the node that we are taking the distance of from the starting node and the value is the distance that the node is from the starting node.

The actual results should be:

I got the values for key 0 and key 1 wrong.

Please help me achieve this.

1 1. 46 47 class MyQueue: def __init__(self): self.items = [] 48 49 50 def __str__(self): return f"{self.items}" 51 52 53 def emptyQueue(self): return self.items == [] 54 55 56 def enqueue(self, item): return self.items.insert(0, item) 57 58 59 def dequeue(self): return self.items.pop() 60 61 62 def __iter__(self): return (x for x in self.items) 63 65 66 67 68 def bfs(graph, s): visited = MyQueue() visited.enqueue(s) array = [] dist = 1 queue = MyQueue() queue. enqueue(s) visited.enqueue(s) 69 70 71 72 73 74 75 76 77 78 while not queue.emptyqueue(): s = queue.dequeue() for i in graph[s]: if i not in visited: visited.enqueue(i) queue.enqueue(i) array.append({i : dist}) dist+=1 print(array) return array 79 80 81 82 83 127 128 129 lst = [(0, 1), (0, 5), (2, 3), (2, 5), (3, 5), (4, 1), (4, 2)] graph to_dict(lst) bfs(graph, 3) 130 [{2: 1}, {5: 1}, {4: 2}, {0: 3}, {1: 4}] [{2:1},{5:1},{4:2},{0:2},{1:3}]