Kruskal 最小生成树算法

最小生成树—Prim算法和Kruskal算法,—primkruskal

Prim算法

1.概览

普Rim算法(Prim算法),图论中的一种算法,可在加权连通图里搜寻最小生成树。意即因而算法搜索到的边子集所构成的树中,不但包蕴了连通图里的持有终端(乌克兰(Ukraine)语:Vertex (graph
theory)),且其兼具边的权值之和亦为最小。该算法于1926年由捷克(Czech)物管理学家沃伊捷赫·亚尔Nick(波兰语:Vojtěch
Jarník)发掘;并在壹玖陆零年由花旗国计算机化学家Robert·普Rim(德文:罗Bert C.
Prim)独立意识;一九五八年,艾兹格·迪科斯彻再度开采了该算法。由此,在一些场馆,普Rim算法又被叫作DJP算法、亚尔尼克算法或普Rim-亚尔尼克算法。

 

2.算法简单描述

1).输入:叁个加权连通图,当中顶点集结为V,边集合为E;

2).初始化:Vnew =
{x},个中x为集结V中的任一节点(开端点),Enew = {},为空;

3).重复下列操作,直到Vnew = V:

a.在集合E中选取权值最小的边<u,
v>,在这之中u为群集Vnew中的成分,而v不在Vnew汇集当中,何况v∈V(纵然存在有多条满意前述标准即拥有同样权值的边,则可任意接纳个中之一);

b.将v加入集合Vnew中,将<u,
v>边参与集结Enew中;

4).输出:使用会集Vnew和Enew来描述所获得的最小生成树。

示例图演示:

图片 1

 

上面临算法的图例描述:

图例 说明 不可选 可选 已选(Vnew
 

此为原始的加权连通图。每条边一侧的数字代表其权值。

顶点D被任意选为起始点。顶点ABEF通过单条边与D相连。A是距离D最近的顶点,因此将A及对应边AD以高亮表示。 C, G A, B, E, F D
 

下一个顶点为距离DA最近的顶点。BD为9,距A为7,E为15,F为6。因此,FDA最近,因此将顶点F与相应边DF以高亮表示。 C, G B, E, F A, D
算法继续重复上面的步骤。距离A为7的顶点B被高亮表示。 C B, E, G A, D, F
 

在当前情况下,可以在CEG间进行选择。CB为8,EB为7,GF为11。E最近,因此将顶点E与相应边BE高亮表示。 C, E, G A, D, F, B
 

这里,可供选择的顶点只有CGCE为5,GE为9,故选取C,并与边EC一同高亮表示。 C, G A, D, F, B, E

顶点G是唯一剩下的顶点,它距F为11,距E为9,E最近,故高亮表示G及相应边EG G A, D, F, B, E, C

现在,所有顶点均已被选取,图中绿色部分即为连通图的最小生成树。在此例中,最小生成树的权值之和为39。 A, D, F, B, E, C, G

 

3.简约表明prim算法

反证法:假如prim生成的不是最小生成树

1).设prim生成的树为G0

2).借使存在Gmin使得cost(Gmin)<cost(G0)  
则在Gmin中存在<u,v>不属于G0

3).将<u,v>加入G0中可得贰个环,且<u,v>不是该环的最长边(那是因为<u,v>∈Gmin)

4).那与prim每趟改动最短边争持

5).故借使不树立,命题得证.

 

Kruskal算法

1.概览

Kruskal算法是一种用来搜索最小生成树的算法,由Joseph
Kruskal在一九五六年刊载。用来缓慢解决同样难题的还应该有Prim算法和Boruvka算法等。二种算法都是贪心算法的施用。和Boruvka算法差异的地点是,Kruskal算法在图中设有同样权值的边时也可能有效。

 

2.算法轻松描述

1).记Graph中有v个顶点,e个边

2).新建图Graphnew,Graphnew中具备原图中一律的e个顶点,但从没边

3).将原图Graph中持有e个边按权值从小到大排序

4).循环:从权值最小的边起初遍历每条边
直至图Graph中存有的节点都在同贰个连缀分量中

                if
那条边连接的多个节点于图Graphnew中不在同三个接入分量中

                                        
增添那条边到图Graphnew

示例图演示:

图片 2

 

图例描述:

图片 3

先是第一步,大家有一张图Graph,有若干点和边 

图片 4

 

将富有的边的长短排序,用排序的结果作为大家挑选边的根据。这里再次显示了贪心算法的酌量。能源排序,对一部分最优的能源拓展精选,排序完毕后,大家率先接纳了边AD。这样我们的图就改成了右图

 

图片 5

