最小生成树之普利姆算法与克鲁斯卡尔算法(贪心算法)

最小生成树之普利姆算法与克鲁斯卡尔算法(贪心算法)

最小生成树(贪心算法)

概念

  • 一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。
  • 连通图有多种连接方式,而其中最小的连通图,就是最小生成树
  • 连通图分为:无向、有向
    • 无向连通图:所以顶点相连,但各个边都没有方向
    • 有向连通图:边有方向

1.普利姆算法(Prim)—–最近顶点策略

  • 策略:选择图中的一个顶点作为起始点,每一步贪心选择不在当前生成树中的最近顶点加入生成树中,直到所有顶点都加入到树中。

  • 算法如下:

    (1)、假如G为无向连通带权图,每两个相邻节点构成一个带权边,其值设为:权值。即:(所有每相邻的两个节点都有各自的权值,只是权值大小不同)

    (2)、设集合 W和D,W用于存放G的最小生成树的顶点集合,D存放G的最小生成树的权值集合

    (3)、选中G的一个节点 (其索引为data-0) 作为初值,从顶点data0开始构建最小生成树。集合D的初值为D{}。

    (4)、标记W[data0]=1.表示标记已被选中的节点

    (5)、data0节点找出周围相邻,且带权边最小的节点(其索引为data-n)。

    (6)、将节点data-n加入集合W。标记W[data-n]=1;将带权边(data0,data-n)加入集合D

    (7)、重复上面步骤

  • 图解步骤:

    (1)、无向连通图

(2)、以节点A开始延申:发现(A,G)间的权值最小,于是选中G为连通点

(3)、以A、G节点为顶点找与之相邻的最小权值边:发现(G,B)间的带权边值最小,选中B

(4)、又以 A、G、B节点为顶点找与之相邻的最小权值边:发现(G,E)间的带权边值最小,选中E

(5)、又以 A、G、B、E节点为顶点找与之相邻的最小权值边:发现(B,A)与(E,F)间的带权边值最相同且最小,但A和B节点都是已使用过的节点,所以选中 F 节点

(6)、依次选择,得到最后的最小生成树

代码如下:


import java.util.Arrays;

/*
贪心策略:最小生成树-普里姆算法
       :在包含n个顶点的无向连通图中,找出只有(n-1)条边且包含n个顶点的连通子图。使其形成最小连通子图。连通子图不能出现回路
分析:
    1.设置集合 W和集合 D 。其中W存入的是无向连通图中最小生成树的顶点集合;D存入的是最小生成树每相邻两个顶点之间的连接边的集合
    2.另集合W的初值为 W{w0}(即从w0顶点开始构建最小生成树),另集合D初始值为 D{}
    3.设V为还未被选中的顶点。
    4.从w与v=V-W 中组成的所有带权边中选出最小的带权边(wn,vn).
    5.将顶点vn加入集合W中。此时集合W{wn,vn},集合D{(wn,vn)}
    6.重复上面步骤,直到V中所有顶点都加入到了W中,边有n-1条带权边。结束
代码:探讨修路问题
 */
public class test1 {
    public static void main(String[] args) {
        //所有节点
    char[] ndata=new char[]{"A","B","C","D","E","F","G"};
        //获取节点个数
        int nodes = ndata.length;
        //邻接矩阵.用较大的数10000表示两点不连通
        int[][] ndlenght=new int[][]{
                //A   ,B,C,  D  ,  E  ,  F  ,G
                {10000,5,7,10000,10000,10000,2},    //A
                {5,10000,10000,9,10000,10000,3},    //B
                {7,10000,10000,10000,8,10000,10000},//C
                {10000,9,10000,10000,10000,4,10000},//D
                {10000,10000,8,10000,10000,5,4},    //E
                {10000,10000,10000,4,5,10000,6},    //F
                {2,3,10000,10000,4,6,10000},        //G
                                                };
        //创建图对象
        Chart chart=new Chart(nodes);
        //创建生成数对象
        MinTree mt=new MinTree();
        //创建邻接矩阵
        mt.creathart(chart,nodes,ndata,ndlenght);
        //获取矩阵
       // mt.dischart(chart);
        mt.Prim(chart,0);


    }

}

