#环路定理

算法理论基础

最小生成树两大理论基础：1. 切分性质：任意割的权值最小割边，必属于某棵最小生成树，是 Prim 算法的依据。2. 环性质：任意环中权值最大的边，一定不在最小生成树里，支撑 Kruskal 算法。连通加权无向图才存在最小生成树，总权值和唯一，可有多棵不同最小生成树。