15
\$\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\$
28
\$\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\$ – Mathias Ettinger 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\$ – AndyK Oct 2 '18 at 8:39
  • \$\begingroup\$ I'm still grocking this, but it doesn't return anything right? \$\endgroup\$ – Scott Skiles May 17 at 2:07
6
\$\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\$

protected by Jamal Oct 3 '18 at 1:00

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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