/*
第二步:
创建生成树对象
 */
class MinTree{
    /**
     * 创建邻接矩阵
     * @param chart :图对象
     * @param nodes :节点个数
     * @param ndata :存放节点数据
     * @param ndlenght  :带权边
     */
    public void creathart(Chart chart,int nodes,char[] ndata,int[] [] ndlenght){
        //i:已经被选中的节点,ndata[i0]就是为初值,ndata[0]节点开始生成树。一共有nodes个
        for (int i=0;i<nodes;i++){
            //将当前已被选的节点存入图对象的ndata中
            chart.ndata[i]=ndata[i];
            //j:还未被选中的节点
            for (int j=0;j<nodes;j++){
                //将所有可能两两连接的节点组合,存入图对象的邻接矩阵中
                chart.ndlenght[i][j]=ndlenght[i][j];
            }
        }
    }

    //显示图矩阵
    public void dischart(Chart chart){
        for (int[] link:chart.ndlenght){
            System.out.println(Arrays.toString(link));
        }
    }


    /**
     * 普里姆算法:
     *    最小生成树
     * @param chart:图
     * @param v :初值
     */
    public void Prim(Chart chart,int v){
        //存放已被选中的节点,初始都为0
        int[] ondata=new int[chart.nodes];
        //标记初值节点已被选中,1(表示被选中了的)
        ondata[v]=1;
        //设即将相连的两个节点下标为 index1、index2。由于还没有存入,所以初始为-1
        int index1=-1;
        int index2=-1;
        //由于还不知道第一个边长为多少,所以先虚拟设置一个最大带权边长。后面后被替换的
        int max=10000;
        //k:表示最多生成(n-1)条带权边
        for (int k=1;k<chart.nodes;k++){
            //i:表示以被选中的节点;j:还未被选中的节点
            for (int i=0;i<chart.nodes;i++){
                for (int j=0;j<chart.nodes;j++){
                    if (ondata[i]==1&&ondata[j]==0&&chart.ndlenght[i][j]<max){
                        max=chart.ndlenght[i][j];
                        index1=i;
                        index2=j;
                    }
                }
            }
            System.out.println("节点:<"+chart.ndata[index1]+","+chart.ndata[index2]+">,==>带权边长:"+max);
            //将当前节点标记为以访问使用的节点
            ondata[index2]=1;
            //重置max
            max=10000;
        }

    }

}

/*
第一步:
创建图对象
 */
class Chart{
    int nodes;  //图中节点个数
    char[] ndata;   //存放节点数据
    int[] [] ndlenght;  //存放带权边。也是邻接矩阵

    //构造器
    public Chart(int nodes) {
        this.nodes = nodes;
        //初始化,数组长度为nodes(节点个数)
        ndata=new char[nodes];
        //初始化,矩阵为nodes行nodes列
        ndlenght=new int[nodes][nodes];
    }
}

结果:

