Return to Answer

The answers that have been posted (including the accepted answer) are wrong because they don't 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
```

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

The answers that have been posted are wrong because they don't 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
```

The answers that have been posted (including the accepted answer) are wrong because they don't 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
```

The answers that have been posted don't 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 node should be completely explored before moving onto the next node (connected nodes 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
```

The answers that have been posted are wrong because they don't 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
```