数据结构–最小生成树
连通图
\color{red}连通图
连通图的生成树是
包含图中全部顶点的一个极小连通子图
\color{red}包含图中全部顶点的一个极小连通子图
包含图中全部顶点的一个极小连通子图。
若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通
图，若加上一条边则会形成一个回路。
最⼩⽣成树（最⼩代价树）
道路规划要求：所有地⽅都连通，且成本尽可能的低 \color{red}道路规划要求：所有地⽅都连通，且成本尽可能的低 道路规划要求：所有地⽅都连通，且成本尽可能的低
部分生成树：
对于⼀个 带权连通⽆向图 \color{red}带权连通⽆向图 带权连通⽆向图G = (V, E)，⽣成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有⽣成树的集合，若T为R中 边的权值之和最⼩的⽣成树 \color{red}边的权值之和最⼩的⽣成树 边的权值之和最⼩的⽣成树，则T称为G的 最⼩⽣成树（ M i n i m u m − S p a n n i n g − T r e e , M S T ）。 \color{red}最⼩⽣成树（Minimum-Spanning-Tree, MST）。 最⼩⽣成树（Minimum−Spanning−Tree,MST）。
注：
• 最⼩⽣成树可能有多个，但边的权值之和总是唯⼀且最⼩的
• 最⼩⽣成树的边数 = 顶点数 - 1。砍掉⼀条则不连通，增加⼀条边则会出现回路
• 如果⼀个连通图本身就是⼀棵树，则其最⼩⽣成树就是它本身
• 只有连通图才有⽣成树，⾮连通图只有⽣成森林
Prim 算法（普⾥姆）
Prim 算法（普⾥姆）：
从某⼀个顶点开始构建⽣成树；
每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。
对于这个图，用prim算法可以得到下面最小生成树：
注：最小生成树可能不唯一，可能存在多棵最小生成树
Kruskal 算法（克鲁斯卡尔）
Kruskal 算法（克鲁斯卡尔）：
每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通
对于这个图，用Kruskal算法可以得到下面最小生成树：
判断是否属于同一个集合可以使用并查集算法实现 \color{purple}判断是否属于同一个集合可以使用并查集算法实现 判断是否属于同一个集合可以使用并查集算法实现
Prim 算法 v.s. Kruskal 算法
Prim 算法（普⾥姆）：
从某⼀个顶点开始构建⽣成树；
每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。
时间复杂度：
O
(
∣
V
∣
2
)
O(|V|^2)
O(∣V∣2)
适合⽤于边稠密图
Kruskal 算法（克鲁斯卡尔）：
每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通
时间复杂度：
O
(
∣
E
∣
l
o
g
2
∣
E
∣
)
O( |E|log_2|E| )
O(∣E∣log2∣E∣)
适合⽤于边稀疏图
代码与例题部分可以查看下面的文章：
\color{green}代码与例题部分可以查看下面的文章：
代码与例题部分可以查看下面的文章：
最小生成树（Kruskal算法+Prim算法）简单讲解+最小生成树例题
