普利姆演算法

习题预习

1. 使用Prim’s演算法来寻找一个带有权重边的最小生成树，请问这个演算法的时间复杂度为何？
2. 请问在Prim’s演算法中，如何选择下一个要加入最小生成树的节点？
3. 假设有一个带有权重边的无向图，请问是否一定存在一个带有权重边的最小生成树？
4. 如果在Prim’s演算法的过程中，所有边的权重都相同，最小生成树可能有多个吗？
5. 在Prim’s演算法中，如何判断一个图是连通的？

说明知识

Prim的演算法是一种用于寻找最小生成树的贪婪演算法。

简单来说，Prim演算法通过从一个起点开始，选择边的方式来构建一个最小生成树。演算法开始时，选择任意一点作为起点，然后选取与该起点相连的最小权值边，a和b两个点在生成树上，没有其他的路线能够从a和b这两个点达到，接着选择与a或b相连的点到生成树上（由于是连到a或b点，最小权值边的选择是唯一的），此过程迭代直到生成树中包含了所有顶点。

例如，考虑下图：

      C
    / | \
  3/  |2\  \4
  A---F---B
  2\  |5/  /3
    \ | / 
      D

从节点A开始，该该节点被添加到生成树中。 节点A与节点F之间的边（权值为2）是包含节点A的最小权值边，添加节点F。节点A与节点C之间的边（权值为3）是包含节点A的最小权值边，添加节点C。 节点F与节点B之间的边（权值为2）是包含节点B，F的最小权值边，添加节点B。 节点F与节点D之间的边（权值为5）是包含节点B、F、D的最小权值边，添加节点D。 节点F与节点E之间的边（权值为4）是包含节点B、F、E、D的最小权值边，添加节点E。

最终生成树如下所示：

      C
      |
  (3) A
      |
      F
    / | \
  2/  |  \2
  B   E   D

条列重点

• Prim’s Algorithm是一种用来找寻最小生成树的演算法。
• 演算法通常需要一个起始点，从该起始点开始建立最小生成树。
• 演算法维护两个数据结构，分别是集合S和边集合T。S表示已经在最小生成树上的点，而T则表示已经在最小生成树上的边。
• 首先将起始点加入集合S中。
• 从集合S中的所有点开始找寻最小生成树的下一个边，找到其中最小权重的边并加入边集合T中。
• 将边的两个端点中未被加入集合S中的点加入集合S中，重复上述过程，直到所有点都在集合S中。
• Prim’s Algorithm的时间复杂度为O(E log V)，其中E是边的数量，V是点的数量。

知识测验

1. 给定以下未经排序的图形的边权重，求 Prim’s 算法找到的最小生成树的权重总和：

    A --2-- B --1-- C
   /    |       /    |
 8     3     1     5
 /      |     /      |
D --2-- E --4-- F --3-- G

答案：11

2. 给定以下未经排序的图形的边权重，求 Prim’s 算法找到的最小生成树的权重总和：

    A --2-- B --1-- C --2-- D
   /    |       /    |       |
 3     1     6     3     4
 /      |     /      |      |
E --5-- F --2-- G --5-- H --3-- I

答案：13

3. 给定以下未经排序的图形的边权重，求 Prim’s 算法找到的最小生成树的权重总和：

    A --2-- B --1-- C --2-- D --3-- E
   /    |       /    |      |       |
 7     6     1     2     8      5
 /      |     /      |     /        |
F --3-- G --4-- H --10-- I --2-- J --1-- K

答案：16

4. 给定以下未经排序的图形的边权重，求 Prim’s 算法找到的最小生成树的权重总和：

     A --3-- B --1-- C --2-- D --5-- E
    /    |       /    |      |       |
  10    2     5     4     7      8
  /      |     /      |     /        |
 F --8-- G --3-- H --1-- I --2-- J --4-- K

答案：19

5. 给定以下未经排序的图形的边权重，求 Prim’s 算法找到的最小生成树的权重总和：

       A --2-- B --1-- C --2-- D --3-- E
      /    |       /    |      |      |
    8     10    6     2     1     2
   /      |     /      |     /       |
 F --3-- G --4-- H --7-- I --9-- J --3-- K

答案：19