树:在N个节点的无向连通图中,包含N个节点,有且只有n-1 条边的连通图称之为树。
最小生成树:
在带权的节点生成树中,所有节点路径权值和最小的树即为最小生成树。
求最小生成树的 Prim 算法解释:
1,将所有节点设置在集合 U 中,所有带全路径(边) 设置在集合 E 中(可用矩阵Aij)的元素表示;
2,随机抽取一节点 放入集合 S 中,找出 集合S 每个节点,与 集合 U-S 中每个节点路径中最小值,放入最小边集合TE,并将与之对应的U-S 中的节点,放入S 中;
3,如果S 中节点个数=N,即包含所有节点,循环结束,否则执行第二步操作;
最好所得的最小生成树边集合即为 TE 。
Prim 算法写入 Grasshopper 中,在建筑设计中的应用: