18
\$\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?

\$\endgroup\$
33
\$\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)
\$\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\$ – Andreas K. 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
7
\$\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
    
\$\endgroup\$

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