最小生成树问题赋权连通图的最小支撑树求最小树的Kruskal算法用Kruskal算法求最小树“是否成圈〞的判断事实上不比边长排序来得容易，尤其是用计算机程序实现时。T={v1,v2,v3}赋权的连通图G=(V,E)中m=|E|,n=|V|,最小树的存在性：赋权的连通图G=(V,E),记m=|E|,n=|V|,支撑树T的边数|E(T)|=n-1,E(T)必为V的n-1元子集，显然这种子集合最多个，所以支撑树是有限的，其权组成有限集，必有最小的[但可能不唯一]。t←t+1,k←k+1,转S3用Kruskal算法求最小树t←t+1,k←k+1“是否成圈〞的判断事实上不比边长排序来得容易，尤其是用计算机程序实现时。T={v1,v2,v3,v5}最小树的存在性：赋权的连通图G=(V,E),记m=|E|,n=|V|,支撑树T的边数|E(T)|=n-1,E(T)必为V的n-1元子集，显然这种子集合最多个，所以支撑树是有限的，其权组成有限集，必有最小的[但可能不唯一]。∴最小树的权为24，最小树为T={v1v2,v1v3,v2v5,v5v6,v6v7,v6v4}S4:若T∪{ek}有圈则k←k+1转S4，否则转S5“是否成圈〞的判断事实上不比边长排序来得容易，尤其是用计算机程序实现时。要让程序读懂“图”，程序如何判断是否成“圈”？谈何容易，时间、空间复杂性绝不应小看树:其特点之一是边数比顶点数少一；Prim法求最小支撑树用Prim算法(就近法)求赋权连通图G的最小树谢谢