2.,克鲁斯卡尔算法(Kruskal)—-最短边策略

  • 策略:每一次贪心的选择从剩下的边中最小的边且不产生环路的,加入到已选边的集合中。直到所有顶点都加入进来。

  • 按照权值从小到大选择n-1条边,并且这些边不构成环路。

  • 算法如下:

    (1)、构建有n个顶点的无边连通图 W ,

    2)、对无向连通图 H 中的各个带权边从小到大排序

    (3)、依次从小到大将 H 中的带权边加入到 W中(期间不能构成环路

  • 算法图解及判断环路:

    • 环路:已加入加入到无边联通图中的顶点的终点不能相同

    • 终点:将所有顶点从小到大排序后,某个顶点的终点就是”与它相连的最大的顶点”;

    • (1)、无边连通图 W。与无向连通图 H1:顶点以排序;2.权值以排序

      • 顶点的终点:此时由于还没有加入。所以W中所有的各个顶点的终点是自己本身

  • (2)、H中从小到大排序后的边依次加入 W中。

    • (2.1)、第一次:<A,C>=4,

    • 顶点的终点:因为顶点是已排序为{A,B,C,D},而目前加入到W中的只有{A,C}。所以A与C连通的最大顶点是:A—>C;C—>C

- (2.2)、第二次:<B,D>=5,

- 顶点的终点:此时**W**中有{A,C},{B,D}。由于目前{B,D}还没有与{A,C}连通,所以B与D连通的最大顶点是:B--->D;D--->D,

- (2.3)、第三次:<C,D>=6,这里虽然前面C与D被加入过,但它们的终点却不同。

- 顶点的终点:此时**W**中有{A,C},{B,D},{C,D}。由于{C,D}的加入导致{A,B,C,D}相互连接,所最大顶点是:A--->D;B--->D;C--->D;D--->D,

- (2.4)、第四次:<A,D>=7。由于前面得出A,与D的最大顶点(终点)相同为D,如果加入会构成环路。所以不能加入.跳过此边,加入下一条边

- (2.5)、第五次:<A,B>=8。由于前面得出A,与B的最大顶点(终点)相同为D,如果加入会构成环路。所以不能加入。所以加入下一条边,发现没有,所有边都已加入到了。
  • (3)、注意:在(2.3)时。其实所有顶点都已加入到了W中,所以就不需要判断后面的了。后面的结论只是为了说明终点与环路。

  • 代码如下:


import java.util.Arrays;

/**
 * 最小生成树:克鲁斯卡尔算法
 * 将无向连通图中的各个边从小到大排序,依次放入无边连通图中(不能出现环路)
 */
public class test1 {

    private int geshu;  //边的个数
    private char[] data; //存放节点
    private int[][] allquanzhi;   //存放带权边,邻接矩阵
    //标记不能相连通的两个节点,即不相邻的两个节点所形成的带权边。为Integer最大值
    private static final int maxlen = Integer.MAX_VALUE;

    public static void main(String[] args) {
      //  char[] data={"A","B","C","D","E"};
//        int[][] allquanzhi={
//                {0,20,maxlen,60,15},
//                {20,0,42,maxlen,maxlen},
//                {maxlen,42,0,30,maxlen},
//                {60,maxlen,30,0,23},
//                {15,maxlen,maxlen,23,0},
//                };
        char[] data={"A","B","C","D"};
        int[][] allquanzhi={
                {0,8,4,7},
                {8,0,maxlen,5},
                {4,maxlen,0,6},
                {7,5,6,0}
                    };
        test1 t=new test1(data,allquanzhi);
        //打印矩阵
        t.dayinjuzheng();
        Bian[] bians=t.andbian();
        System.out.println("排序前的边集合"+Arrays.toString(bians));
        t.biansort(bians);
        System.out.println("排序后的边集合"+Arrays.toString(bians));
        t.KrusKal();

    }

    //定义构造器
    public test1(char[] data, int[][] allquanzhi) {
        //初始化顶点数
        int spotgeshu = data.length;
        //初始化顶点(节点)
        this.data = data;
        //初始化 边
        this.allquanzhi = allquanzhi;
        //统计边的个数
        for (int i = 0; i < spotgeshu; i++) {
            for (int j = i+1; j < spotgeshu; j++) {
                if (this.allquanzhi[i][j] < maxlen) {
                    geshu++;
                }
            }
        }
    }

    //打印邻接矩阵
    public void dayinjuzheng() {
        System.out.println(geshu);
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data.length; j++) {
                //格式化输出
                System.out.printf("%15d	", +allquanzhi[i][j]);
            }
            System.out.println();
        }
    }


    /*
    对边排序:冒泡《从小到大》
     */
    public void biansort(Bian[] bian){
        for (int i=bian.length-1;i>0;i--){
            for (int j=0;j<i;j++){
                if (bian[j].bianquanzhi>bian[j+1].bianquanzhi){
                    Bian temp=bian[j];
                    bian[j]=bian[j+1];
                    bian[j+1]=temp;
                }
            }
        }
    }

    /*
    判断顶点是否存在
    返回顶点的索引
     */
