Prim算法如何绘制最小生成树图解？

本文共计1675个文字，预计阅读时间需要7分钟。

Prim算法+最小生成树+图解：什么是生成树+子图：G=V,E,C，G'=V',E',C'，为两个图（V为点集，E为边集），若V'=V，E'=E，则称G'为G的子图。若V'=V，E'是E的子集，则称G'为G的子图。若G'=G，则称G'为G的子图。

Prim 最小生成树 图解 ​

什么是生成树

子图：G=<V，E>，G'=<V', E'>，为两个图（V为点集，即图中点的集合，E为边集），如果V'是V的子集且E'是E的子集，则G'是G的子图。

如果V'=V，则称G'为G的生成子图

如果G'是无向生成子图且是树的结构，则为生成树

最小生成树

最小生成树：是一张有权无向连通图中边权和最小的生成树

Prim算法：

维护一个已经加入最小生成树的点的集合C，每次通过一条边连接一个不在这个点集C的点，直到最后形成一个树形结构

Dist(u)表示u点到点集C中的点的最小距离

每次选择一个到点集C距离最小的点加入点集C，并通过加入的点去更新未加入的点到点集C的最小距离（因为C中多加了一个点），直到n个点全部加入点集C或没有点能够加入（不能构成连通图）。

图解

​

前言：已经加入点集C的点标记为蓝色，当前加入的点标记为红色，被当前加入的点更新的dist标记为红色。