BFS algorithm in Python

Question

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.

What do you mean by "solve?" What is the solution supposed to be? Also, be careful with making a default argument be `[]` in Python. See [this article](http://www.deadlybloodyserious.com/2008/05/default-argument-blunders/). — 2rs2ts, May 05 '14 at 17:09
I think by "solve this queue line", he means, diagnose the error that occurs on the line beginning with `queue.extend`. Namely, `TypeError: unsupported operand type(s) for -: 'list' and 'list'` — Kevin, May 05 '14 at 17:13
Incidentally, OP, watch out for that `path=[]` in your function definition - you may get surprising results if you run this function more than once. See [this](http://stackoverflow.com/questions/1132941/least-astonishment-in-python-which-scope-is-the-mutable-default-argument-in) question on default mutable arguments. — Kevin, May 05 '14 at 17:15

score 1 · Answer 1 · answered May 05 '14 at 17:22

1

queue.extend(graph[vertex] - path)

This line is giving TypeError: unsupported operand type(s) for -: 'list' and 'list', because you are not allowed to subtract two lists. You could convert them to a different collection that does support differences. For example:

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(set(graph[vertex]) - set(path))
    return path

print bfs(graph, 0)

Result:

[0, 1, 3, 4, 2, 6, 5]

By the way, it may be good to modify the argument list so that you don't have a mutable list as a default:

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

answered May 05 '14 at 17:22

Kevin

74,910
12
133
166

You don't need to convert both to a set (`set.difference()` takes any iterable) and `list.extend()` takes any iterable as well, so the `list()` call is redundant too. – Martijn Pieters May 05 '14 at 17:23
Good observation on the unnecessary `list` call. Edited. However, it looks like both `set` conversions are necessary if one wants to use the minus operator. Although, an explicit `difference` call could take a list, as you say. – Kevin May 05 '14 at 17:24
just need queue.extend(graph[vertex]) here also. – Padraic Cunningham May 05 '14 at 17:33
`queue.extend(set(graph[vertex]) - set(path) - set(queue))` in order to avoid to add to the queue, more than once, a node which has not been visited yet. – gaetano Aug 15 '18 at 20:56

score 1 · Accepted Answer · edited May 23 '17 at 11:45

1

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]

edited May 23 '17 at 11:45

Community

1
1

answered May 05 '14 at 17:22

Martijn Pieters

1,048,767
296
4,058
3,343

using queue.extend(graph[vertex]) gets the same result. – Padraic Cunningham May 05 '14 at 17:27
@PadraicCunningham: sure; as the `vertex not in path` test also filters. Good point. – Martijn Pieters May 05 '14 at 17:28
The `if vertex not in path:` check is expensive... can this be made more efficient? I understand path has to contain order. Perhaps, a second set can be used to just test for membership. – cs95 Dec 08 '17 at 19:56
@cᴏʟᴅsᴘᴇᴇᴅ: I've experimented in the past with this; unless your paths are very long it is usually not worth the effort. – Martijn Pieters Dec 08 '17 at 20:50

score 0 · Answer 3 · answered Jun 01 '15 at 05:14

Bug is that there is no list difference method. Either you can convert it to set and use set difference method or you can use list comprehension as

queue.extend(graph[vertex] - path)

can be replaced by

queue += [i for i in graph[vertex] if i not in path].

score 0 · Answer 4 · answered Dec 27 '20 at 15:29

 #USE BELOW CODE FOR SIMPLE UNDERSTANDING

    

  
graph = {
    'A' : ['B' , 'C','D'],
    'B' : ['E'],
    'C' : ['F'],
    'D' : ['G'],
    'E' : [],
    'F' : ['Z'],
    'G' : [],
    'Z' : [],
}


visited = [] #Store visted nodes
queue = [] #BFS uses queue structure so this varible will work like QUEUE ( LIFO)
final_result = [] 

def bfs(visited,graph,node):
    visited.append(node)
    queue.append(node)
    
    while queue:
        s = queue.pop(0)
        print(s,end=" ")
        #final_result.append(s)
        
        for neighbour in graph[s]:
            if neighbour not in visited:
                visited.append(neighbour)
                queue.append(neighbour)
    

    bfs(visited,graph,'A')
    print(final_result)

BFS algorithm in Python

4 Answers4

Linked