【图论】最小生成树

摘要：最小生成树有两种生成算法普里姆算法克鲁斯克尔算法算法普利姆算法算法流程我的理解任选一个元素，作为起始点将起始点标记为，代表该点已经加入最小生成树集合计算这个集合到未加入的各个点的距离选择一个最小的距离点，加入集合，即标记为已访问更新集合到其

Prim（普里姆算法）

Kruskal（克鲁斯克尔）算法

算法流程：（我的理解）

任选一个元素，作为起始点

将起始点标记为visit，代表该点已经加入最小生成树集合

计算这个集合到未加入的各个点的距离

选择一个最小的距离点，加入集合，即标记为已访问

更新集合到其他各个点的最小距离

迭代

存疑

- 目前没有找到记录下路径的办法，不知道是不是还没理解到位

package com.edu.chapter03;

import org.junit.Test;

public class MinimumTree {
    /**
     * 最小生成树
     */
    int n;
    int e[][];
    int dis[];

    public void createMinmumTree() {
        int pos = 1; // 从1节点开始，可以任意指定；pos 代表当前要加入最小生成树集合的编号
        int join[] = new int[n + 1]; // 记录各个点加入的情况
        int weight = 0;
        // 初始化最小生成树集合与其他各个点的距离
        for (int i = 1; i <= n; i++) {
            dis[i] = i == pos ? 0 : e[pos][i];
        }

        for (int i = 2; i <= n; i++) { // 从寻找第二个点开始（并不是代表要把2号点添加进去）
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= n; j++) {
                if (join[j] == 0 && dis[j] !=0 && min > dis[j]) { // 找出集合距离未加入的点的最近边及点;dis[j]!=0 表示跳过和自己的比较
                    min = dis[j];
                    pos = j; // 找到最小位置，下一个要加入的点就是这个点
                }
            }

            join[pos] = 1; // 标记为以加入最小生成树集合
            weight += min;
 
            //重新计算集合距离其他点的距离
            for (int j = 1; j <= n; j++) {
                if (join[j] == 0 && dis[j] > e[pos][j]) { // 比较新加入的点是否带来的更短的距离，
                    dis[j] = e[pos][j]; //有，则更新。保证dis里存储的是到其他点的最近距离
                }
            }
        }
        System.out.println("weight:" + weight);
    }

    @Test
    public void test01() {
        n = 6;
        e = new int[n + 1][n + 1];
        dis = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    e[i][j] = 0;
                } else {
                    e[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        e[1][2] = e[2][1] = 2;
        e[1][3] = e[3][1] = 4;
        e[1][4] = e[4][1] = 7;

        e[2][3] = e[3][2] = 1;
        e[2][5] = e[5][2] = 2;

        e[3][4] = e[4][3] = 1;
        e[3][5] = e[5][3] = 6;
        createMinmumTree();
    }
}

算法思路

首先将图中的边按权重大小排序（从小到大）

可以使用快速排序或者堆排序

取出一条边，将边对应的两个节点放入一个集合

如果集合中已经存在这两个点，则放弃该边

不断有边加入，将不同的集合连起来，直到集合包含了所有节点，结束

每次有效添加的一条边，代表了最小生成树中对应的边，或者说路径