MST(Minimum Spanning Tree,最小生成树)问题有两种通用的解法,Prim
算法就是其中之一,它是从点的方面考虑构建一颗 MST,大致思想是:设图
G 顶点集合为 U,首先任意选择图 G 中的一点作为起始点 a,将该点加入集
合 V,再从集合 U-V 中找到另一点 b 使得点 b 到 V 中任意一点的权值最小,
此时将 b 点也加入集合 V;以此类推,现在的集合 V={a,b},再从集合 U-V
中找到另一点 c 使得点 c 到 V 中任意一点的权值最小,此时将 c 点加入集合
V,直至所有顶点全部被加入 V,此时就构建出了一颗 MST。因为有 N 个顶
点,所以该 MST 就有 N-1 条边,每一次向集合 V 中加入一个点,就意味着
找到一条 MST 的边。
用图示和代码说明:
初始状态:
设置 2 个数据结构:
lowcost[i]:表示以 i 为终点的边的最小权值,当 lowcost[i]=0 说明以 i 为终点的
边的最小权值=0,也就是表示 i 点加入了 MST