不失一般性，设由prim算法得到的最小生成树为G，其中度最小的2个相邻节点为a,b，要证明最优子结构，此时需合并a,b为一个整体节点c,并删除连接a,b的边y，此时得到的新生成树记作G'，若G'是最小生成树，原问题正确性得证；若G'不是最小生成树，则存在另一最小生成树G''，且。不失一般性，设由Kruskal算法得到的最小生成树为G，其中权值最小的边为e，要证明最优子结构，此时需合并以e为边的两个