Breadth-First Search (BFS)

Breadth First Search Traversal Problem Statement Given an undirected graph, return a list of all nodes traversed in breadth first order, starting from node 0. Input Specification The first line contains two integers, N and M, representing the number of nodes and the number of edges in the graph, respectively. N lines follow, each containing two integers u and v, denoting an undirected edge between node u and node v. Nodes are 0 indexed. Output Specification Output a single line containing space separated integers, representing the nodes in breadth first traversal order starting from node 0. Constraints 1 <= N <= 10^5 0 <= M <= 2 10^5 0 <= u, v < N Sample Test Case Input: Output: Explanation: Starting BFS from node 0: 1. Add 0 to the queue and mark visited. 2. Dequeue 0. Add 0 to BFS traversal. Neighbors of 0 are 1, 4. Enqueue 1, 4 and mark visited. 3. Dequeue 1. Add 1 to BFS traversal. Neighbors of 1 are 0, 2, 3. 0 is visited. Enqueue 2, 3 and mark visited. 4. Dequeue 4. Add 4 to BFS traversal. Neighbors of 4 is 0. 0 is visited. 5. Dequeue 2. Add 2 to BFS traversal. No unvisited neighbors. 6. Dequeue 3. Add 3 to BFS traversal. No unvisited neighbors. Queue becomes empty. The BFS traversal is 0 1 4 2 3.