Prim最小生成树 - java实现

2020-08-05T22:27:51
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

偶然看到一个Prim算法的非常好的动画演示,贴上链接【bilibili】https://www.bilibili.com/video/av47042691?from=search&seid=12957229882655641618

注意,图的最小生成树不一定只有一种

我用到一个自写的Array类,Array代码如下,着急运行的同学不用太在意这个,复制粘贴到一个package下即可
package structuretools;

public class Array<E> {

    private E[] data; //定义 访问+类型+数组名

    private int size;   //数组中元素的个数 <指向第一个没有元素的下标>

    //构造函数 , 传入数组的容量capacity构造Array
    public Array(int capacity) { //capacity表示数组最大容量
        data = (E[])new Object[capacity];
        size = 0;
    }

    public Array() {
        this(10);   //默认的 capacity = 10
    }


    //返回数组内元素个数
    public int getSize() {
        return size;
    }

    //返回数组最大容纳元素个数
    public int getCapacity() {
        return data.length;
    }

    //返回数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }


    //////////////////////////////增增增增增增增增增增增增增增增增增增增增增增增增增增增增增
    //在所有元素后添加 e
    public void addLast(E e) {
        //System.out.println("addLast传参成功" + e);
        add(size, e);
    }

    //在所有数组最前添加 e
    public void addFirst(E e) {
        add(0, e);
    }

    //在index位置插入新元素e
    public void add(int index, E e) {

        //判断:传入下标是否合法
        if (index < 0 || index > size)
            throw new IllegalArgumentException("AddLast is failed. Array is full.");

        if (size == data.length) //判断:添加前数组是否已满
            //throw new IllegalArgumentException("AddLast is failed. Array is full.");
            resize(2*data.length);  //动态数组操作 私有方法 resize 扩容2倍
        // 合法执行插入
        for (int i = size - 1; i >= index; i--)
            data[i + 1] = data[i];    //向后漂移

        data[index] = e;
        size++;
    }

    //////////////////////////////查查查查查查查查查查查查查查查查查查查查
    //得到索引index对应的元素
    public E get(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed . Index is illegal");
        return data[index];
    }

    public void set(int index, E e) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed . Index is illegal");
        data[index] = e;
    }

    //查找数组中!是否!e
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e))  //.equals()用于两个对象值的比较
                // == 为 两个对象 引用比较
                return true;
        }
        return false;
    }

    // 查询数组中元素e 的索引, 若不存在则返回-1
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i] == e)
                return i;
        }
        return -1;
    }

    public E getLast(){
        return get(size - 1);
        //不使用get(data[size - 1])  size = 0 不会报错 而get可以
    }

    public E getFirst(){
        return get(0);
    }





    //删//删//删//删//删//删//删//删//删//删//删//删//删//删//删//删//删//删//删//删//删//删//删//删
    //删除索引为index的元素 //同时返回被删除的元素
    public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed . Index is illegal");

        E res = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];
        size--;
        //此时data[size]的数值 == data[size-1]  不会被JAVA垃圾回收机制自动回收
        data[size] = null;  //启动语句   //称为loitering objects != memory leak
                                        // 游离的对象无法自动回收 != 内存泄漏
        if (size == data.length / 4 && data.length / 2 != 0)
            resize(data.length / 2);
        return res;
    }

    //删除第一个元素
    public E removeFirst() {
        return remove(0);
    }

    //删除第二个元素
    public E removeLast() {
        return remove(size - 1);
    }

    //1.查询数组内有没有e 有则删除 !!不能保证数组中没有元素e
    public boolean removeElement(E e) {
        int index = find(e);
        if (index != -1) {
            remove(index);
            return true;
        }
        return false;//没有元素e存在
    }



    @Override   //覆盖标记
    public String toString() {
        //控制 直接打印类的输出形式
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array:size = %d , capacity = %d\n", size, data.length));
        // StringBuilder 动态字符串类  String.format 文本处理工具
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            /*if (i != size - 1)    //size-1为已赋值元素中最后一个元素的index
                res.append(",");*/
        }
        res.append(']');    //build数组=>字符串  形如[1,2,3]
        return res.toString();
    }


    //扩容 => 动态数组
    private void resize (int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++)  //旧数组复制到新数组
            newData[i] = data[i];
        data = newData; //新数组引用给旧引用
    }   //动态数组更新完成

}

</ br>
</ br>


PrimTree代码如下。这里需要引入之前的Array类

package COURSE;

import structuretools.Array;

public class PrimTree {
    private class Node {
        int index; // 第index号节点,即name
        boolean selected; // 是否被加入prim树
        int minDist; // 最小边权值
        int parentIndex; // 父节点

        public Node(int index) {
            this.index = index;
            selected = false;
            minDist = Integer.MAX_VALUE;
            parentIndex = -1;
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append("{index=" + index + ", selected=" + selected + ", minDist=" + minDist + ", parentIndex=" + parentIndex + ")\n");
            return res.toString();
        }
    }

    int map[][];
    Node root;
    Array<Node> nodes = new Array<>();

    // 初始化
    public PrimTree(int root, int[][] map) {
        this.map = map;
        initTree(root);

        while (!isFinished()) {
            update();
            System.out.println(nodes);
            int addNodeIndex = scan();
            add(addNodeIndex);
        }

    }

    private void initTree(int root) {
        // 包括根节点的标记
        for (int i = 0; i < this.map.length; i++) {
            this.nodes.addLast(new Node(i));
        }
        this.root = nodes.get(root);
        this.root.selected = true;
    }

    // 标记已选点集 与 未选点集 连线
    private void update() {

        for (int i = 0; i < nodes.getSize() - 1; i++) {
            Node cur = nodes.get(i);

            // 已选点
            if (cur.selected) {
                // cur点到next点的权值
                int[] row = map[cur.index];

                for (int j = 0; j < row.length; j++) {
                    Node next = nodes.get(j);

                    // 与未选点比较
                    if (!next.selected && row[j] < next.minDist) {
                        next.minDist = row[j];
                        next.parentIndex = cur.index;
                    }

                }
            }
        }
    }

    // 返回 这些连线中权值最小的现对应的 未选点
    private int scan() {
        // 找出nodes中minDist最小的点,加入PrimTree并初始化minDist
        int minDist = Integer.MAX_VALUE;
        int minDistIndex = -1;

        for (int i = 0; i < nodes.getSize(); i++) {
            Node cur = nodes.get(i);
            if (!cur.selected && cur.minDist <= minDist) {
                minDist = cur.minDist;
                minDistIndex = i;
            }
        }
        return minDistIndex;
    }

    private boolean isFinished() {
        for (int i = 0; i < nodes.getSize() - 1; i++) {
            if (!nodes.get(i).selected) {
                return false;
            }
        }
        return true;
    }

    // 讲该未选点标记为 已选点
    private void add(int index) {
        nodes.get(index).selected = true;
    }

    private void print(){
        System.out.println(nodes);
    }


    public static void main(String[] args) {
        int max = Integer.MAX_VALUE;
        int[][] map = {
                {max, 4, max, max, max, max, max, 8},
                {4, max, 8, max, max, max, max, 11, max},
                {max, 8, max, 7, max, 4, max, max, 2},
                {max, max, 7, max, 9, 14, max, max, max},
                {max, max, max, 9, max, 10, max, max, max},
                {max, max, 4, 14, 10, max, 2, max, max},
                {max, max, max, max, max, 2, max, 1, 6},
                {8, 11, max, max, max, max, 1, max, 7},
                {max, max, 2, max, max, max, 6, 7, max}
        };

        PrimTree p = new PrimTree(0, map);
        p.print();
    }
}


扫一扫关注公众号添加购物返利助手,领红包
当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »
因本文不是用Markdown格式的编辑器书写的,转换的页面可能不符合MIP标准。