（Prim）和（Kruskal）最小生成树的两种算法

文章目录

一、生成树的概念

二、最小生成树的概念

三、普里姆算法（Prim）构造最小生成树

四、 克鲁斯卡尔算法（Kruskal）构造最小生成树

一、生成树的概念：

一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点和构成一颗树的（n-1）条边。

可以用深度优先遍历、广度优先遍历生成树：

二、最小生成树的概念：

对于带权连通图G（每条边上的权均为大于零的实数），可能有多棵不同生成树。

• 对于带权连通图G（每条边上的权均为大于零的实数），可能有多棵不同生成树。
• 每棵生成树的所有边的权值之和可能不同
• 其中权值之和最小的生成树称为图的最小生成树

三、普里姆算法（Prim）

普里姆算法是一种构造性算法，用于构造最小生成树

Prim算法更适合稠密图求最小生成树

四、克鲁斯卡尔算法（Kruskal）

• 一种求带权无向图的最小生成树的构造性算法
• 按权值的递增次序选择合适的边来构造最小生成树的方法。

Kruskal算法更适合稀疏图求最小生成树