BFS

Problem

Given a graph, perform BFS. Start from vertex 0, visit the vertices in the exact order as they appear in the graph, and ensure all vertices are visited.

Examples

  • [[2, 3, 1], [0], [0, 4], [0], [2]] Output [0, 2, 3, 1, 4]

  • [[1, 2], [0, 2], [0, 1, 3, 4], [2], [2]] Output [0, 1, 2, 3, 4]

Constraints

  • 1≤V≤105 (number of vertices)1 \le V \le 10^5 \ (\text{number of vertices})

  • 1≤E≤2×105 (number of edges)1 \le E \le 2 \times 10^5 \ (\text{number of edges})

  • 0≤v≤105 (vertex value)0 \le v \le 10^5 \ (\text{vertex value})

Expected Complexities

  • Time Complexity: O(V+E)\mathcal{O}(V + E)

  • Auxiliary Space: O(V)\mathcal{O}(V)

Solution

Python
from collections import deque


def bfs(adj):
    visited = [False] * len(adj)
    result = []

    for i in range(len(adj)):
        if not visited[i]:
            queue = deque()
            queue.append(i)
            visited[i] = True

            while queue:
                current = queue.popleft()
                result.append(current)

                for neighbor in adj[current]:
                    if not visited[neighbor]:
                        queue.append(neighbor)
                        visited[neighbor] = True

    return result


print(bfs([[2, 3, 1], [0], [0, 4], [0], [2]]))
print(bfs([[1, 2], [0, 2], [0, 1, 3, 4], [2], [2]]))