# Breadth First Search Python Implementation

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()

• 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. – RootTwo Jun 9 at 23:04