大家好!我是幻化意识流。
今天我们用Python写一个最小生成树算法,我做了注释说明,欢迎大家一起学习:
以下是使用Prim算法实现最小生成树的代码:
from typing import List, Tuple
def prim_algorithm(graph: List[List[Tuple[int, int]]]) -> List[Tuple[int, int]]:
"""
Prim算法实现最小生成树
参数:
graph: 无向图的邻接表表示法,graph[i]表示与节点i相邻的节点列表,(j, w)表示节点i到节点j的边权重为w
返回值:
以元组形式表示的最小生成树,元组中第一个值表示边的起始节点,第二个值表示边的结束节点,例如:[(0, 1), (1, 2), (2, 3)]
"""
n = len(graph) # 图中节点的个数
mst = [] # 存储最小生成树的边
selected = set([0]) # 存储已经被选中的节点的集合
candidates = graph[0] # 存储候选边的集合,初始时为节点0的所有邻接边
while len(selected) < n:
min_edge = None # 选出当前候选边中权重最小的边
for edge in candidates:
if edge[0] not in selected: # 如果边的起始节点不在已选节点集合中,则不考虑该边
continue
if min_edge is None or edge[1] < min_edge[1]: # 如果该边权重小于目前最小边,则更新最小边
min_edge = edge
mst.append(min_edge) # 将最小边加入到最小生成树中
selected.add(min_edge[1]) # 将该边的结束节点加入到已选节点集合中
candidates.extend(graph[min_edge[1]]) # 将该边的结束节点的所有邻接边加入到候选边集合中
candidates = [edge for edge in candidates if edge[0] in selected] # 过滤掉候选边集合中已经不合法的边
return mst
这个算法的时间复杂度是 $O(E log V)$,其中 $E$ 表示图中的边数,$V$ 表示图中的节点数。
如果喜欢我的文章,麻烦您动动您的神手帮我点个赞哦!本人在此深深的感谢!
页面更新:2024-04-24
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号