橘子洲头吃橘子
讲解最小生成树之前，您需要先了解什么是生成树。
生成树
数据结构中，根据数据之间关系的复杂程度，可以选用线性表、树和图这 3 种存储结构来有效地存储数据。其中，树和图最大的区别在于：图结构中可以存在环路，比如图 1 就是一个图结构，它具有很多环路（a-f-b-a、b-f-c-b 等等），而树结构中不允许存在环路（树结构可以看做是无环的图结构）。
图 1 图存储结构
图中的 a、b、c、d、e 和 f 称为顶点，顶点之间的连线称为路径，各个路径上标记的数值称为权或权值。例如，顶点 a 和 b 之间有一条路径，它的权值为 4。
图 1 除了是一个图，它还具备以下两个特征：
顶点之间的路径是无向（不带箭头）的，以顶点 a 和 b 之间的路径来说，它既表示从 a 到 b 的路径，也表示从 b 到 a 的路径；
从一个顶点到达另一个顶点，至少存在一条连通的路径（简称通路）。例如，顶点 a 和 c 之间就存在不只一条路径，比如 a-b-c、a-f-c、a-b-f-c 等等；
这样的图存储结构又称为连通图。
表面上，生成树指的是一种树存储结构，但实际上它指的是符合如下特征的连通图：
包含图中所有的顶点；
任意顶点之间有且仅有一条通路；
以图 1 为例，它是一个连通图，内部包含有多种生成树，比如：
图 2 生成树
图 2 仅列举了 2 种，图 1 的连通图还对应有其他的生成树。也就是说，一个连通图可能对应有多种不同的生成树。
最小生成树
结合图 1 和图 2，连通图中的各个路径都标有权值，一个连通图可能对应有多种生成树，因此各个生成树的总权值很可能不同。例如图 2 中，左侧生成树的总权值为 2 4 6 3 2 = 17，右侧生成树的总权值为 2 3 6 3 2 = 16。
最小生成树指的是总权值最小的生成树。如果连通图中含有权值相等的路径，则该图对应的最小生成树可能有多种；反之，如果连通图中各个路径的权值都不相等，则该图对应的最小生成图有且仅有一种。
最小生成树常用于解决以下问题：
使用通信网络连接多个站点，设计一种方案，使得在任何两个站点之间建立通信连接的同时保证成本最低；
构建跨越多个城市的高速公路或者铁路；
设计局域网；
查找一个连通图对应的最小生成树，常用的方法有 2 种，分别称为普里姆算法和克鲁斯卡尔算法。
