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]