普里姆算法
考试要求：
掌握
知识路径：
>
应用数学
>
图论应用
>
图论应用
>
最小生成树
设已知
G
=（
V
，
E
）是一个带权连通无向图，顶点
V
=｛0，1，2，…，
n
-1｝。设
U
是构造生成树过程中已被考虑在生成树上的顶点的集合。初始时，
U
只包含一个出发顶点。设
T
是构造生成树过程中已被考虑在生成树上的边的集合，初始时
T
为空。如果边（
i
，
j
）具有最小代价，且
i
∈
U
，
j
∈
V
-
U
，那么最小代价生成树应包含边（
i
，
j
）。把
j
加到
U
中，把（
i
，
j
）加到
T
中。重复上述过程，直到
U
等于
V
为止。这时，
T
即为要求的最小代价生成树的边的集合。
普里姆算法的特点是当前形成的集合
T
始终是一棵树。因为每次添加的边是使树中的权尽可能小，因此这是一种贪心的策略。普里姆算法的时间复杂度为
O
(
n
2
)，与图中边数无关，所以适合于稠密图。
更多复习资料
请登录电脑版软考在线 www.rkpass.cn
京B2-20210865
|
京ICP备2020040059号-5
京公网安备 11010502032051号
|
营业执照
Copyright ©2000-2025 All Rights Reserved
软考在线版权所有
京公网安备 11010502032051号 | 营业执照