BFS of graph

Given a connected undirected graph containing V vertices, represented by a 2-d adjacency list adj[][], where each adj[i] represents the list of vertices connected to vertex i. Perform a Breadth First Search (BFS) traversal starting from vertex 0, visiting vertices from left to right according to the given adjacency list, and return a list containing the BFS traversal of the graph.

Note: Do traverse in the same order as they are in the given adjacency list.

Examples:

Input: adj[][] = [[2, 3, 1], [0], [0, 4], [0], [2]]

Output: [0, 2, 3, 1, 4]
Explanation: Starting from 0, the BFS traversal will follow these steps: 
Visit 0 → Output: 0 
Visit 2 (first neighbor of 0) → Output: 0, 2 
Visit 3 (next neighbor of 0) → Output: 0, 2, 3 
Visit 1 (next neighbor of 0) → Output: 0, 2, 3, 
Visit 4 (neighbor of 2) → Final Output: 0, 2, 3, 1, 4

Input: adj[][] = [[1, 2], [0, 2], [0, 1, 3, 4], [2], [2]]

Output: [0, 1, 2, 3, 4]
Explanation: Starting from 0, the BFS traversal proceeds as follows: 
Visit 0 → Output: 0 
Visit 1 (the first neighbor of 0) → Output: 0, 1 
Visit 2 (the next neighbor of 0) → Output: 0, 1, 2 
Visit 3 (the first neighbor of 2 that hasn't been visited yet) → Output: 0, 1, 2, 3 
Visit 4 (the next neighbor of 2) → Final Output: 0, 1, 2, 3, 4

Constraints:
1 ≤ V = adj.size() ≤ 10⁴
1 ≤ adj[i][j] ≤ 10⁴

Approach 01:

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    vector<int> bfs(vector<vector<int>>& adjacencyList) {
        int numNodes = adjacencyList.size();
        vector<int> traversalOrder;
        vector<int> visited(numNodes, 0);
        queue<int> bfsQueue;

        bfsQueue.push(0);
        visited[0] = 1;

        while (!bfsQueue.empty()) {
            int currentNode = bfsQueue.front();
            bfsQueue.pop();
            traversalOrder.push_back(currentNode);

            for (int neighbor : adjacencyList[currentNode]) {
                if (!visited[neighbor]) {
                    bfsQueue.push(neighbor);
                    visited[neighbor] = 1;
                }
            }
        }

        return traversalOrder;
    }
};

from collections import deque
from typing import List

class Solution:
    def bfs(self, adjacencyList: List[List[int]]) -> List[int]:
        numNodes = len(adjacencyList)
        traversalOrder = []
        visited = [0] * numNodes
        bfsQueue = deque()

        bfsQueue.append(0)
        visited[0] = 1

        while bfsQueue:
            currentNode = bfsQueue.popleft()
            traversalOrder.append(currentNode)

            for neighbor in adjacencyList[currentNode]:
                if not visited[neighbor]:
                    bfsQueue.append(neighbor)
                    visited[neighbor] = 1

        return traversalOrder

Time Complexity:

• Visiting Each Node:

  Each node in the graph is visited once, contributing \( O(N) \), where \( N \) is the number of nodes.

• Processing Each Edge:

  Each edge is processed once when exploring neighbors, contributing \( O(E) \), where \( E \) is the number of edges.

• Total Time Complexity:

  The overall time complexity is \( O(N + E) \).

Space Complexity:

• Visited Array:

  A boolean array of size \( N \) is used to track visited nodes, taking \( O(N) \) space.

• Queue Storage:

  In the worst case, all nodes might be stored in the queue simultaneously, requiring \( O(N) \) space.

• Traversal Order Storage:

  The result array stores all nodes in the traversal order, requiring \( O(N) \) space.

• Total Space Complexity:

  The overall space complexity is \( O(N) \).