什么是最小生成树？

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

 

MST性质：

假设 N = (V, {E})是一个连通网，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值（代价）的边，其中 u ∈ U， v ∈ V - U，则必存在一棵包含边（u, v）的最小生成树。

证明如下（反证法）：

　　假设连通网N的任何一棵最小生成树中都不包含边（u，v）。

　　设T是N的一棵最小生成树，则由上述假设可知，T中不包含（u，v）。由于T是连通的，因此有一条从u到v的路径。将T中的顶点集分为两部分：顶点集U和顶点集V - U，其中，顶点集U和相关的边构成一棵最小生成树T1，顶点集V - U和相关的边也构成一棵最小生成树T2，并且T1与T2之间只能有一条边，不妨设为（u`, v`），则u 和 u`之间、v和v`之间均是连通的。当把边（u，v）加入最小生成树T时，T中必有一条包含边（u，v）的回路，删除边（u`, v`），上述回路即被删除，由此得到另一棵生成树Ｔ｀，如图所示。因为边（ｕ，ｖ）的权值小于等于（ｕ｀，ｖ｀）的权值，则Ｔ｀的代价也就小于等于Ｔ的代价，因此Ｔ｀也是Ｎ的最小生成树，且包含边（ｕ，ｖ），与假设矛盾，得证。

 

 什么是Prim算法？

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

 

Prrim算法的基本思想是：假设N = （V， E）是连通网，令T = （U， TE）是N的最小生成树。算法的基本思想是：T的初始状态为U = {Vo} (Vo∈V），TE = {}，重复执行下述操作：

① 在所有u∈U，v∈V - U的边（u，v）∈ E中，找一条代价最小的边（ui, vj）并入集合TE，同时将 vj 并入 U 中；

② 如此不断重复，知道 U = V 为止。此时 TE 必有 n - 1 条边，则 T（V，TE）为 N 的最小生成树。

 

Prim算法代码实现：