最小生成树算法(Prim & Kruskal)

Kruskal算法:

 

MST_kruskal_en

 

 

public class Kruskal {

    public class data{
        public int start;//开始点
        public int end;//结束点
        public int val;
        data(){
           start = 0;
            end = 0;
            val  = Integer.MAX_VALUE;
        }
        public void printout(){
            System.out.println(start +"---"+ end+" val:"+val);
        }
    }

    public void kruscal(int graph[][]){
        int n = graph.length;
        data []edges = new data[n * (n-1) /2];//生成n*(n-1)/2条边的存储对象


        int edgeCount = 0;//边数最多n * (n-1) /2
        for (int i = 0; i < graph.length; i++) {
            for (int j = i+1; j < graph.length; j++) {
                if (graph[i][j] > 0 && graph[i][j] < Integer.MAX_VALUE){

                    edges[edgeCount] = new data();
                    edges[edgeCount].start = i;
                    edges[edgeCount].end = j;
                    edges[edgeCount].val = graph[i][j];
                    edgeCount++;
                }
            }
        }

        sortEdges(edges, 0, edgeCount-1);
        ArrayList<data> result = kruscalMst(edges, edgeCount,n);
      //  printEdges(result);



    }
/**
 *
 * 根据已经排好序的边,以不成环为原则,选出前n-1条边
 * */
    public ArrayList<data> kruscalMst(data[] edges, int count, int vertex) {

        ArrayList<data> edge = new ArrayList<data>();
        LinkedList<HashSet<Integer>> u = new LinkedList<HashSet<Integer>>();
        //初始化
        for (int i = 0; i < vertex; i++) {
            u.add(new HashSet<Integer>());
            u.get(i).add(i);//集合0是a0,集合1是a1,集合2是a2
        }


        for (int i = 0; i < count; i++) {
            if(!inSameSet(u,edges[i])){
                edge.add(edges[i]);
            }
        }
    return edge;
    }
/**
 * 判断边edge中的两个点,是否已经在一个集合中
 * */
    private boolean inSameSet(LinkedList<HashSet<Integer>> u, data edge) {
        int start = edge.start;
        int end = edge.end;
        int together1 = -1;
        int together2 = -1;

        for (HashSet<Integer> set : u){
            if(set.contains(start) ){
                together1 = u.indexOf(set);
            }
            if(set.contains(end) ){
                together2 = u.indexOf(set);
            }
        }
        if (together1 != together2){
            u.get(together1).addAll(u.get(together2));//第二个集合放到第一个集合中
            u.remove(together2);//删除第二个集合

            return false;
        }else{
            return true;
        }


    }


    private void printEdges(ArrayList<data> edges) {
        for (data d :edges) {
            d.printout();
        }

    }

    /**
     * quick sort,按边的权值排序
     * */
    private void sortEdges(data[] edges, int left, int right) {

        if (left < right){
            int i = left;
            int j =right;
            int tmp = edges[left].val;
            int tmpStart = edges[left].start;
            int tmpEnd = edges[left].end;

            while (i < j){
                while (i < j && tmp <= edges[j].val)
                    j--;
                if (i < j){
                    edges[i].val = edges[j].val;
                    edges[i].start = edges[j].start;
                    edges[i].end = edges[j].end;
                    i++;
                }

                while (i < j && tmp > edges[i].val)
                    i++;
                if (i < j){
                    edges[j].val = edges[i].val;
                    edges[j].start = edges[i].start;
                    edges[j].end = edges[i].end;
                    j--;
                }
            }

            edges[i].val = tmp;
            edges[i].start = tmpStart;
            edges[i].end = tmpEnd;

            sortEdges(edges , left, i-1);
            sortEdges(edges, i+1, right);

        }
    }

}

 

 

 

Prim算法:

Prim-algorithm-animation-2

 

 

 

/**
 * Created by chris on 15/5/2.
 * 求最小生成树的辅助类
 */
public class Closedge {
    private  int lowcost;//最小权值
    private  int vertex;

    Closedge(){

        vertex = 0;
        lowcost = Integer.MAX_VALUE;
    }

    public int getLowcost() {
        return lowcost;
    }

    public int getVertex() {
        return vertex;
    }

    public void setLowcost(int lowcost) {
        this.lowcost = lowcost;
    }

    public void setVertex(int vertex) {
        this.vertex = vertex;
    }
}



package com.company;

import java.util.ArrayList;

/**
 * Created by chris on 15/5/1.
 * Prim algorithm
 */
public class Prim {

    /**
     *   Prim 最小生成树算法,
     * @param adjMatrix 临接矩阵表示图
     * @param u 存储生成的最小树,初始值输入是一个起点
     * @param closedge 辅助,用来存放某点点最低权值
     * */
    void miniSpanTreePrim(int adjMatrix[][], ArrayList<Integer> u, Closedge closedge[]){
        closedge[u.get(0)].setLowcost(0);//初始化,u只有一个点,设置这个点的最低权值是 0

        for (int i = 0; i < adjMatrix.length; i++) {
            if (i != u.get(0)) {
                closedge[i].setVertex(u.get(0));//对v-u中的顶点i,初始化closedge[i]
                closedge[i].setLowcost(adjMatrix[u.get(0)][i]);
            }
        }

        for (int i = 1; i <= adjMatrix.length-1; i++) {//找 n-1条边
            int minVertex = minimumOfCloseEdge(closedge);//找相邻边中,最小权值的点
            u.add(minVertex);
            //System.out.println(closedge[minVertex].getVertex() +"---"+ minVertex);
            closedge[minVertex].setLowcost(0);
            //在 minVertex并入 u 点后,更新closedge[i]
            for (int j = 0; j < adjMatrix.length; j++) {
                //如果u中不包含 j 点,就看刚才添加到u中的minVertex点到j点的权值是否更小

                if (!u.contains(j)
                    && adjMatrix[minVertex][j]!=0
                    && adjMatrix[minVertex][j] < closedge[j].getLowcost() ){
                    closedge[j].setLowcost(adjMatrix[minVertex][j]);
                    closedge[j].setVertex(minVertex);
                }
            }
        }
   // printArrayList(u);
    }
/**
 * 输出集合中vertex的顺序
 * */
    private void printArrayList(ArrayList<Integer> u) {
        for (Integer i : u){
            System.out.print(i + ",");

        }
        System.out.println();
    }
/**
 * 找到辅助数组中的最小正数
 * */
    private int minimumOfCloseEdge(Closedge[] closedge) {
        int min = closedge[0].getLowcost();
        int minPos = 0;

        for (int i = 1; i < closedge.length; i++) {
            if (min == 0 && closedge[i].getLowcost()!=0
            || closedge[i].getLowcost()!=0 && min > closedge[i].getLowcost()){
                minPos = i;
                min = closedge[i].getLowcost();
            }
        }
        return minPos;
    }
}

 

Tagged on:

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据