Prim算法
2016-10-06 20:49:50 0 举报Prim算法是一种贪心算法，用于求解图的最小生成树问题。它从一个顶点开始，每次选择与已选顶点集合中距离最小的顶点相连的边，并将其加入已选顶点集合中，直到所有顶点都被加入。该算法保证了所得到的生成树是连通的且包含图中的所有顶点。Prim算法的时间复杂度为O(V^2)，其中V为图中顶点的数量。
作者其他创作
大纲/内容
1
V1
从V1、V3、V5顶点相关联的边中选一条最小的边
V3
Prim算法流程
2
6
V6
V5
4
5
3
V4
V2
从V1顶点出发，选一条最小的边
原图
第一步
第三步
第四步
第五步
从V1、V3、V5、V6顶点相关联的边中选一条最小的边
第二步
从V1、V3、V5、V6、V2顶点相关联的边中选一条最小的边
从V1、V3顶点相关联的边中选一条最小的边
这条边不能选，因为会形成环路
收藏
收藏
0 条评论
下一页
