181. BFS Traversal of a Graph

Given an undirected graph with n vertices (0-indexed) and m edges, and a starting vertex, print its breadth-first traversal order starting from that vertex, space-separated. When multiple unvisited neighbors are available, visit them in ascending order of vertex number. Only vertices reachable from the start should appear.

Input: The first line contains an integer n, the number of vertices. The second line contains an integer m, the number of edges. Each of the next m lines contains two space-separated integers u and v, an undirected edge. The final line contains the starting vertex. Output: Print the BFS traversal order starting from the given vertex, space-separated.

1 <= n <= 10^5

This is the foundational traversal underlying countless other graph problems in this category (shortest path in unweighted graphs, connected components, bipartite checking, and more) - mastering plain BFS here pays off broadly.

Visit every reachable vertex of a graph level by level, starting from a given vertex. Brute force: There isn't a meaningfully different 'slower' approach - a queue-based BFS IS the standard, direct way to achieve level-by-level graph traversal. Optimised: Marking a vertex visited AT ENQUEUE TIME (not dequeue time) is the crucial detail that prevents the same vertex from being added to the queue multiple times by different neighbors reaching it - without this, the queue could grow unnecessarily and even revisit vertices.

Represent the graph as an n x n adjacency matrix (matrix[u][v] = true if an edge exists). Run standard BFS from the start vertex using a queue and a visited array, but whenever a vertex is dequeued, find its neighbors by scanning the entire matrix row for that vertex left to right (which conveniently visits them in ascending order automatically). This is correct and simple, but building and scanning an O(n^2)-sized matrix is very wasteful when the graph is sparse, especially at n up to 10^5. Time: O(n^2) Space: O(n^2)

Build an adjacency list from the m edges (for each undirected edge, append each endpoint to the other's neighbor list), which takes only O(n+m) space instead of O(n^2). Since neighbors are appended in arbitrary edge-input order, sort each vertex's neighbor list once before running BFS so that dequeuing a vertex and iterating its (now-sorted) list visits unvisited neighbors in ascending order, exactly as required. This is a large space improvement over the matrix, at the cost of a sorting pass. Time: O((n + m) log m) Space: O(n + m)

Build the same adjacency list, but insert each vertex's neighbors already in ascending order without a comparison-based sort: since vertex labels are bounded integers 0..n-1, use a counting/bucket approach - first count each vertex's degree, then place its neighbors directly into a pre-allocated, correctly-ordered segment of a flat array (or perform a single linear-time bucket sort per adjacency list). Standard BFS with a queue and visited array then runs over this structure. This removes the log factor from sorting entirely by exploiting the bounded-integer vertex labels, giving a truly linear-time construction and traversal. Time: O(n + m) Space: O(n + m)

1. Use a queue, starting with just the source vertex, marked visited immediately. 2. Repeatedly dequeue a vertex, visit (print) it, and enqueue all its UNVISITED neighbors in ascending order. 3. Mark a neighbor visited the MOMENT it's enqueued (not when dequeued), to avoid enqueuing the same vertex twice.

Time: O(n + m) - every vertex is enqueued/dequeued once, and every edge is examined once (from each of its endpoints). Space: O(n), for the queue and the visited-tracking structure.

a start vertex with no edges, vertices unreachable from the start that must be excluded from output, and n at its upper bound of 10^5 to confirm the traversal runs efficiently.

Be ready to state precisely WHY marking visited at enqueue time (not dequeue time) matters - this is a very common subtle bug, especially in graphs where multiple vertices can share a common unvisited neighbor.