Prim算法

Prim算法用于构造最小生成树，且适用于稠密图。

基本思想 : 归并顶点

设连通网络 N = { V, E }

从某顶点 u0 出发，

选择与它关联的具有最小权值的边(u0, v)，

将其顶点加入到生成树的顶点集合U中每一步从U中挑选一个顶点u，而另一个顶点不在U中的各个顶点中选择权值最小的边(u, v),把它的顶点加入到U中直到所有顶点都加入到生成树顶点集合U中为止

举例

Kruskal算法

Krusklal算法用于构造最小生成树，且适用于稀疏图。

基本思想 : 归并边

设连通网络 N = { V, E }

构造一个只有 n 个顶点，没有边的非连通图 T = { V, ∅\varnothing∅}, 每个顶点自成一个连通分量在 E 中选最小权值的边,若该边的两个顶点落在不同的连通分量上，则加入 T 中；否则舍去，重新选择重复下去，直到所有顶点在同一连通分量上为止

举例