def Kruskal(n,m,edges): edges.sort(key=lambda edges:int(edges[2])) edge_num=0 res=[] for i in range(m): if edge_num==n-1: break if unite(edges[i][0],edges[i][1]): res.append(edges[i]) edge_num+=1 return res def found(node): if fa[node]==node: return node else: fa[node]=found(fa[node]) return fa[node] def unite(node1,node2): node1=found(node1) node2=found(node2) if node1==node2: return False else: fa[node1]=node2 return True m=12 n=7 di={0:'A',1:'B',2:'C',3:'D',4:'E',5:'F',6:'G'} fa=[_ for _ in range(n)] edges=[[0,1,2],[0,3,5],[0,5,8], [1,2,7],[1,3,7],[1,4,2], [2,4,3],[3,4,6],[3,5,7], [3,6,3],[4,6,4],[5,6,4]] res=Kruskal(n,m,edges) s=0 for edge in res: print(f'{di[edge[0]]}-{di[edge[1]]}:{edge[2]}') s+=edge[2] print(f'权值:{s}')
时间: 2024-04-26 07:20:13 浏览: 125
Kruskal 算法
5星 · 资源好评率100%
这是一个Kruskal算法的实现,用于求解无向图的最小生成树。其中,n表示节点数,m表示边数,edges表示边的信息,每条边表示为一个列表,包含三个元素,分别是两个节点和边的权值。这段代码会将所有边按照权值从小到大排序,然后依次加入到生成树中,直到生成树的边数达到n-1为止。在加入每一条边之前,会判断这条边的两个节点是否已经连通,如果已经连通,则不加入该边,否则加入该边,并将这两个节点合并。最后输出生成树的边以及总权值。
阅读全文