在余下的变中检索。大家找到了CE。这里边的权重也是5

图片 6

逐一类推大家找到了6,7,7,即DF,AB,BE。

图片 7

下边继续选择,
BC恐怕EF纵然现近年来长度为8的边是纤维的未选用的边。然而今后他们曾经连通了(对于BC能够经过CE,EB来连接,类似的EF能够透过EB,BA,AD,DF来三番五次)。所以不供给选取他们。类似的BD也一度连通了(这里上航海用体育场所的连通线用紫色代表了)。

谈到底就剩下EG和FG了。当然大家挑选了EG。最终成功的图正是右:

 

3.简短表明Kruskal算法

对图的极端数n做综合,注明Kruskal算法对私下n阶图适用。

汇总基础:

n=1,鲜明能够找到最小生成树。

综合进度:

假诺Kruskal算法对n≤k阶图适用,那么,在k+1阶图G中,大家把最短边的八个端点a和b做多少个联合操作,即把u与v合为三个点v’,把原本接在u和v的边都接到v’上去,那样就能够收获多个k阶图G'(u,v的统一是k+1少一条边),G’最小生成树T’能够用Kruskal算法获得。

咱俩作证T’+{<u,v>}是G的最小生成树。

用反证法,倘使T’+{<u,v>}不是最小生成树,最小生成树是T,即W(T)<W(T’+{<u,v>})。显著T应该满含<u,v>,不然,能够用<u,v>插手到T中,形成三个环,删除环上原有的即兴一条边,形成一棵更加小权值的生成树。而T-{<u,v>},是G’的生成树。所以W(T-{<u,v>})<=W(T’),也正是W(T)<=W(T’)+W(<u,v>)=W(T’+{<u,v>}),发生了争执。于是假使不树立,T’+{<u,v>}是G的最小生成树,Kruskal算法对k+1阶图也适用。

由数学归咎法,Kruskal算法得证。

 

上面选择java程序演示Prim算法:

代码如下:

package com.itheima.primer;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 最小生成树(普里姆算法(Prim算法))
 * @author zhangming
 * @date 2016/04/20
 */
public class MinTreePrimer {
    private static List<Vertex> visitedVertexs,leftedVertexs; //分别为添加到集合U中的节点集和剩余的集合V中的节点集
    private static List<Edge> searchEdges;

    //初始化图的信息
    public static void initGraph(Graph g){
        visitedVertexs = new ArrayList<Vertex>();
        leftedVertexs = new ArrayList<Vertex>();
        searchEdges = new ArrayList<Edge>();

        Scanner sc = new Scanner(System.in);
        System.out.print("输入顶点数: ");
        int vertexNumber = sc.nextInt();
        System.out.print("请输入边数: ");
        int edgeNumber = sc.nextInt();
        String[] allVertex = new String[vertexNumber];
        String[] allEdge = new String[edgeNumber];

        System.out.println("=================================");
        System.out.println("请输入各个顶点:");
        Scanner scanner = new Scanner(System.in);
        for(int i=0;i<vertexNumber;i++){
            System.out.print("顶点"+(i+1)+":");
            allVertex[i] = scanner.nextLine();
        }
        System.out.println("=================================");
        for(int i=0;i<edgeNumber;i++){
            System.out.print("输入边(Vi,Vj)中的顶点名称和权值W(如:A B 7): ");
            allEdge[i] = scanner.nextLine();
        }

        g.vertex = new Vertex[allVertex.length];
        g.edge = new Edge[allEdge.length];
        g.minWeight = 0;

        for(int i=0;i<allVertex.length;i++){
            g.vertex[i] = new Vertex();
            g.vertex[i].vName = allVertex[i];
            leftedVertexs.add(g.vertex[i]); //初始化剩余点集合
        }

        for(int i=0;i<allEdge.length;i++){
            g.edge[i] = new Edge();
            g.edge[i].startVertex = new Vertex();
            g.edge[i].endVertex = new Vertex();

            String edgeInfo[] = allEdge[i].split(" ");
            g.edge[i].startVertex.vName = edgeInfo[0];
            g.edge[i].endVertex.vName = edgeInfo[1];
            g.edge[i].weight = Integer.parseInt(edgeInfo[2]);
        }
    }

    public static void onChangeVertex(Vertex vertex){
        visitedVertexs.add(vertex); //添加初始节点,作为默认的开始节点
        leftedVertexs.remove(vertex);
    }

