图的最小子树算法--Kruskal和Prim

一、Kruskal

1.算法思想：每次挑最小的边生成子树，不断合并子树生成最小子树

2.算法步骤

（1）构造一个边类，放两个顶点和边长，还有一个isvisit用来知道该边是否被访问过

 class  Edge //  边 
 {
    String A;
    String B;
      int   length;
      boolean  isvisit= false  ;
      //  getter setter 
}

（2）初始化数据

        HashMap<String,String> Points= new  HashMap<> ();//放顶点，和顶点所属的子树群
        ArrayList <Edge> Edges= new  ArrayList<> ();//放边的信息
        Edges.add(  new  Edge("A","B",2 ));
        Edges.add(  new  Edge("A","D",4 ));
        Edges.add(  new  Edge("A","C",5 ));
        Edges.add(  new  Edge("B","C",4 ));
        Edges.add(  new  Edge("C","D",6 ));
        Edges.add(  new  Edge("B","E",5 ));
        Edges.add(  new  Edge("D","F",7 ));
        Edges.add(  new  Edge("C","E",3 ));
        Edges.add(  new  Edge("C","F",4 ));
        Edges.add(  new  Edge("E","F",1 ));
        printKruskal(Points,Edges);//调用函数
 

（3）写工具函数

selectMin()挑选最小边 

getGroup() 获得子树群信息，用来合并子树

 private   static  Edge selectMin(ArrayList<Edge>  edges) {
          int  min=999 ;
          int  index=-1 ;
          for ( int  i=0;i<edges.size();i++ )
        {
              if (edges.get(i).isvisit== false &&edges.get(i).getLength()< min)
            {
                index = i;
                min = edges.get(i).getLength();
            }
        }
        edges.get(index).setIsvisit(  true  );
          //  System.out.println("!"+edges.get(index).getA()+"<=>"+edges.get(index).getB()+" length="+edges.get(index).getLength()); 
         return   edges.get(index);
    }

 

 private   static  ArrayList<String> getGroup(String str,HashMap<String, String>  points) 
    {
        ArrayList <String> result= new  ArrayList<> ();
          for (Entry<String,String>  entry:points.entrySet())
        {
              if  (entry.getValue().equals(str))
            {
                result.add(entry.getKey());
            }
        }
          return   result;
    } 

（4）逻辑处理和输出结果

 private   static   void  printKruskal(HashMap<String, String> points,ArrayList<Edge>  edges) 
    {
        ArrayList <Edge> result= new  ArrayList<> ();
          while (result.size()<5 )
        {  
        Edge e = selectMin(edges);
          while (points.get(e.getA())!= null && points.get(e.getA()).equals(points.get(e.getB())))
        {
            e = selectMin(edges);
        }
          if (points.get(e.getA())== null &&points.get(e.getA())== null  )
        {
            points.put(e.getA(), e.getA());
            points.put(e.getB(), e.getA());
        }
          else   if (points.get(e.getA())== null  )
        {
            points.put(e.getA(), e.getB());
        }
          else   if (points.get(e.getB())== null  )
        {
            points.put(e.getB(), e.getA());
        }
          else  
        {
            ArrayList <String> groupB= getGroup(points.get(e.getB()),points);
              for  (String str:groupB)
            {
                points.put(str, e.getA());
            }
        }
        result.add(e);
        System.out.println(e.getA() +"<=>"+e.getB()+" length="+ e.getLength());
        }

    } 

3.结果截图

 二、Prim

1.算法思想：从一个顶点出发，不断挑选已有数可到达的最小边，直到生成最小生成树

2.算法步骤：

（1）构造边类：同上

（2）数据初始化：同上

（3）逻辑处理：

        ArrayList<Edge> result= new  ArrayList<> ();
        ArrayList <String> now= new  ArrayList<> ();//已有顶点
        now.add( "A"); //  从A出发 
         while (now.size()<6 )
        {
              int  min=999 ;
            Edge minEdge = null  ;
              for  (Edge e:edges)
            {
                  for ( int  i=0;i<now.size();i++ )
                {
                      if (now.get(i).equals(e.getA())|| now.get(i).equals(e.getB()))
                    {
                          if (!e.isIsvisit()&&e.getLength()< min)
                        {
                            min = e.getLength();
                            minEdge = e;
                        }
                    }
                }
            }
            minEdge.setIsvisit(  true  );
              if  (now.contains(minEdge.getA()))
            {
                now.add(minEdge.getB());
            }
              else  
            {
                now.add(minEdge.getA());
            }
            System.out.println(minEdge.getA() +"<=>"+minEdge.getB()+" length="+ minEdge.getLength());
            result.add(minEdge);
        } 

3.结果截图

 

查看更多关于图的最小子树算法--Kruskal和Prim的详细内容...