美文网首页
克鲁斯卡尔算法

克鲁斯卡尔算法

作者: Stroman | 来源:发表于2018-02-18 19:55 被阅读32次

这是用Java写的控制台程序，我建议各位看官先运行再看代码。

package com.company;

public class Main {

    public static void main(String[] args) {
    // write your code here
        int[][] adjustMatrix = {
                {0,7,-1,5,-1,-1,-1},
                {-1,0,8,9,7,-1,-1},
                {-1,-1,0,-1,5,-1,-1},
                {-1,-1,-1,0,15,6,-1},
                {-1,-1,-1,-1,0,8,9},
                {-1,-1,-1,-1,-1,0,11},
                {-1,-1,-1,-1,-1,-1,0}
        };
        Kruskal.kruskal0(adjustMatrix);
    }
}

package com.company;

public class Kruskal {
    /**
     * 这是传说中著名的克鲁斯卡尔算法
     * 用于生成最小生成树
     * 适用于无向连通图
     * 权值必须为自然数
     * @param sourceArray
     */
    static public void kruskal0(int[][] sourceArray) {
        int arrayLength = sourceArray.length;
        //第一步对输入的
        // 矩阵按照权值
        // 进行从小到大
        // 排序因为链表
        // 的插入时间复
        // 杂度为O(1)，
        // 所以此处采用
        // 单向链表来构
        // 造从小到大有
        // 序的序列。
        SingleLinkNode headPointer = new SingleLinkNode(-1,-1,-1);
        for (int counter = 0;counter < arrayLength;counter++) {
            for (int counter0 = counter + 1;counter0 < arrayLength;counter0++) {
                if (sourceArray[counter][counter0] > 0) {
                    SingleLinkNode newNode = new SingleLinkNode(counter,counter0,sourceArray[counter][counter0]);
                    SingleLinkNode currentPointer = headPointer;
                    while (currentPointer.nextPointer != null &&
                            currentPointer.nextPointer.getWeight() < newNode.getWeight())
                        currentPointer = currentPointer.nextPointer;
                    newNode.nextPointer = currentPointer.nextPointer;
                    currentPointer.nextPointer = newNode;
                }
            }
        }
        //用来创建连通图结点的集合，每个二维
        // 数组代表一个集合。初始情况下，因为
        // 每个顶点自成一个连通图，所以默认
        // 值情况下每个二维数组的下标为0的值
        // 是该二维数组的index。因为每个二维
        // 数组被当成一个栈来使用，并且已经有
        // 了一个元素，所以栈顶指针为0.此处为
        // 判断新边加入到已有集合的时候是否已
        // 经形成了环。
        //连通图的各集合
        int[][] circleUnion = new int[arrayLength][arrayLength];
        for (int counter = 0;counter < arrayLength;counter++)
            circleUnion[counter][0] = counter;
        //这是栈顶指针，初始状态的时候每个栈中都有一个元素，所以栈顶指针置为0.
        int[] unionTopPointer = new int[arrayLength];
        for (int counter = 0;counter < arrayLength;counter++)
            unionTopPointer[counter] = 0;
        //此数组中代表的是每个顶点此时处于哪个集合之中。
        int[] vertexMarkArray = new int[arrayLength];
        //因为默认情况下每个顶点自成一个连通图，
        // 所以该顶点所属的集合编号就是它自己的编号。
        for (int counter = 0;counter < arrayLength;counter++)
            vertexMarkArray[counter] = counter;
        //逐个选择最小的边进行判断，合格的被加入到某集合中。不合格的从链表中抠去。
        SingleLinkNode currentPointer = headPointer;
        //如果2个顶点对应的编号相同代表
        // 它们属于同一个连通分量，换句
        // 话说已经在一个连通图里面了。
        // 不同则可以合并，不过前提是这
        // 两个顶点所属集合不为空。
        while (currentPointer.nextPointer != null) {
            System.out.println("打印调整前的各结点的集合归属状态");
            for (int counter = 0;counter < arrayLength;counter++) {
                System.out.println(counter + "-->" + vertexMarkArray[counter]);
            }
            System.out.println("打印调整前各集合桶的状态变化");
            for (int counter = 0;counter < arrayLength;counter++) {
                System.out.print("桶" + counter + ":");
                for (int counter0 = 0;counter0 <= unionTopPointer[counter];counter0++) {
                    System.out.print(circleUnion[counter][counter0] + " ");
                }
                System.out.println();
            }
            //链表中某结点的源顶点编号和目标顶点编号
            int sourceIndex = currentPointer.nextPointer.getSourceNode();
            int targetIndex = currentPointer.nextPointer.getTargetNode();
            System.out.println("新顶点对:(" + sourceIndex + "," + targetIndex + ")");
            if (vertexMarkArray[sourceIndex] != vertexMarkArray[targetIndex]
                    && unionTopPointer[vertexMarkArray[sourceIndex]] > -1
                    && unionTopPointer[vertexMarkArray[targetIndex]] > -1) {
                System.out.println("对应的桶编号为:(" + vertexMarkArray[sourceIndex] + "," + vertexMarkArray[targetIndex] + ")");
                //比较一个哪个集合元素多，具体就是比较栈
                // 顶指针。因为要把少的栈中的元素转移到多的栈中。
                if (unionTopPointer[vertexMarkArray[targetIndex]] > unionTopPointer[vertexMarkArray[sourceIndex]]) {
                    int tempIndex = sourceIndex;
                    sourceIndex = targetIndex;
                    targetIndex = tempIndex;
                }
                int moreBucket = vertexMarkArray[sourceIndex];
                int lessBucket = vertexMarkArray[targetIndex];
                while (unionTopPointer[lessBucket] > -1) {
                    int vertexId = circleUnion[lessBucket][unionTopPointer[lessBucket]--];
                    circleUnion[moreBucket][++unionTopPointer[moreBucket]] = vertexId;
                    //在转移的同时刷新被移动的每个顶点所属的集合编号。
                    vertexMarkArray[vertexId] = moreBucket;
                }
                //只要栈中的元素个数达到了顶点的总数就代表算法完成了。
                if (unionTopPointer[vertexMarkArray[sourceIndex]] == arrayLength - 1) {
                    currentPointer.nextPointer.nextPointer = null;
                    System.out.println("打印调整后各集合桶的状态变化");
                    for (int counter = 0;counter < arrayLength;counter++) {
                        System.out.print("桶" + counter + ":");
                        for (int counter0 = 0;counter0 <= unionTopPointer[counter];counter0++) {
                            System.out.print(circleUnion[counter][counter0] + " ");
                        }
                        System.out.println();
                    }
                    System.out.println("集合归并结束");
                    break;
                }
                currentPointer = currentPointer.nextPointer;
            } else {
                System.out.println("舍去");
                currentPointer.nextPointer = currentPointer.nextPointer.nextPointer;
            }
            System.out.println("打印调整后的各结点的集合归属状态");
            for (int counter = 0;counter < arrayLength;counter++) {
                System.out.println(counter + "-->" + vertexMarkArray[counter]);
            }
            //打印各集合桶的状态变化
            System.out.println("打印调整后各集合桶的状态变化");
            for (int counter = 0;counter < arrayLength;counter++) {
                System.out.print("桶" + counter + ":");
                for (int counter0 = 0;counter0 <= unionTopPointer[counter];counter0++) {
                    System.out.print(circleUnion[counter][counter0] + " ");
                }
                System.out.println();
            }
            System.out.println();
        }
        //打印剩下的抠去不合格结点后的链表
        System.out.println("\n结果集为:");
        while (headPointer.nextPointer != null) {
            System.out.println("(" + headPointer.nextPointer.getSourceNode() + "," + headPointer.nextPointer.getTargetNode() + ")-->" + headPointer.nextPointer.getWeight());
            headPointer = headPointer.nextPointer;
        }
    }

