卷別

資料結構與演算法

選擇

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

(4 points) Let $G = (V, E)$ be a connected, undirected, weighted graph with distinct and positive edge weights. Let $A \subseteq E$ be a subset of edges that is contained in some minimum spanning tree of $G$ . Which of the following statements is always true?

(A)
Any minimum-weight edge in the graph is safe for $A$ .
(B)
For any cut $(S, V \setminus S)$ , the lightest edge crossing the cut is safe for $A$ , regardless of whether the cut respects $A$ .
(C)
If an edge $e$ is the lightest edge on some cycle in $G$ , then $e$ must belong to every minimum spanning tree (MST).
(D)
If a cut $(S, V \setminus S)$ respects $A$ , then the lightest edge crossing this cut is safe for $A$ .
(E)
Any edge chosen by Prim's algorithm from an arbitrary start vertex is safe for every subset $A \subseteq E$ .

標準解析

AI 已複查