Application lab in Graph Representations and Traversal

Mission

Traverse the source component in ascending-neighbor BFS order.

Learning outcome: Apply breadth-first traversal

Correctness contract

Invariant: A vertex is marked when discovered so every reachable vertex is processed once.

Required technique: Build undirected adjacency lists, sort neighbors, and mark each vertex when it is enqueued.

Complexity target: time O(V + E log V) including neighbor sorting; space O(V+E).

Input and output

Input: V and E, then E undirected vertex pairs, then the source vertex. Whitespace may be spaces or line breaks.

Output: Print the requested sequence on one line with single spaces and no trailing space. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• V is positive and every vertex index is in the range 0 through V - 1.
• The declared edge count exactly matches the supplied pairs.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Build undirected adjacency lists, sort neighbors, and mark each vertex when it is enqueued.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

5 4 0 1 0 2 1 3 2 4 0

Sample output

0 1 2 3 4

Why the sample works: Visible walkthrough for the ordinary non-trivial path. A vertex is marked when enqueued, so sorted adjacency rows produce one deterministic discovery order. Input `5 4 0 1 0 2 1 3 2 4 0` therefore produces `0 1 2 3 4`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Mark or assign distance at enqueue time, not at dequeue time.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.