21
\$\begingroup\$
def bfs(graph, root):
    visited, queue = [], [root]
    while queue:
        vertex = queue.pop(0)
        for w in graph[vertex]:
            if w not in visited:
                visited.append(w)
                queue.append(w)

graph = {0: [1, 2], 1: [2], 2: []}
bfs(graph, 0)

Does this look like a correct implementation of BFS in Python 3?

| improve this question | | | | |
\$\endgroup\$
35
\$\begingroup\$
  • sets perform containing checks (w in visited) \$O(1)\$ rather than \$O(n)\$ for lists.
  • collections.deque are better than lists for poping elements at the front (popleft).
  • you should put your example code under an if __name__ == '__main__' clause.
  • w as a variable name does not convey meaning, you should try to come up with something more explicit.
import collections


def breadth_first_search(graph, root): 
    visited, queue = set(), collections.deque([root])
    while queue: 
        vertex = queue.popleft()
        for neighbour in graph[vertex]: 
            if neighbour not in visited: 
                visited.add(neighbour) 
                queue.append(neighbour) 


if __name__ == '__main__':
    graph = {0: [1, 2], 1: [2], 2: []} 
    breadth_first_search(graph, 0)

Given a growing number of comments indicating that the code does not return anything, I’d like to add that, yes, this code does not process nodes: it only traverse the graph and you're likely to want to add your own custom logic to process each node. As your mileage may vary (building a traversal list, finding the first node that satisfies a condition, etc.), there is not a "one code fits all" approach, but a useful first approximation would be to yield each node as they are traversed:

import collections


def breadth_first_search(graph, root): 
    visited, queue = set(), collections.deque([root])
    while queue: 
        vertex = queue.popleft()
        yield vertex
        visited.add(vertex)
        queue.extend(n for n in graph[vertex] if n not in visited)


if __name__ == '__main__':
    graph = {1: [2, 4, 5], 2: [3, 6, 7], 3: [], 4: [], 5: [], 6: [], 7: []}
    list(breadth_first_search(graph, 1))  # [1, 2, 4, 5, 3, 6, 7]

Note that this alternative iteration also takes care of the bug mentioned in this answer

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ But the code is poping elements from the right? \$\endgroup\$ – Christofer Ohlsson Aug 2 '18 at 14:44
  • 1
    \$\begingroup\$ @ChristoferOhlsson Which code? OP uses list.pop(0) which pop from the left and mine uses deque.popleft() which, well, also pop from the left. \$\endgroup\$ – 301_Moved_Permanently Aug 2 '18 at 14:48
  • 1
    \$\begingroup\$ I'm sorry, I must be blind. For some reason, I didn't realize OP used 0 as an argument. \$\endgroup\$ – Christofer Ohlsson Aug 2 '18 at 14:51
  • 1
    \$\begingroup\$ You forgot to 'return visited' \$\endgroup\$ – X Æ A-12 Oct 2 '18 at 8:39
  • \$\begingroup\$ I'm still grocking this, but it doesn't return anything right? \$\endgroup\$ – Scott Skiles May 17 '19 at 2:07
8
\$\begingroup\$

I agree with Mathias Ettinger's use of sets and deques, with two changes:

  • name the set seen instead of visited, because your algorithm adds to set before visiting.
  • add the root to seen before entering while loop. Otherwise the root may be revisited (eg test case below where 1 points back to 0).

    import collections
    
    def bfs(graph, root):
        seen, queue = set([root]), collections.deque([root])
        while queue:
            vertex = queue.popleft()
            visit(vertex)
            for node in graph[vertex]:
                if node not in seen:
                    seen.add(node)
                    queue.append(node)
    
    def visit(n):
        print(n)
    
    if __name__ == '__main__':
        graph = {0: [1, 2], 1: [2, 0], 2: []} 
        bfs(graph, 0)
    

    Outputs:

    0
    1
    2
    
| improve this answer | | | | |
\$\endgroup\$
1
\$\begingroup\$

The answers that have been posted (including the accepted answer) are wrong because they don't explore the vertex completely before moving onto the next vertex. For the below adjacency matrix

test_graph = {
    1: [2, 4, 5],
    2: [3, 6, 7],
    3: [],
    4: [],
    5: [],
    6: [],
    7: []
}

The output should be 1, 2, 4, 5, 7, 6, 3, or 1, 5, 4, 2, 3, 6, 7, etc. The idea is that the current vertex should be completely explored before moving onto the next vertex. In addition, connected vertices can occur in any order.

Below code provides the correct sequence

import collections

def bfs(graph, start_vertex):
    visited = set()
    traversal = []
    queue = collections.deque([start_vertex])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            traversal.append(vertex)
            queue.extend(reversed(graph[vertex]))   # add vertex in the same order as visited
    return traversal
```
| improve this answer | | | | |
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.