public  int ismbian(char ch){
    for (int i=0;i<data.length;i++){
        if (data[i]==ch){
            return i;
        }
    }
    //如果ch不是顶点就返回-1
    return -1;
}

/*
将所以相邻边存入Bian[]中
 */
public Bian[] andbian(){
    int index=0;
    Bian[] bians=new Bian[geshu];
    for (int i=0;i<data.length;i++){
        for (int j=i+1;j<data.length;j++){
            if (allquanzhi[i][j]!=maxlen){
                bians[index++]=new Bian(data[i],data[j],allquanzhi[i][j]);
            }
        }
    }
    return bians;
}


/*
获取小标为i的顶点的终点,用于判断两个顶点的终点是否相同
star:存入的是顶点的终点的索引,初始化为{0,0,0,0,...},
i:顶点的索引
 */
public int getEnd(int[] star,int i){
    //动态的判断以此顶点的索引,
    //相连的前一个顶点的终点索引就是后一个顶点的索引
    //由于第一次的顶点的终点是自己的索引都
    //如果在star中找到了终点
    while (star[i]!=0){
        //就将此终点的值变为新的顶点的索引(找到此索引对应的顶点的终点,直到新的索引在star中没有找到终点,即为0,就将此索引返回为最初始的节点的终点索引)
        i=star[i];
    }
    //返回为终点
    return  i;
}


/*
最小生成树克鲁斯卡尔算法
 */
public  void KrusKal(){
    int index=0;    //最后结果数组的索引
    //存放最小生成树每个顶点的终点
    int[] star=new  int[geshu];
    //保存最终生成树
    Bian[] fin=new  Bian[geshu];
    //获取边的集合
    Bian[] andnewbian = andbian();
    //对所有边进行排序
    biansort(andnewbian);
    //遍历边集合。在判断的同时判断是否形成回路
    for (int i=0;i<geshu;i++){
        //上面andbian存放获得的边的类:bians[index++]=new Bian(data[i],data[j],allquanzhi[i][j]);
        //获取第一边的起点(顶点),对应的是data[i]
        int h1=ismbian(andnewbian[i].da1);
        //获取第一条边的第二个顶点,对应的是data[j]
        int h2=ismbian(andnewbian[i].da2);
        //获取第一个顶点的终点
        int end = getEnd(star, h1);
        //获取第二个顶点的终点
        int end1 = getEnd(star, h2);
        //判断回路:如果没有构成回路
        if (end!=end1){
            //设置end1为已有生成数的终点
            star[end]=end1;
            //此时最终生成树有了一条边
            fin[index++]=andnewbian[i];
        }
    }
    System.out.println("最后生成树:"+Arrays.toString(fin));
    System.out.println("最小生成树:");
    for (int i=0;i<index;i++){
        System.out.println(fin[i]);
    }
}

}


/*
边类
 */
class Bian{
    //组成一条边的两个节点
    char da1;
    char da2;
    //边权值
    int bianquanzhi;

    public Bian(char da1, char da2, int bianquanzhi) {
        this.da1 = da1;
        this.da2 = da2;
        this.bianquanzhi = bianquanzhi;
    }

    @Override
    public String toString() {
        return "bian{" +
                "da1=" + da1 +
                ", da2=" + da2 +
                ", bianquanzhi=" + bianquanzhi +
                "}";
    }
}

结果:

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » 最小生成树之普利姆算法与克鲁斯卡尔算法(贪心算法)