Prim算法的算法框架
所谓算法框架,其实就是大概的一个步骤,说白了就是每一步该做什么。
Prim是一种贪心的最小生成树算法,适合于边稠密的图。
- 初始时从图中仁取义顶点加入树T,此时树中只含有一个顶点。
- 选择一个与当前T中顶点集合距离最近的顶点,并将该顶点和相应的边加入T,每次操作后T的顶点数和边数都加1。
- 以此类推,直到图中所有的顶点都并入T,得到的T就是最小生成树,此时T中必有n-1条边。
Prim算法伪代码:
void prim(G, T) {
// 初始化空树
T = ∅;
// 添加任意顶点w
U = {
w}