（Prim）和（Kruskal）最小生成树的两种算法
文章目录
一、生成树的概念
二、最小生成树的概念
三、普里姆算法（Prim）构造最小生成树
四、 克鲁斯卡尔算法（Kruskal）构造最小生成树
一、生成树的概念：
一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点和构成一颗树的（n-1）条边。
可以用深度优先遍历、广度优先遍历生成树：
二、最小生成树的概念：
对于带权连通图G（每条边上的权均为大于零的实数），可能有多棵不同生成树。
- 对于带权连通图G（每条边上的权均为大于零的实数），可能有多棵不同生成树。
- 每棵生成树的所有边的权值之和可能不同
- 其中权值之和最小的生成树称为图的最小生成树
三、普里姆算法（Prim）
普里姆算法是一种构造性算法，用于构造最小生成树
Prim算法更适合稠密图求最小生成树
四、克鲁斯卡尔算法（Kruskal）
- 一种求带权无向图的最小生成树的构造性算法
- 按权值的递增次序选择合适的边来构造最小生成树的方法。
Kruskal算法更适合稀疏图求最小生成树
