联系我们 - 广告服务
您的当前位置:官网首页 > 资讯 > 热评 >

python最小生成树kruskal与prim算法详解

来源: 编辑: 时间:2019-10-03
导读: kruskal算法基本思路:先对边按权重从小到大排序,先选取权重最小的一条边,如果该边的两个节点均为不同的分量,则加入到最小生成树,否则计算下一条边,直到遍历完......

kruskal算法基本思路:先对边按权重从小到大排序,先选取权重最小的一条边,如果该边的两个节点均为不同的分量,则加入到最小生成树,否则计算下一条边,直到遍历完所有的边。

prim算法基本思路:所有节点分成两个group,一个为已经选取的selected_node,一个为candidate_node,首先任取一个节点加入到selected_node,然后遍历头节点在selected_node,尾节点在candidate_node的边,选取符合这个条件的边里面权重最小的边,加入到最小生成树,选出的边的尾节点加入到selected_node,并从candidate_node删除。直到candidate_node中没有备选节点。

#coding=utf-8
class graph:
 def __init__:
 self.maps = maps
 self.nodenum = self.get_nodenum
 self.edgenum = self.get_edgenum
 def get_nodenum:
 return len
 def get_edgenum:
 count = 0
 for i in range:
 for j in range:
 if self.maps[i][j] 0 and self.maps[i][j] 9999:
 count += 1
 return count
 def kruskal:
 res = []
 if self.nodenum = 0 or self.edgenum self.nodenum-1:
 return res
 edge_list = []
 for i in range:
 for j in range:
 if self.maps[i][j] 9999:
 edge_list.append#按[begin, end, weight]形式加入
 edge_list.sort#已经排好序的边集合
 group = [[i] for i in range]
 for edge in edge_list:
 for i in range):
 if edge[0] in group[i]:
 m = i
 if edge[1] in group[i]:
 n = i
 if m != n:
 res.append
 group[m] = group[m] + group[n]
 group[n] = []
 return res
 def prim:
 res = []
 if self.nodenum = 0 or self.edgenum self.nodenum-1:
 return res
 res = []
 seleted_node = [0]
 candidate_node = [i for i in range]
 while len 0:
 begin, end, minweight = 0, 0, 9999
 for i in seleted_node:
 for j in candidate_node:
 if self.maps[i][j] minweight:
 minweight = self.maps[i][j]
 begin = i
 end = j
 res.append
 seleted_node.append
 candidate_node.remove
 return res
凯发vip网址max_value = 9999
row0 = [0,7,max_value,max_value,max_value,5]
row1 = [7,0,9,max_value,3,max_value]
row2 = [max_value,9,0,6,max_value,max_value]
row3 = [max_value,max_value,6,0,8,10]
row4 = [max_value,3,max_value,8,0,4]
row5 = [5,max_value,max_value,10,4,0]
maps = [row0, row1, row2,row3, row4, row5]
graph = graph
print
print)
print
print)
print
print)

初始的图如下。

运行结果如下。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持萬仟网。

责任编辑:

打赏

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

上一篇:pyqt5的QWebEngineView 使用模板的方法
下一篇:没有了

网友评论:

在“\templets\demo\comments.htm”原来的内容全部删除,插入第三方评论代码,如果不需要评论功能,删除comments.html里面的内容即可
推荐使用友言、多说、畅言(需备案后使用)等社会化评论插件

Copyright © 2018 凯发vip凯发vip-凯发vip网址-凯发官网 All Rights Reserved Power by DedeCms
本站所有资讯来源于网络 如有侵权请联系QQ:9490489
Top