定义1 对于无向图G和一棵树T来说，如果T是G的子图，则称T为G的树，如果T是G的生成子图，则称T是G的生成树。
定义2 对于一个边上具有权值的图来说，其边权值和最小的生成树称做图G的最小生成树。
定理1 对于一个图G，如果图中的边权值都不相同，则图的最小生成树唯一。
最小生成树
求无向图的最小生成树主要有Prim算法和Kruskal算法。
（1）基本算法
将图G中的所有点V分成两个顶点集合Va和Vb。在计算过程中Va中的点为已经选好连接入生成树的点，否则属于Vb。最开始的时候Va包含任意选取的图G中的一个点u，其余的点属于Vb，算法结束时所有与u连通的点属于Va，其余的点仍留在Vb中。如果算法结束时Vb不为空，说明图G的生成树不存在，只存在生成森林。
代码如下：
Kruskal算法基于贪心的思想，对于图G={V,E}，先构造G‘={V，Ø},然后依次向G’中添加E中未添加过的权值最小的边，如果这条边加入G‘中存在环，则去掉这条边，直到G’成为一棵树。
具体步骤：
①首先初始化，生成图G‘，并将E中的边按权值排序。
②从最小的边开始尝试加入到图G’中，如果当前便加入后存在环，则弃掉当前边，否则标记当前边并计数。
③遍历所有边后，如果选择的边数等于n-1，则生成最小生成树，计算步骤②所选择的边的权值之和，否则最小生成树不存在，只存在最小生成森林，但是Kruskal算法不需要反复运行，当前结果就是图G的最小生成森林。
算法的关键在于如何判断新加入的边会使图G‘产生环，这里使用并查集，并查集中的一个等价类代表图G’中的一个连通分量，也就是一棵树，如果新加入边的两端在并查集的一个等价类中，说明存在环，需要舍掉这条边；否则保留当前边，并合并涉及的两个等价类。
代码如下：
次小生成树
次小生成树的边的权值和可能等于最小生成树的权值和，或者略大。
定义1 设G={V,E}是连通的无向图，T是图G的一棵最小生成树。如果有另一棵树T1，T1≠T，满足不存在T‘，T’≠T，w(T')<w(T1)，则称T1是图G的次小生成树。
定理1 存在边(u,v) ∈T和(x,y)不属于T满足T\(u,v)U(x,y)是图的一棵次小生成树。
基于定理1，那么所有的T\(u,v)U(x,y)刚好构成了T的邻集，则T的邻集中权值最小的就是次小生成树了。（定义由最小生成树T进行一次可行交换得到的新的生成树所组成的集合，称为树T的邻集，记为N(T)。所谓的可行交换即去掉T中的一条边，再新加入图G中的一条边，使得新生成的图仍为树。）
效率较高的做法是先加入(x,y)，对于一棵树，加入(x,y)后一定成为环，如果删去环上除(x,y)以外的最大的一条边，会得到加入(x,y)时权值最小的一棵树。如果能够快速计算最小生成树中点x到y之间路径中最长边的长度，这个问题就能很好地解决。最小生成树中x到y的最长边可以使用树形动态规划或者LCA等方法在O(n^2)的时间复杂度内算出。如果使用Kruskal算法求最小生成树，可以在算法的运行过程中求出x到y路径上的最长边，因为每次合并两个等价类的时候，分别属于两个等价类的两个点间的最长边一定是当前加入的，按照这条性质记录的话就可以求出所有值了。为了便于合并时的修改，需要记录每个集合都有哪些点，可以写一个类似邻接表的数据结构，将以i为代表元的集合的所有点作为i的邻接点进行存储。
具体实现如下：
在Kruskal算法的基础上进行修改，加入对x,y两点在最小生成树上路径中最长边的计算，存入length[][]数组。使用链式前向星记录每个集合都有哪些点。为了合并方便，除了head[]记录每条邻接表的头结点位置外，end[]记录每条邻接表尾节点的位置便于两条邻接表合并。mst为最小生成树的大小，secmst为次小生成树的大小。
代码如下：
整个算法运行了一次Kruskal算法，时间复杂度是O(mlogm),同时又对整个length[][]进行赋值，时间复杂度O(n^2),最终又进行了时间复杂度为O(m)的遍历，所以总的时间复杂度为O(mlogm+n^2)。
有向图的最小树形图
首先看一个例子，有一处水源给附近的菜地供水，在没有抽水机的情况下，水只能从高处流向低处，每修一条水渠都有一定的花费，问怎样修才能使花费最低。考虑到水的流向，要求生成的最小生成树必须以水源为根，而且需要能够由根到达所有的节点。这就是最小树形图问题。
定义1 最小树形图的定义：
设G=(V,E)是一个有向图，如果具有以下性质：
(1)G中不包含有向环；
(2)存在一个顶点Vi，他不是任何弧的终点，而V的其他顶点都恰好是唯一的一条弧的终点。则称G是以Vi为根的树形图。
基本算法:
最小树形图基于贪心的思想和缩点的思想。所谓缩点，就是将几个点看成一个点，所有连接到这几个点的边都视为连到收缩点，所以从这几个点连出的边都被视为从收缩点连出。
下面根节点取为V0.
（1）求最短弧集合E0
从所有以Vi（i!=0）为终点的弧中去一条最短的，若对于点Vi，没有入边，则不存在最小树形图，算法结束；如果能取，则得到由n个点和n-1条边组成的图G的一个子图G‘，该子图的权值一定是最小的，但是不一定是一棵树。
（2）检查E0
若E0没有有向环且不含收缩点，则计算结束，E0就是G的以V0为根的最小树形图。若E0没有有向环、但含收缩点，则转步骤（4），若E0含有有向环，则转入步骤（3）。
（3）收缩G中的有向环
把G中的C收缩成点u，对于图G中两端都属于C的边被收缩掉了，其他弧扔保留，得到一个新的图G1，G1中以收缩点为终点的弧的长度要变化，变化的规律是：设点v在环C中，且环中指向v的边长为w，点v'不在环C中，则对于每条边<v',v),在G1中有边<v',u>与其对应，且权重为w(<v',v>)-w；对于图G中以环C为起点的边<v,v'>，在图G1中有边<u,v'>,权重为w(<v,v'>)。在此步生成的图G1中可能存在重边。
对于图G和图G1：
①如果图G1中没有以V0为根的最小树形图，则图G也没有。
②如果图G1中有以V0为根的最小树形图，则可以按照步骤（4）的展开方法得到图G的最小树形图。
因此，此时需要将G1带入步骤（1）做为图G继续进行计算，反复计算直到图G1的最小树形图求出。
（4）展开收缩点
如果图G1的最小树形图T1已经求出，那么所有T1的弧都属于T。将图G1的一个收缩点u展开成环C，从C中去掉与T1中有相同终点的弧，其他弧都属于T。
在计算的过程中可以发现，图Gi与图Gi-1的最小树形图的权值差正好是被缩掉的环的权值和，在这种性质的影响下，如果不需要知道最终的T0中到底需要那几条边，只需要知道T0的权值时，可以不需要展开。