卷別

資料結構與演算法

選擇

國立臺灣大學 2026 · 考試 · 第 24 題

(4 points) Let $G = (V, E)$ be a directed graph represented using adjacency lists without edge weights. We run BFS from a source $s$ , producing distance labels $d[v]$ for each reachable vertex $v$ . Which of the following statements is always true?

(A)
For every edge $(u, v) \in E$ , we must have $d[v] \le d[u] + 1$ .
(B)
If $d[v] = d[u] + 1$ , then $(u, v)$ must be a tree edge in the BFS tree.
(C)
BFS always produces a shortest-path tree that is also a topological ordering of the reachable subgraph.
(D)
If the graph is represented by an adjacency matrix instead of adjacency lists, BFS may compute incorrect distances that lead to repeated relaxations.
(E)
If BFS discovers vertices in the order $v_1, v_2, \dots, v_k$ , then this order is a shortest-path ordering for all pairs of vertices.

標準解析

AI 已複查