首页 > 代码库 > 最小生成树-Kruskal算法
最小生成树-Kruskal算法
因为这个算法比较简单，网上的内容页比较丰富，这里就简单说了。Kruskal算法的核心思想是以“边”（edge）为主角，以此把序把短边放到集合当中，只选取那些不构成环的，直到所有的顶点都存在集合当中。
该算法的理论依据就是最小生成树的性质：
（例如：v∈V-U），且（u，v）具有最小权值，则最小生成树性质：设G=(V，E）是一个连通网络，U是顶点集V的一个非空真子集。若(u，v）是G中一条“一个端点在U中（例如：u∈U），另一个端点不在U中的边一定存在G的一棵最小生成树包括此边（u，v）。
总结来说就是：最小生成树一定会通过小权重的边，这点和我们的直观认知是一致的。
这里想把几个关键的点发散一下：
1. 边的排序。
排序算法有多种，偷懒的话就用现成的库，不然就自己挑一个顺手的。
2. 判断是否连通。
连通问题在《算法导论C语言实现》中放在第一章。核心思想是用一个数组来表明各个点，比如点0-3，初始化为[0, 1,2,3]，这4个点各不相连，如果把点0和3连接，可以把数组变成[3,1,2,3]。数字看到0和3是连接的，程序上呢，直接下标可以看到a[a[0]] = 3,同时呢，a[3]=3。是不是就像树一样，从叶子节点回到根。
后面上代码：
有部分内容不在代码中，比如graph的封装，还有判断是否连通的Connector多不在下面的代码里。
#encoding:utf-8require ‘./graph.rb‘def build_tree graph = Graph.new [0,1,2,3,4,5,6].each { |vt| graph.add_v(Vertex.new vt) } newg = Connector.new graph.vertexes.size # 三元数组，分别表示顶点,顶点，权值 [[0, 1, 7], [0, 3, 5], [1, 3, 9], [1, 2, 8], [2, 4, 7], [0, 4, 5], [3, 4, 15], [3, 5, 6], [4, 5, 8], [4, 6, 9], [5, 6, 11]].each { |edge| graph.add_e(Edge.new edge[0], edge[1], edge[2]) } # Kruskal Algorithm require ‘set‘ vs = Set.new graph.vertexes.each { |v| vs.add v.id } edges = graph.edges.clone edges.sort_by! { |edge| edge.weight } puts "Edges is #{edges}" des = Set.new path = Set.new # If vs is empty, loop finish while TRUE # vertex set, edge set if edges.nil? or edges.size.equal? 0 break end # pick shortest edge shortest = edges[0] # puts "Shortes #{shortest}" edges = edges[1..-1] if newg.is_connect shortest.from, shortest.to #if newg.connected? shortest.to, shortest.from next else des.add shortest.from des.add shortest.to vs.delete shortest.from vs.delete shortest.to path.add shortest newg.connect shortest.from, shortest.to end if vs.empty? break end end total = 0 path.each { |edge| puts edge.to_s; total += edge.weight } puts totalendbuild_tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。