作者:风中摇曳一 | 来源:互联网 | 2023-09-17 09:09
github地址:https:github.comarkulo56thoughtblobmastersoftwaredataStruct%E6%95%B0%E6%8D%AE%E7%
github地址:
https://github.com/arkulo56/thought/blob/master/software/dataStruct/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E5%9B%BE_%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91.md
图-最小生成树(联通网的最小代价生成树)
(有规律的连续访问多个顶点的需求)
假设你是电信实施工程师,需要为一个镇的九个村庄架设通信网络做设计,村与村之间的距离就是边的权重,领导要求用最小成本完成任务,你该怎么做???
- 最小生成树也就是最小权重生成树
- n个顶点拥有n-1条边(想想树的节点个数),使得所有顶点之间都有路径可达
- n个节点之间不能构成回路
重要!!!
Prim算法/普里姆算法
原理:对于图G=(V,E),用Prim算法求最小生成树T=(S,TE)的流程如下:
- 初始化:设S、TE为空集,任选顶点k加入S
- 选取一条权值最小的边(X,Y), 其中X
总结
可以从图中看到,两种算法最后生成的最小生成树是一样的