一、基本知识

学习最小生成树算法之前我们先来了解下 下面这些概念：

树（Tree）：如果一个无向连通图中不存在回路，则这种图称为树。

生成树 （Spanning Tree）：无向连通图G的一个子图如果是一颗包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的极小连通子图。这里所谓极小是指：若在树中任意增加一条边，则将出现一条回路；若去掉一条边，将会使之变成非连通图。

最小生成树（Minimum Spanning Tree，MST）：或者称为最小代价树Minimum-cost Spanning Tree:对无向连通图的生成树，各边的权值总和称为生成树的权，权最小的生成树称为最小生成树。

构成生成树的准则有三条：

1、 必须只使用该网络中的边来构造最小生成树。

2、必须使用且仅使用n-1条边来连接网络中的n个顶点

3、不能使用产生回路的边。

构造最小生成树的算法主要有：克鲁斯卡尔（Kruskal）算法和普利姆（Prim）算法他们都遵循以上准则。