次小生成树的两种算法:
算法1、step 1. 先用prim求出最小生成树T.
在prim的同时,用一个矩阵max[u][v] 记录 在T中连结任意两点u,v的唯一的
路中权值最大的那条边的权值. (注意这里).
这是很容易做到的,因为prim是每次增加一个结点s, 而设已经标号了的结点
集合为W, 则W中所有的结点到s的路中的最大权值的边就是当前加入的这条边.
step 1 用时 O(V^2).
step 2. 枚举所有不在T中的边uv, 加入边uv则必然替换权为max[u][v]的边。
算法2、先用prim求出最小生成树T。
枚举T中的每一条边,把它删除,求剩下的图的最小生成树。选所有枚举得到的生成树中的最小的那一个。