Skip to content
Advertisement

BFS algorithm in Python

graph={ 0:[1,3,4], 1:[0,2,4], 2:[1,6], 3:[0,4,6], 4:[0,1,3,5], 5:[4], 6:[2,3] }

def bfs(graph, start, path=[]):
    queue = [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in path:
            path.append(vertex)
            queue.extend(graph[vertex] - path)
    return path

print bfs(graph, 0)

Guys! Can someone help me with this bfs code? I can’t understand how to solve this queue line.

Advertisement

Answer

To extend your queue with all nodes not yet seen on the path, use set operations:

queue.extend(set(graph[vertex]).difference(path))

or use a generator expression:

queue.extend(node for node in graph[vertex] if node not in path)

Lists don’t support subtraction.

You don’t really need to filter the nodes, however, your code would work with a simple:

queue.extend(graph[vertex])

as the if vertex not in path: test also guards against re-visiting nodes.

You should not use a list as default argument, see “Least Astonishment” and the Mutable Default Argument; you don’t need a default argument here at all:

def bfs(graph, start):
    path = []

Demo:

>>> graph={ 0:[1,3,4], 1:[0,2,4], 2:[1,6], 3:[0,4,6], 4:[0,1,3,5], 5:[4], 6:[2,3] }
>>> def bfs(graph, start):
...     path = []
...     queue = [start]
...     while queue:
...         vertex = queue.pop(0)
...         if vertex not in path:
...             path.append(vertex)
...             queue.extend(graph[vertex])
...     return path
... 
>>> print bfs(graph, 0)
[0, 1, 3, 4, 2, 6, 5]
Advertisement