    public static Vertex findOneVertex(Graph g){
        int minValue = Integer.MAX_VALUE;
        Vertex findVertex = new Vertex();
        Edge findEdge = new Edge();

        for(int i=0;i<visitedVertexs.size();i++){
            for(int j=0;j<leftedVertexs.size();j++){
                Vertex v1 = visitedVertexs.get(i);
                Vertex v2 = leftedVertexs.get(j); //获取两个顶点的名称

                for(int k=0;k<g.edge.length;k++){
                    String startName = g.edge[k].startVertex.vName;
                    String endName = g.edge[k].endVertex.vName;

                    if((v1.vName.equals(startName) && v2.vName.equals(endName))
                ||(v1.vName.equals(endName) && v2.vName.equals(startName))){
                        if(g.edge[k].weight < minValue){
                            findEdge = g.edge[k];
                            minValue = g.edge[k].weight;
                            if(leftedVertexs.contains(v1)){ //会调用对象的equals方法比较对象,需重写equals方法
                                findVertex = v1;
                            }else if(leftedVertexs.contains(v2)){
                                findVertex = v2;
                            }
                        }
                    }
                }
            }
        }
        g.minWeight+= minValue;
        searchEdges.add(findEdge);

        return findVertex;
    }

    public static void prim(Graph g){
        while(leftedVertexs.size()>0){ //直到剩余节点集为空时结束循环
            Vertex findVertex = findOneVertex(g);
            onChangeVertex(findVertex);
        }
        System.out.print("\n最短路径包含的边: ");
        for(int i=0;i<searchEdges.size();i++){
            System.out.print("("+searchEdges.get(i).startVertex.vName+","+searchEdges.get(i).endVertex.vName+")"+" ");
        }
        System.out.println("\n最短路径长度: "+g.minWeight);
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        initGraph(g);
        onChangeVertex(g.vertex[0]);
        prim(g);
    }
}

/**
 * 顶点类Vertex
 */
class Vertex{
    String vName; //顶点的名称

    @Override
    public boolean equals(Object obj) {
        if(obj instanceof Vertex){
            Vertex vertex = (Vertex)obj;
            return this.vName.equals(vertex.vName);
        }
        return super.equals(obj);
    }
}

/**
 * 边类Edge
 */
class Edge{
    Vertex startVertex;
    Vertex endVertex;
    int weight;
}

/**
 * 图的存储结构
 */
class Graph{
    Vertex[] vertex; //顶点集
    Edge[] edge; //边集
    int minWeight; //最短路径
}

 

运行结果截图:

图片 8

 

http://www.bkjia.com/Javabc/1122414.htmlwww.bkjia.comtruehttp://www.bkjia.com/Javabc/1122414.htmlTechArticle最小生成树—Prim算法和Kruskal算法,—primkruskal
Prim算法 1.大概浏览 普Rim算法 (
Prim算法),图论中的一种算法,可在加权连通图里探寻最小生…

kruskal.h

kruskal.cpp