    /**
     * 本实现是对kruskal0的改进
     * @param sourceArray
     */
    static public void kruskal1(int[][] sourceArray) {
        int arrayLength = sourceArray.length;
        SingleLinkNode headPointer = new SingleLinkNode(-1,-1,-1);
        for (int counter = 0;counter < arrayLength;counter++) {
            for (int counter0 = counter + 1;counter0 < arrayLength;counter0++) {
                if (sourceArray[counter][counter0] > 0) {
                    SingleLinkNode newNode = new SingleLinkNode(counter,counter0,sourceArray[counter][counter0]);
                    SingleLinkNode currentPointer = headPointer;
                    while (currentPointer.nextPointer != null &&
                            currentPointer.nextPointer.getWeight() < newNode.getWeight())
                        currentPointer = currentPointer.nextPointer;
                    newNode.nextPointer = currentPointer.nextPointer;
                    currentPointer.nextPointer = newNode;
                }
            }
        }
        //此处原本采用了n×n的二维数组，
        // 但是实际元素数量只有n，所以
        // 利用率只有1/n，太低了，于是
        // 考虑用链表来实现。而且这样做
        // 也不用再使用栈顶指针了。
        DoubleLinkNode[] circleUnion = new DoubleLinkNode[arrayLength];
        //在这里姑且用结点的vertexId属性
        // 来标识连通集的ID吧，用counter属性来记录当前桶的顶点个数。
        for (int counter = 0;counter < arrayLength;counter++)
            circleUnion[counter] = new DoubleLinkNode(1,counter);
        int[] vertexMarkArray = new int[arrayLength];
        for (int counter = 0;counter < arrayLength;counter++)
            vertexMarkArray[counter] = counter;
        SingleLinkNode currentPointer = headPointer;
        while (currentPointer.nextPointer != null) {
            System.out.println("打印调整前的各结点的集合归属状态");
            for (int counter = 0;counter < arrayLength;counter++) {
                System.out.println(counter + "-->" + vertexMarkArray[counter]);
            }
            System.out.println("打印调整前各集合桶的状态变化");
            for (int counter = 0;counter < arrayLength;counter++) {
                System.out.print("桶" + counter + ":");
                DoubleLinkNode bucketHeadPointer = circleUnion[counter];
                while (bucketHeadPointer != null) {
                    System.out.print(bucketHeadPointer.getVertexId() + " ");
                    bucketHeadPointer = bucketHeadPointer.prePointer;
                }
                System.out.println();
            }
            int sourceIndex = currentPointer.nextPointer.getSourceNode();
            int targetIndex = currentPointer.nextPointer.getTargetNode();
            System.out.println("新顶点对:(" + sourceIndex + "," + targetIndex + ")");
            if (vertexMarkArray[sourceIndex] != vertexMarkArray[targetIndex]
                    && circleUnion[vertexMarkArray[sourceIndex]] != null
                    && circleUnion[vertexMarkArray[targetIndex]] != null) {
                System.out.println("对应的桶编号为:(" + vertexMarkArray[sourceIndex] + "," + vertexMarkArray[targetIndex] + ")");
                if (circleUnion[vertexMarkArray[targetIndex]].getCounter() >
                        circleUnion[vertexMarkArray[sourceIndex]].getCounter()) {
                    int tempIndex = sourceIndex;
                    sourceIndex = targetIndex;
                    targetIndex = tempIndex;
                }
                int moreBucket = vertexMarkArray[sourceIndex];
                int lessBucket = vertexMarkArray[targetIndex];
                while (circleUnion[lessBucket] != null) {
                    DoubleLinkNode moreHeadPointer = circleUnion[moreBucket];
                    DoubleLinkNode lessHeadPointer = circleUnion[lessBucket];
                    DoubleLinkNode movedPointer = lessHeadPointer;
                    lessHeadPointer = lessHeadPointer.prePointer;
                    movedPointer.nextPointer = null;
                    movedPointer.prePointer = null;
                    vertexMarkArray[movedPointer.getVertexId()] = moreBucket;
                    moreHeadPointer.nextPointer = movedPointer;
                    movedPointer.prePointer = moreHeadPointer;
                    movedPointer.setCounter(moreHeadPointer.getCounter() + 1);
                    moreHeadPointer = movedPointer;
                    circleUnion[moreBucket] = moreHeadPointer;
                    circleUnion[lessBucket] = lessHeadPointer;
                }
                if (circleUnion[moreBucket].getCounter() == arrayLength) {
                    currentPointer.nextPointer.nextPointer = null;
                    System.out.println("打印调整后各集合桶的状态变化");
                    for (int counter = 0;counter < arrayLength;counter++) {
                        System.out.print("桶" + counter + ":");
                        DoubleLinkNode bucketHeadPointer = circleUnion[counter];
                        while (bucketHeadPointer != null) {
                            System.out.print(bucketHeadPointer.getVertexId() + " ");
                            bucketHeadPointer = bucketHeadPointer.prePointer;
                        }
                        System.out.println();
                    }
                    System.out.println("集合归并结束");
                    break;
                }
                currentPointer = currentPointer.nextPointer;
            } else {
                System.out.println("舍去");
                currentPointer.nextPointer = currentPointer.nextPointer.nextPointer;
            }
            System.out.println("打印调整后的各结点的集合归属状态");
            for (int counter = 0;counter < arrayLength;counter++) {
                System.out.println(counter + "-->" + vertexMarkArray[counter]);
            }
            System.out.println("打印调整后各集合桶的状态变化");
            for (int counter = 0;counter < arrayLength;counter++) {
                System.out.print("桶" + counter + ":");
                DoubleLinkNode bucketHeadPointer = circleUnion[counter];
                while (bucketHeadPointer != null) {
                    System.out.print(bucketHeadPointer.getVertexId() + " ");
                    bucketHeadPointer = bucketHeadPointer.prePointer;
                }
                System.out.println();
            }
            System.out.println();
        }
        System.out.println("\n结果集为:");
        while (headPointer.nextPointer != null) {
            System.out.println("(" + headPointer.nextPointer.getSourceNode() + "," + headPointer.nextPointer.getTargetNode() + ")-->" + headPointer.nextPointer.getWeight());
            headPointer = headPointer.nextPointer;
        }
    }
}

package com.company;

public class SingleLinkNode {
    private int sourceNode;
    private int targetNode;
    private int weight;
    public SingleLinkNode nextPointer = null;

    public SingleLinkNode(int sourceNode, int targetNode, int weight) {
        this.sourceNode = sourceNode;
        this.targetNode = targetNode;
        this.weight = weight;
    }

    public int getWeight() {
        return weight;
    }

    public int getSourceNode() {
        return sourceNode;
    }

    public int getTargetNode() {
        return targetNode;
    }
}


package com.company;

public class DoubleLinkNode {
    private int counter;
    private int vertexId;
    public DoubleLinkNode prePointer = null;
    public DoubleLinkNode nextPointer = null;

    public DoubleLinkNode(int counter, int vertexId) {
        this.counter = counter;
        this.vertexId = vertexId;
    }

    public int getCounter() {
        return counter;
    }

    public void setCounter(int counter) {
        this.counter = counter;
    }

    public int getVertexId() {
        return vertexId;
    }
}

输出如下

打印调整前的各结点的集合归属状态
0-->0
1-->1
2-->2
3-->3
4-->4
5-->5
6-->6
打印调整前各集合桶的状态变化
桶0:0 
桶1:1 
桶2:2 
桶3:3 
桶4:4 
桶5:5 
桶6:6 
新顶点对:(2,4)
对应的桶编号为:(2,4)
打印调整后的各结点的集合归属状态
0-->0
1-->1
2-->2
3-->3
4-->2
5-->5
6-->6
打印调整后各集合桶的状态变化
桶0:0 
桶1:1 
桶2:2 4 
桶3:3 
桶4:
桶5:5 
桶6:6 

