Question bank — BFS — algorithm, queue-based, O(V+E), shortest path in unweighted graphs

True — the queue holds at most two consecutive levels $k$ and $k+1$ with level-$k$ ahead, so dequeues come out sorted by distance, which is the whole reason first arrival is shortest.

False — a stack makes it dive deep (that becomes DFS); first arrival is no longer guaranteed to be via the fewest edges.

True — each node stores the parent that first discovered it at distance $d(u)+1$, so walking parents to the root gives one valid fewest-edge path.

False — it gives one shortest path; if two equal-length routes exist, BFS keeps only whichever neighbor discovered the node first, ignoring the tie.

True — if every edge has the same positive weight, fewest edges equals least total weight, so BFS's edge-count minimization coincides with true cost (just multiply distances by 5).

False — BFS counts edges, so a two-edge path of weight $1+1=2$ can beat a one-edge path of weight $2$ in true cost, but BFS would prefer the single edge; use Dijkstra or 0-1 BFS for such tricks.

False — edge scans across all vertices sum to ${\sum }_v\mathrm{deg}(v)=2E$ (undirected), and vertices are handled once, so the two loops add to $O(V+E)$, not multiply.

False — BFS only reaches nodes in the source's connected component; unreached nodes keep distance "infinity" and must be found by restarting BFS from each unvisited node.

True — BFS respects edge direction (it scans adj[u] = out-neighbors), so the count is of directed hops; the reverse direction may be unreachable, which is expected.

Mostly true on distances but risky — the same node can sit in the queue several times, and if you (correctly) skip already-processed pops you get right answers but $O(E)$ queue bloat; the safe convention is mark-at-enqueue.

The same unvisited node can be pushed by several neighbors before it is ever popped, so the queue can hold up to $O(E)$ duplicates, breaking the "each vertex enqueued once" guarantee — mark visited the instant you push.

BFS minimizes the number of edges, not the summed weight; on a weighted map fewer roads can cost more, so this needs Dijkstra (non-negative weights) instead.

Re-enqueueing an already-visited node in a cyclic graph can loop forever and may overwrite a correct smaller distance with a larger one; only enqueue unvisited neighbors.

The distance must be fixed at discovery (enqueue) time from the node that first found w; setting it at dequeue from a random current node has no meaning — w was already given its correct distance when pushed.

An undirected edge must appear in both adjacency lists (v in adj[u] and u in adj[v]); otherwise BFS from v can never traverse back to u and distances break.

list.pop() removes the last element (LIFO), turning your BFS into a DFS-like traversal; you need popleft() (a collections.deque) to preserve FIFO order.

The source can then be re-discovered by a neighbor and re-enqueued, causing an extra pass; always mark the source visited (and give it dist = 0) before the main loop starts.

Distance to itself is 0 by definition and marking it up front stops a neighbor from re-discovering and re-queueing it, keeping the "each vertex once" invariant intact.

An adjacency list lets you visit only the $\mathrm{deg}(u)$ real neighbors of u, giving $\sum \mathrm{deg}=2E$ work; scanning all pairs (matrix style) would cost $O(V^2)$ regardless of how sparse the graph is.

parent[w] records who discovered w on the shortest-path tree, so the chain from w to s is a fewest-edge route; you reverse it only because you built it from target to source.

Each node is discovered exactly once (marked at enqueue), so it gets exactly one parent; the discovery edges form a tree, and the non-tree ("cross"/"back") edges are simply ignored for distance purposes.

BFS lays nodes out in levels, and coloring by level parity (even vs odd distance) is exactly a 2-coloring; a same-color edge between two nodes on the same level reveals an odd cycle, so the graph is not bipartite.

Because u was dequeued with the minimum remaining distance, any other route to a neighbor w passes through a node of distance $\ge d(u)$, giving length $\ge d(u)+1$ — so $d(u)+1$ is already optimal.

The source is enqueued, popped, has no neighbors, and the queue empties; result is dist = {s: 0}, the trivial correct answer.

When scanning s's neighbors we find s, but it is already marked visited, so it is skipped — the self-loop harmlessly contributes nothing to distances.

The second and later parallel edges hit an already-visited endpoint and are skipped; distances are unaffected because BFS cares only about reachability at fewest hops, not edge multiplicity.

The target is never enqueued, so its dist stays at the "infinity"/-1 sentinel; you must initialize distances to that sentinel and interpret it as "no path exists".

Every non-source node is a direct neighbor of s, so all of them get distance 1 in the first level; the queue swells to $n-1$ nodes at once, illustrating the $O(V+E)$ bound with $E=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$.

Never more than one or two nodes at a time, since each level has a single node; this is the opposite extreme of $K_n$ and shows queue size depends on the graph's "width", not just $V$.

The main loop starts with an empty queue and exits immediately, leaving every other node unvisited — the source's distance is correct but nothing else is ever explored.

Not necessarily — leaves are simply nodes with no undiscovered neighbors, so different branches can end at different levels depending on where cycles close off further exploration.