《算法分析与设计》作业1----最小生成树的Prim算法和Kruskal算法

1. Prim算法

• 加点：从一个顶点a开始，把顶点a加入最小生成树的集合U中，每次迭代选择与集合U中的点相连的权重最小的边对应的点，加入集合U中，继续迭代直到所有顶点都在集合U中。

• 构造步骤如下：
  1）假设从顶点A开始，发现边AB的权重最小，U={A,B}，输出边：A----B
  2）与A或B相连的权重最小的边为AC，U={A,B,C}，输出边：A----C
  3）与A或B或C相连的权重最小的边为CD，U={A,B,C,D}，输出边：C----D
  4）此时与U中元素相连的权重最小的边为DF，U={A,B,C,D,F}，输出边：D----F
  5）此时与U中元素相连的权重最小的边为FE，U={A,B,C,D,E,F}，输出边：F----D。此时所有边都在集合U中，最小生成树建立完成。

• 各步骤图解如下：
  

2. Kruskal算法

• 加边：去掉所有边，将边按权重从小到大的顺序添加到图中，保证添加的过程中不会形成环，，添加至所有顶点相连即可，即最小生成树的边数为顶点数-1。

• 构造步骤如下：
  1）最短边为EF，输出边：E----F
  2）接下来是权重为2的边，对于权重相同的边，添加无先后顺序，只要不形成环即可，若先加DF，输出边：D----F
  3）加入边AB，输出边：A----B
  4）同2）理，加边AC，输出边：A----C
  5）加边CD，输出边：C----D。此时生成树的边数为5，最小生成树建立完成。

• 各步骤图解如下：