Return to Revisions

The idea is to 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