最小生成树之Prim贪心算法

本文共253个字,预计阅读时间需要1分钟。

设图G顶点集合为U,首先任意选择图G中的一点作为起始点a,将该点加入集合V,再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小,此时将b点也加入集合V;以此类推,现在的集合V={a,b},再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小,此时将c点加入集合V,直至所有顶点全部被加入V,此时就构建出了一颗MST。因为有N个顶点,所以该MST就有N-1条边,每一次向集合V中加入一个点,就意味着找到一条MST的边。

代码:

 

读者评分
[评分人数: 1 平均分: 5]

3 位极客在 “最小生成树之Prim贪心算法” 留下足迹

评论

OmegaXYZ