prim和kruskal算法图解

### Prim 和 Kruskal 算法的图形化解释

#### Prim 算法的图形化过程

Prim 算法用于构建最小生成树，其核心是从任意一个节点出发逐步扩展到其他节点。该方法通过不断选择连接已访问集合与未访问集合之间最短的一条边来增加新的顶点。

假设有一个无向加权图：

1. **初始化阶段**
- 选取任一顶点作为起始点。

2. **迭代更新**
- 查找当前已被选中的顶点集与其外部相连的所有边上权重最小者，并将其对应的另一个端点纳入进来形成新的子图。
- 继续重复上述操作直到所有的顶点都被囊括其中为止。

此过程中每一步都会使得新加入的那个顶点成为现有部分的一个延伸，最终得到一棵覆盖整个网络且总长度尽可能小的树结构[^1]。

     A---7---B
    /         \
   5           8  
  /             \ 
C                D
                 |
                9|
                 |
                 E

在这个例子中，如果从A开始，则会依次按照AC (5), AB (7), BD (8)，最后DE (9)这样的顺序添加边构成MST。

#### Kruskal 算法的图形化展示

相比之下，Kruskal 的策略有所不同——它关注的是全局范围内尚未被使用的最轻量级链接而非局部最优解。具体做法如下所示：

- 将所有可能存在的边按从小到大排序；
- 对于每一个候选边，只要两端不属于同一个连通分量就接纳这条线段并把两个独立区域合并为一体；反之则舍弃以免造成环路；
- 当处理完毕全部符合条件的边之后即获得了一棵完整的最小生成树[^3]。

同样的对于上面那个简单案例而言，依据各连线数值大小先后次序考虑CE (5), AC (5), AD (8)，忽略掉BE因为这会造成循环回路，所以不会取BD而是直接接上AE完成构造。

     A       B
      \     /
       7   8
        \ /
         D
        / |   
       9  |
      /   |
     C----E
          5

两种方式虽然路径不同但是终点相同都能有效地找到一张给定网状布局里成本最低廉又不失联通性的框架体系。