图片 9#pragma once
图片 10
图片 11#include <iostream>
图片 12#include <vector>
图片 13#include <algorithm>
图片 14#include <functional>
图片 15#include <set>
图片 16
图片 17
图片 18template<class Vertex_Type, class Edge_Type>
图片 19class Kruskal
图片 20图片 21…{
图片 22 typedef Kruskal<Vertex_Type,Edge_Type>  Self_Type ;
图片 23protected:
图片 24 struct Edge_t
图片 25图片 26 …{
图片 27  typedef typename Self_Type::Edge_t  Self_Type ;
图片 28  Vertex_Type v1,  v2 ;
图片 29  Edge_Type e ;
图片 30图片 31  Edge_t()…{}
图片 32  Edge_t(Vertex_Type & _v1,Vertex_Type & _v2,Edge_Type & _e) :
图片 33  v1(_v1),v2(_v2),e(_e)
图片 34图片 35  …{}
图片 36  Edge_t(const Edge_t & edge):v1(edge.v1),v2(edge.v2),e(edge.e)
图片 37图片 38  …{}
图片 39图片 40  Edge_t & operator=(const Edge_t & edge)…{ v1=edge.v1,v2=edge.v2,e=edge.e ;return *this ; }
图片 41图片 42  bool operator<(const Self_Type & other )const …{   return e<other.e ;   }
图片 43  //friend istream &  operator>>(istream & in, Self_Type & edge)
图片 44  //{ in>>edge.v1>>edge.v2>>edge.e ;   return in ;  }
图片 45 };
图片 46
图片 47 //
图片 48 struct Vertex_t
图片 49图片 50 …{
图片 51  Vertex_Type v ;
图片 52  Vertex_t * root ;
图片 53图片 54  Vertex_t()…{}
图片 55图片 56  Vertex_t(Vertex_Type & _v, Vertex_t * _r=0): v(_v),root(_r)…{}
图片 57图片 58  bool operator<(const Vertex_t & other ) const …{  return v<other.v ;   }
图片 59图片 60  bool isRoot(void) const    …{  return 0==root || root==this;    }
图片 61图片 62  bool isSingle(void) const   …{  return 0==root ;          }
图片 63 };
图片 64 //
图片 65 std::vector<Edge_t> Edges ;
图片 66 std::vector<Edge_t> resultEdges ;
图片 67 size_t edgeNum ;
图片 68 size_t vertexNum ;
图片 69 std::set<Vertex_t> VexSet ;
图片 70
图片 71public:
图片 72图片 73 Kruskal():edgeNum(0),vertexNum(0)…{}
图片 74图片 75 Kruskal(size_t vNum, size_t eNum): Edges(eNum),edgeNum(eNum),vertexNum(vNum)…{}
图片 76图片 77 Kruskal(size_t vNum, size_t eNum, Edge_t & default):Edges(eNum,default),edgeNum(eNum),vertexNum(vNum)…{}
图片 78图片 79 virtual ~Kruskal() …{}
图片 80图片 81 void setNum( size_t vNum, size_t eNum) …{   edgeNum=eNum,vertexNum=vNum ;   }
图片 82 virtual void sort(void)
图片 83图片 84 …{
图片 85  std::sort(Edges.begin(),Edges.end()) ;
图片 86 }
图片 87 virtual void input(std::istream & in)
图片 88图片 89 …{
图片 90  if(Edges.size()<edgeNum)
图片 91   Edges.resize(edgeNum) ;
图片 92  for(size_t i=0; i<edgeNum; ++i)
图片 93图片 94  …{
图片 95   in>>Edges[i].v1>>Edges[i].v2>>Edges[i].e; // you may change this
图片 96   VexSet.insert(Edges[i].v1) ;
图片 97   VexSet.insert(Edges[i].v2);
图片 98  }
图片 99 }
图片 100图片 101 friend std::istream &  operator>>(std::istream & in, Self_Type & object) …{ object.input(in) ;  return in ; }
图片 102 
图片 103 friend std::ostream &  operator<<(std::ostream & out, Self_Type & object)
图片 104图片 105 …{
图片 106  out<<“vertex_1   vertex_2   edge  ” ;
图片 107  std::vector<Edge_t>  & edges=object.resultEdges ;
图片 108  for(size_t i =0; i<edges.size() ; ++i)
图片 109   out<<edges[i].v1<<” “<<edges[i].v2<<” “<<edges[i].e<<std::endl ;
图片 110  return out ;
图片 111 }
图片 112
图片 113 
图片 114
图片 115 Vertex_t & findRoot(Vertex_t & v )
图片 116图片 117 …{
图片 118  if (v.isRoot())
图片 119   return v ;
图片 120  return findRoot(*v.root) ;
图片 121 }
图片 122
图片 123 virtual bool isInSameSet(Vertex_Type & _v1, Vertex_Type & _v2)
图片 124图片 125 …{
图片 126  Vertex_t &  v1=findRoot(*VexSet.find(_v1)) ;
图片 127  Vertex_t &  v2=findRoot(*VexSet.find(_v2)) ;
图片 128
图片 129  if(v1.v==v2.v)
图片 130   return true ;
图片 131  if(v1.isSingle())
图片 132   v1.root=&v2 ;
图片 133  else
图片 134   v2.root=&v1 ;
图片 135
图片 136  return false;
图片 137 }
图片 138 void run(void)
图片 139图片 140 …{
图片 141  sort() ;
图片 142  for(size_t i=0; i<edgeNum; ++i)
图片 143图片 144  …{
图片 145   Vertex_Type & v1=Edges[i].v1 ;
图片 146   Vertex_Type & v2=Edges[i].v2 ;
图片 147   if( ! isInSameSet(v1,v2) )
图片 148    resultEdges.push_back( Edges[i] );
图片 149  }
图片 150 }
图片 151};
图片 152
图片 153 
图片 154
图片 155

