图的最小子树算法--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.结果截图