سوال ۶۲ کنکور ارشد علوم کامپیوتر ۱۴۰۳

Approach

Evaluate each statement against the standard BFS algorithm on an undirected connected graph represented with adjacency lists.

Key insight

BFS runs in $\Theta(V+E)$ time, and on an undirected graph stored as adjacency lists, every edge $\{u,w\}$ is stored in both $u$'s list and $w$'s list, so it is scanned once from each endpoint — exactly twice over the whole run.

Steps

• Option 1 — running time $O(n)$: False. BFS is $\Theta(V+E)$. For a connected graph $E$ ranges from $n-1$ (tree) up to $\binom{n}{2}=\Theta(n^2)$ (complete graph). So the time is $O(n+m)$, not $O(n)$ in general.
• Option 2 — each edge examined exactly twice: True. When BFS dequeues a vertex it iterates over its adjacency list. In an undirected graph each edge has two endpoints and thus appears in two adjacency lists, so it is examined once from each side — exactly twice. This is the textbook accounting that yields the $O(V+E)$ bound.
• Option 3 — vertices visited by smallest distance from $v$: Not the intended correct statement. While BFS does discover vertices in non-decreasing order of distance (level by level), the ordering within a level is arbitrary (determined by adjacency-list order), and the phrasing of "smallest distance" alone does not characterize the precise visiting order, so it is not the clean true statement chosen.
• Option 4 — bipartite ordering: False. BFS first visits $v$ itself (in $v$'s own part), then its neighbors in the opposite part, alternating parts level by level. It does not visit the opposite part entirely before the part containing $v$.

Sanity check

The handshake / two-endpoints argument is exactly what produces the $\sum_{u}\deg(u)=2|E|$ total work, confirming each undirected edge is touched twice and the total adjacency-list scanning is $O(E)$, giving overall $O(V+E)$.

Exam trick: Option 3 sounds true because BFS is the shortest-path (level-order) traversal, but its wording does not pin down the actual visiting order; the precise, unambiguous textbook fact is option 2 (each undirected edge scanned exactly twice), which is the property that underlies the $O(V+E)$ running time.