最小生成树(MST)
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 [1] 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。
Kruskal算法
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止.
Kruskal算法的基本思想为：初始时隐去所有的边，这样图中每个顶点都自成一个连通块。之后执行下面的步骤：
1.对所有的边按照从小到大排序。
2.按照边权从小到大测试所有的边，如果当前测试的边所连接的两个顶点不在一个连通块中，则把这条测试边加入当前最小生成树中；否则，将边舍去。
3.执行步骤2，直到最小生成树的边数等于总顶点的数目减一或是测试完所有边结束。当结束时最小生成树的边数小于总顶点数减一，则该图不连通。
Prim算法
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew= {x}，其中x为集合V中的任一节点（起始点），Enew= {},为空；
3).重复下列操作，直到Vnew= V：
a.在集合E中选取权值最小的边
b.将v加入集合Vnew中，将
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
应用
铺设光缆
要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。