打印调整前的各结点的集合归属状态
0-->0
1-->1
2-->2
3-->3
4-->2
5-->5
6-->6
打印调整前各集合桶的状态变化
桶0:0 
桶1:1 
桶2:2 4 
桶3:3 
桶4:
桶5:5 
桶6:6 
新顶点对:(0,3)
对应的桶编号为:(0,3)
打印调整后的各结点的集合归属状态
0-->0
1-->1
2-->2
3-->0
4-->2
5-->5
6-->6
打印调整后各集合桶的状态变化
桶0:0 3 
桶1:1 
桶2:2 4 
桶3:
桶4:
桶5:5 
桶6:6 

打印调整前的各结点的集合归属状态
0-->0
1-->1
2-->2
3-->0
4-->2
5-->5
6-->6
打印调整前各集合桶的状态变化
桶0:0 3 
桶1:1 
桶2:2 4 
桶3:
桶4:
桶5:5 
桶6:6 
新顶点对:(3,5)
对应的桶编号为:(0,5)
打印调整后的各结点的集合归属状态
0-->0
1-->1
2-->2
3-->0
4-->2
5-->0
6-->6
打印调整后各集合桶的状态变化
桶0:0 3 5 
桶1:1 
桶2:2 4 
桶3:
桶4:
桶5:
桶6:6 

