3
\$\begingroup\$

I have the below implementation of the BFS algorithm, in which I've used OrderedDict instead of a list or set. ( I've used OrderedDict in DFS to preserve the order of visited vertices ). Is this an efficient implementation of BFS and any other suggestions for improvements?

(Note: My use case is a sparse graph, i.e., the input will always be an adjacency list)

import collections

def bfs_iterative(graph, vertex):
    visited = collections.OrderedDict()
    queue = collections.deque([vertex])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited[vertex] = True
            queue.extend(graph[vertex])
    return list(visited.keys())

def main():
    test_graph1 = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }

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

    print(bfs_iterative(test_graph1, 'A'))    # output: ['A', 'B', 'C', 'D', 'E', 'F']
    print(bfs_iterative(test_graph2, 1))      # output: [1, 2, 4, 5, 3, 6, 7]

if __name__ == '__main__':
    main()
\$\endgroup\$
  • 3
    \$\begingroup\$ As of Python 3.7, the built in dict class preserves insertion order (see last paragraph in the docs). So a regular dict will work and the OrderedDict isn't needed. \$\endgroup\$ – RootTwo Jun 9 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.