Unable to search by breadth even when using a queue-CodePudding

I was trying to understand and implement breadth first search.

Using a Queue in this instance since Stack would have been for Depth first search.

But when I print out the result, it ends up being Depth first instead of Breadth.

What have I missed? Thanks.

from collections import deque

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


q = deque()
visited = {}
level = {}
parent = {}
result = []

for node in adj_list.keys():
    visited[node] = False
    parent[node] = None
    level[node] = float('-inf')

s = 'A'
visited[s] = True
level[s] = 0
q.append(s)

while q:
    u = q.pop()
    result.append(u)

    for v in adj_list[u]:
        if not visited[v]:
            visited[v] = True
            parent[v] = u
            level[v] = level[u]   1
            q.append(v)

print(result)

This prints:

['A', 'D', 'F', 'H', 'G', 'E', 'B', 'C']

This result is depth first.

For breadth first, it should have been:

['A', 'B', 'D', 'C', 'E', 'F', 'G', 'H']

CodePudding user response：

You are using the default pop() and append() functions, which operate on the same (right) end of the queue, which effectively makes it equivalent to a stack. What you might want to use is popleft() and append(), or pop() and appendleft(). You can find some examples listed here.

The shortest change to fix this in your program would be to replace

while q:
    u = q.pop()

with

while q:
    u = q.popleft()

CodePudding user response：

Use popleft() instead of pop() for the deque object. This is the point of using deque instead of list, for example. In your code as written a list would not have performance issues, but with popleft() the list would need to shuffle all remaining elements to the left by one which would be inefficient (though it would give the same result as using deque). The deque data type is designed to efficiently support this type of operation (popping from the left end of the collection).

from collections import deque

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


q = deque()
visited = {}
level = {}
parent = {}
result = []

for node in adj_list.keys():
    visited[node] = False
    parent[node] = None
    level[node] = float('-inf')

s = 'A'
visited[s] = True
level[s] = 0
q.append(s)

while q:
    u = q.popleft()
    result.append(u)

    for v in adj_list[u]:
        if not visited[v]:
            visited[v] = True
            parent[v] = u
            level[v] = level[u]   1
            q.append(v)

print(result)

Output:

['A', 'B', 'D', 'C', 'E', 'F', 'G', 'H']