打印调整前的各结点的集合归属状态
0-->0
1-->1
2-->2
3-->0
4-->2
5-->0
6-->6
打印调整前各集合桶的状态变化
桶0:0 3 5 
桶1:1 
桶2:2 4 
桶3:
桶4:
桶5:
桶6:6 
新顶点对:(1,4)
对应的桶编号为:(1,2)
打印调整后的各结点的集合归属状态
0-->0
1-->2
2-->2
3-->0
4-->2
5-->0
6-->6
打印调整后各集合桶的状态变化
桶0:0 3 5 
桶1:
桶2:2 4 1 
桶3:
桶4:
桶5:
桶6:6 

打印调整前的各结点的集合归属状态
0-->0
1-->2
2-->2
3-->0
4-->2
5-->0
6-->6
打印调整前各集合桶的状态变化
桶0:0 3 5 
桶1:
桶2:2 4 1 
桶3:
桶4:
桶5:
桶6:6 
新顶点对:(0,1)
对应的桶编号为:(0,2)
打印调整后的各结点的集合归属状态
0-->0
1-->0
2-->0
3-->0
4-->0
5-->0
6-->6
打印调整后各集合桶的状态变化
桶0:0 3 5 1 4 2 
桶1:
桶2:
桶3:
桶4:
桶5:
桶6:6 

打印调整前的各结点的集合归属状态
0-->0
1-->0
2-->0
3-->0
4-->0
5-->0
6-->6
打印调整前各集合桶的状态变化
桶0:0 3 5 1 4 2 
桶1:
桶2:
桶3:
桶4:
桶5:
桶6:6 
新顶点对:(4,5)
舍去
打印调整后的各结点的集合归属状态
0-->0
1-->0
2-->0
3-->0
4-->0
5-->0
6-->6
打印调整后各集合桶的状态变化
桶0:0 3 5 1 4 2 
桶1:
桶2:
桶3:
桶4:
桶5:
桶6:6 

打印调整前的各结点的集合归属状态
0-->0
1-->0
2-->0
3-->0
4-->0
5-->0
6-->6
打印调整前各集合桶的状态变化
桶0:0 3 5 1 4 2 
桶1:
桶2:
桶3:
桶4:
桶5:
桶6:6 
新顶点对:(1,2)
舍去
打印调整后的各结点的集合归属状态
0-->0
1-->0
2-->0
3-->0
4-->0
5-->0
6-->6
打印调整后各集合桶的状态变化
桶0:0 3 5 1 4 2 
桶1:
桶2:
桶3:
桶4:
桶5:
桶6:6 

打印调整前的各结点的集合归属状态
0-->0
1-->0
2-->0
3-->0
4-->0
5-->0
6-->6
打印调整前各集合桶的状态变化
桶0:0 3 5 1 4 2 
桶1:
桶2:
桶3:
桶4:
桶5:
桶6:6 
新顶点对:(4,6)
对应的桶编号为:(0,6)
打印调整后各集合桶的状态变化
桶0:0 3 5 1 4 2 6 
桶1:
桶2:
桶3:
桶4:
桶5:
桶6:
集合归并结束

结果集为:
(2,4)-->5
(0,3)-->5
(3,5)-->6
(1,4)-->7
(0,1)-->7
(4,6)-->9

相关文章

网友评论

      本文标题：克鲁斯卡尔算法

      本文链接：https://www.haomeiwen.com/subject/cumbtftx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|克鲁斯卡尔算法|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！