最小生成树

邻接矩阵

image.png image.png image.png image.png image.png

最小生成树问题 Minimum Span Tree

最小生成树在现实生活中的应用：
1、电缆布线设计
2、网络设计
3、电路设计

针对带权无向图
针对连通图

找V-1条边
连接V个顶点
总权值最小

切分定理
把图中的结点分为两部分，成为一个切分(Cut)

如果一个边的两个端点，属于切分(Cut)不同的两边，这个边称为横切边(Crossing Edge)

切分定理：

给定任意切分，横切边中权值最小的边必然属于最小生成树。