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 中;否则舍去,重新选择重复下去,直到所有顶点在同一连通分量上为止