图片 156
图片 157#include “kruskal.h”
图片 158#include <fstream>
图片 159#include <iostream>
图片 160#include <vector>
图片 161#include <algorithm>
图片 162#include <functional>
图片 163#include <set>
图片 164#include <string>
图片 165
图片 166using namespace std ;
图片 167
图片 168struct edg_t 
图片 169…{
图片 170 int vec1,vec2, weight ;
图片 171 friend istream &  operator>>(istream & in, edg_t & edg)
图片 172 …{
图片 173  in>>edg.vec1>>edg.vec2>>edg.weight ;
图片 174  return in ;
图片 175 }
图片 176};
图片 177
图片 178bool cmp(const edg_t & left, const edg_t & right )
图片 179…{
图片 180 return left.weight<right.weight ;
图片 181}
图片 182
图片 183void kruskal(fstream & fin) ;
图片 184size_t findRoot(vector<int> & vec, int index) ;
图片 185
图片 186template<class vetex_type, class edge_type>
图片 187void test(istream &  fin)
图片 188…{
图片 189 int vecNum, edgNum ;
图片 190 fin>>vecNum>>edgNum ;
图片 191 …{
图片 192  Kruskal<vetex_type,edge_type> sun(vecNum, edgNum) ;
图片 193  fin>>sun ;
图片 194  sun.run() ;
图片 195  cout<<sun ;
图片 196 } 
图片 197 getchar() ;
图片 198}
图片 199
图片 200int _tmain(int argc, _TCHAR* argv[])
图片 201…{
图片 202 fstream fin(“data.txt”,ios::in) ;
图片 203 test<string,int>(fin) ;
图片 204 test<char,int>(fin) ;
图片 205 test<int,int>(fin) ;
图片 206
图片 207 cout<<”
 —————   ” ;
图片 208
图片 209 kruskal(fin) ;
图片 210 getchar() ;
图片 211 fin.close() ;
图片 212 return 0;
图片 213}
图片 214
图片 215// find the root of the set with the vec[index] in it
图片 216size_t findRoot(vector<int> & vec, int index)
图片 217…{
图片 218 if(index>=vec.size())
图片 219  return 0 ;
图片 220 if( vec[index]==-1) // is it a root ?
图片 221  return index ;
图片 222 return findRoot(vec,vec[index]) ;
图片 223}
图片 224//
图片 225void kruskal(fstream & fin)
图片 226…{
图片 227 if(!fin)
图片 228  cout<<“Error in open file! “;
图片 229 //cout<<fin.rdbuf() ;
图片 230 int VecNum, EdgNum ;
图片 231 fin>>VecNum>>EdgNum ;
图片 232 vector<edg_t>  edgVec(EdgNum) ;
图片 233 vector<int> resultVec(VecNum,-1) ;
图片 234 for(int i=0; i<EdgNum; i++)
图片 235  fin>>edgVec[i] ;
图片 236
图片 237 //step 1 : sort by edge
图片 238 sort(edgVec.begin(), edgVec.end(), ptr_fun(cmp));
图片 239
图片 240 // step 2: for each edge in the sorted @edgVec, 
图片 241 // select it’s two vertex if they are not in the same set and union the two set
图片 242 for(int i=0; i<EdgNum; i++)
图片 243 …{
图片 244  edg_t &  edg=edgVec[i] ;
图片 245
图片 246  // find the two set of each vertex of the edge
图片 247  size_t lRoot=findRoot(resultVec,edg.vec1-1);
图片 248  size_t rRoot=findRoot(resultVec,edg.vec2-1);
图片 249  if(lRoot==rRoot) // are they in the same set ?
图片 250   continue ;
图片 251  // here we union the two set
图片 252  if(-1==resultVec[lRoot])
图片 253   resultVec[lRoot]=rRoot ;
图片 254  else
图片 255   resultVec[rRoot]=lRoot ;
图片 256
图片 257  cout<<edg.vec1<<” “<<edg.vec2<<” “<<edg.weight
图片 258   <<endl ; // print the result
图片 259 }
图片 260}
图片 261 
图片 262
图片 263 
图片 264
图片 265

data.txt

9 14
sda erb 4
sda gggh 8
erb itc 8
erb gggh 11
itc qwed 7
itc xcvf 4
itc asdfi 2
qwed erte 9
qwed xcvf 14
erte xcvf 10
xcvf dfgg 2
dfgg gggh 1
dfgg asdfi 6
gggh asdfi 7

9 14
a b 4
a h 8
b c 8
b h 11
c d 7
c f 4
c i 2
d e 9
d f 14
e f 10
f g 2
g h 1
g i 6
h i 7

9 14
1 2 4
1 8 8
2 3 8
2 8 11
3 4 7
3 6 4
3 9 2
4 5 9
4 6 14
5 6 10
6 7 2
7 8 1
7 9 6
8 9 7

9 14
1 2 4
1 8 8
2 3 8
2 8 11
3 4 7
3 6 4
3 9 2
4 5 9
4 6 14
5 6 10
6 7 2
7 8 1
7 9 6
8 9 7

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图