Python采用Prim(普利姆)算法实现最小生成树
需积分: 1 103 浏览量
2024-05-25
10:56:16
上传
评论
收藏 109KB PDF 举报
最小生成树（Minimum Spanning Tree, MST）
最小生成树是一个无向加权连通图的子集，它连接了图中的所有顶点（节点），并且没有循环（回路），同
时所有边的权重之和是最小的。在计算机网络、电路设计、物流运输等领域有着广泛的应用。
Prim算法实现原理和步骤
1. 从一个顶点开始，将其加入已选择的顶点集合。
2. 找出所有与已选择的顶点集合相邻的、且未选择的顶点中权重最小的边。
3. 将该边加入最小生成树，并将该边的另一端点加入已选择的顶点集合。
4. 重复步骤2和3，直到所有顶点都被选择。
Python实现
import heapq
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
# 找到与顶点v相邻的、未选择的顶点中权重最小的边
def min_key(self, key, mst_set):
min_val = float('inf')
for vertex in range(self.V):
if key[vertex] < min_val and mst_set[vertex] == False:
min_val = key[vertex]
min_index = vertex
return min_index
# Prim算法实现
def prim_mst(self):
result = [] # 存储最小生成树的边
i, e = 0, 0
self.key = [float('inf')] * self.V # 初始化权重数组
self.parent = [-1] * self.V # 初始化父节点数组
# 将第一个顶点加入已选择的顶点集合，并将其权重设为0
self.key[0] = 0
self.mst_set = [False] * self.V
# 遍历所有顶点
while e < self.V - 1:
资源评论
孤蓬&听雨
- 粉丝: 1w+
- 资源: 382
最新资源
- 9364b7c93d9cd9d09c3bd5ceeaa0350b.JPG
- 代码审计工具Checkmarx安装环境和安装过程
- MiniBurp.7z
- 最新的Chrome版本
- eclipse哈哈哈哈哈
- vs 2019 c++20规范 S TL库中的 ratio duration＜T,U＞ time-point＜T,U＞等
- Idea哈哈哈哈哈哈哈哈哈
- vs 2019 c++20 规范的头文件 ＜future＞ 源码注释和几个结论
- vs 2019 c++20规范 S TL 库中头文件 ＜atomic＞ 源码注释及探讨几个知识点
- c++20 规范， v s 2019 ， 头文件 ＜m u t ex ＞ ,注释以及几个探讨
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
