最小生成树

介绍

生成树：给定一个无向连通图，在其子图中，如果任意顶点都是连通的，且是一个树结构，则这个树就是生成树。

最小生成树：在一个图的所有生成树中，边的权值之和最小的生成树就是最小生成树。

例如：

image-20221226005529321

其最小生成树

image-20221226010258468

prim（普里姆）算法

prim算法是一种贪心算法，主要思路是：

  1. 先随意找一个顶点，并加入集合
  2. 从该只有一个点的集合出发，找到一个离该集合最近的顶点并加入到集合中
  3. 然后继续找离集合最近的顶点，加入集合，直到所有点都在集合中

例如：

image-20221226005529321

先随便找一个点，比如我找的是顶点 5，将顶点 5 加入集合中

image-20221229231803400

现在找到和集合相连的点

image-20221229232034624

其中顶点 3 离集合最近，距离为 3。将顶点 3 加入到集合中

image-20221229232534417

继续找与集合内顶点直接相连的顶点

image-20221229232636413

其中顶点 1 离集合最近，将顶点 1 加入到集合中

image-20221229232828984

继续找和集合直接相连的顶点

image-20221229232949898

顶点 2 离集合最近，将顶点 2 加入集合中

image-20221229233240489

最后将顶点 6 加入到集合中

image-20221229233336421

得到最小生成树

image-20221226010258468

相关例题

1584. 连接所有点的最小费用 - 力扣（Leetcode）