一，次最小生成树

        定义：设T是图G的最小生成树，如果T1满足ω(T1)=min{ω(T’)| T’∈Not(T)},则T1是G的次小生成树。

        解释：除了最小生成树外，另外一个生成树的权值和最小的生成树，定义为次最小生成树。

        经典题目：POJ1679  The Unique MST，对于一张图，判断最小生成树是否惟一。惟一的定义是：不存在第二棵生成树，它的权值与最小生成树的权值相等。w(次最小生成树)!=w(最小生成树)

        算法的思路：1，先生成一棵最小生成树，

                               2，然后枚举生成树以外的边，每次添加了一条边后，会产生一个环

                               3，依次去掉环上的除新添加的边以外的权值最大边，然后判断新的生成树与原生成树权值是否相同（不可能比原来生成树的权值要小）

        总体思路：简单地说就是判断新添加的边是否与环上原有的边中权值最大的边具有相同的权值。（原因：最小生成树选取的边都是权值最小的，剩余的边>=最小生成树最大的边）

        方法一：先求最小生成树，标记出构成最小生成树边，然后枚举这些边，每次删一条，然后求一次生成树，将其值保存起来。求完之后，把删除的边补回去。进行下一次删边，枚举过程中保存最小值，如果最小值跟原来的最小生成树的值相等的话，则说明，该最小生成不唯一，反之唯一。

        方法二：用Prim算法求一棵最小生成树，利用Prim算法的特性，即对于每一步扩展，都保持扩展的结果是一棵树，为了方便下一步枚举边的判断，我们用一个Max数组记录最小生成树上任意两点之间的最大边权(这里存在歧义，正解为：找到i点跟j点之间所有边中最大的一条边)，这一步在Prim算法中很容易做到，因为Max[i][j]=max{Max[i][k],edge[k][j]}。接下来的操作就是枚举每一条不在最小生成树中的边，对于edge[i][j]，判断它是否等于Max[i][j]，若相等，则说明最小生成树不惟一。

PS:需要改进的地方，我在边与点之间做了一些映射，空间开销比较大，编程复杂度也高，以后想办法写得更简洁一些。(update：对于数据量小的题，用邻接矩阵存比较方便 )