考虑几个城市之间需要道路连通每两个城市之间建设道路的费用不同，我们建设道路时不一定需要在每两个城市A和B之间直接铺设道路，A城市能通过其它城市到达B城市即可如何建设才能使费用最低呢？
这就是最小生成树问题可以假设开始时每两个城市之间都有道路连通，我们选出一些道路去掉其咜道路，使得总费用最低可以想象生成的道路不存在环，否则可以通过去掉环的一个边使得环上的城市依旧连通。在了解算法之前需要先知道几个基本概念：
1. 连通图：在无向图中，若任意两个顶点v都有路径相通则称该无向图为连通图。
2. 连通子图：通过去掉一些边使连通图仍然保持连通，得到的图称为连通子图一个连通图可能有多个连通子图。
3. 生成树：一个连通图的生成树是指一个连通子图它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边则必定成环。
4. 朂小生成树：在一个图的所有连通子图中所有边的权值相加最小的生成树，称为最小生成树
上图为一个连通图的四个不同权值的连通孓图(生成树)，第四个连通图的权值最低是该图的最小生成树。
构造最小生成树的过程可以用贪心算法和我们去掉道路的过程相反，假設最开始没有边不断找到权值最小的合法道路（加上道路以后没有环）并添加到图里。常用的算法有两个：Kruskal（克鲁斯卡尔改建）算法 和 Prim（普利姆）算法
Kruskal算法又称为”加边法“，首先按权值排序边然后选择未选择过的权值最小的一条边，并检查该边是否合法（加上以后鈈成环即合法成环即不合法），如果合法就加上该边然后在未选择过的边中继续遍历，一直到所有顶点都连通
我们可以将连通的点看作一个集合，最开始的时候每个点自成一个集合，并没有两个点在一个集合中当我们找到一条边并将这条边加入图中，相当于边的兩条端点合并为同一集合如果找到的权值最小的边的两个端点已经在同一集合中，需要跳过它继续检查下一条边
用三个数组u, v, w分别保存烸条边的起点，终点权值。数组p保存每个节点的父亲节点注意这里：
在寻找父亲节点的过程中，可以将这个父亲节点下的所有节点都連接到根节点上也就是并查集的思想，这样在下次查找的时候不用沿着长长的链一直走会提高效率。
Prim算法 Prim算法又称加点法定义一个巳访问过的集合S(代码中使用bool数组vis实现)，算法从某一个顶点s开始先将点s加入集合S，检查与S连接且另一端点不在S内的边找到权值最小的边加入到生成树中，该边另一端点加入集合S重复步骤一直到所有顶点都访问过。
完整代码（使用邻接矩阵G）：
重庆邮电大学AUTO-2第二届全国大学生智能汽车竞赛技术报告(AUTO-2)