资料内容:
最小生成树(Minimum Spanning Tree, MST)
最小生成树是一个无向加权连通图的子集,它连接了图中的所有顶点(节点),并且没有循环(回路),同
时所有边的权重之和是最小的。在计算机网络、电路设计、物流运输等领域有着广泛的应用。
Prim算法实现原理和步骤
1. 从一个顶点开始,将其加入已选择的顶点集合。
2. 找出所有与已选择的顶点集合相邻的、且未选择的顶点中权重最小的边。
3. 将该边加入最小生成树,并将该边的另一端点加入已选择的顶点集合。
4. 重复步骤2和3,直到所有顶点都被选择。