CODEWITHSUNDEEP
algorithmdebugginggraphbreadth-first-search
nish
nish

Reputation: 7280

Unable to figure out the bug in BFS

I have written two versions of BFS, however one of them has a bug and doesn't lead to the correct result. I'm not able to figure out what the bug is though.

Correct version:

def find_all_distances(self, start_node):
    distance = {}
    marked = {}
    marked[start_node] = True
    distance[start_node] = 0
    queue = [start_node]
    while queue:
        node = queue.pop(0)
        for adj_node in self.adj[node]:
            if adj_node not in marked:
                marked[adj_node] = True
                distance[adj_node] = distance[node] + 6
                queue.append(adj_node)

Buggy version:

def find_all_distances(self, start_node):
    distance = {}
    marked = {}
    queue = [(start_node, 0)]
    while queue:
        node, dist = queue.pop(0)
        marked[node] = True
        distance[node] = dist
        for adj_node in self.adj[node]:
            if adj_node not in marked:
                queue.append((adj_node, dist + 6))

The only difference apparent to me is when we are marking a visited - before adding to queue or after popping from the queue. Why does that affect the results?

Upvotes: 1

Views: 70

Answers (2)

Martin Yang
Martin Yang

Reputation: 53

For a side note, pop(0) has O(n) complexity. It is not recommended to use a Python list as a queue. Use collections.deque instead.

Upvotes: 2

Yash Shah
Yash Shah

Reputation: 1654

Because the Buggy version leads to the visit of the similar nodes twice or more, Example :

enter image description here

Suppose you start at A:

Iteration 1:

Queue Q = [A]

marked = {}

Iteration 2:

Node Popped out: A

Queue Q = [B]

marked = {A:True}

Iteration 3:

Node Popped out: B

Queue Q = [C,D]

marked = {A:True,B:True}

Iteration 4:

Node Popped out: C

Queue = [D,D]

marked = {A:True,B:True,C:True}

Take a look at what happens on iteration 4, Node D visited twice... because you are marking nodes after popping out.

Upvotes: 2

Related Questions