最小生成树

July 9, 2022

Content #

对于每条边\((u,v)\in E\)，其权重记为\(w(u,v)\)。我们希望找到一个无环子集 \(T\subseteq E\)，使其能够将所有结点连接起来，又具有最小的权重，即

\begin{displaymath}w(T)=\sum_{(u,v)\in E}w(u,v)\end{displaymath}

的值最小。这样的树即为最小生成树。