|
|
|
知识路径： > 应用数学 > 图论应用 > 图论应用 > 最小生成树 >
|
|
考试要求：掌握
相关知识点：2个
|
|
|
|
|
设已知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(n2)，与图中边数无关，所以适合于稠密图。
|
|
|
|
|
|
|
|
