讨论:如何求得最小生成树? 最小生成树(MST)的性质如下: 若U集是的一个非空子集,若(uv是一条最小权值的 边,其中u∈U,v∈VU;则:(u,vo)必在最小生成树上。 设想一下:先把权值最小的边归入生成 树内,逐个递增,舍去回路边,则得到 的很可能就是最小生成树! 对边操作 求MST有多种算法,但最常用的是以下两种: Kruskal(克鲁斯卡尔)算法 Prim(普里姆)算法 对顶点操作 Kruskal算法特点:将边归并,适于求稀疏网的最小生成树。 Prime算法特点:将顶点归并,与边数无关,适于稠密网。9 讨论：如何求得最小生成树？ 最小生成树（MST）的 性质如下： 若U集是V的一个非空子集，若(u0 , v0 )是一条最小权值的 边，其中u0U，v0V-U；则：(u0 , v0 )必在最小生成树上。 设想一下：先把权值最小的边归入生成 树内，逐个递增，舍去回路边，则得到 的很可能就是最小生成树！ 求MST有多种算法，但最常用的是以下两种： ❖ Kruskal（克鲁斯卡尔）算法 ❖ Prim（普里姆）算法 Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。 Prime算法特点: 将顶点归并，与边数无关，适于稠密网。 对边操作 对顶点操作