题解 | #最小生成树#

题目：最小生成树
描述：一个有n户人家的村庄，有m条路连接着。村里现在要修路，每条路都有一个代价，现在请你帮忙计算下，最少需要花费多少的代价，就能让这n户人家连接起来。
示例1：输入：3,3,[[1,3,3],[1,2,1],[2,3,1]]，返回值：2

解法一：
思路分析：通过观察这道题，有n户人家，需要m条路，代价值用cost数组给出，这里需要解释一下关于这个cost数组，根据实例1分析，数组为[[1,3,3],[1,2,1],[2,3,1]]，该数组的意思是，数组中的第一个数组值代表第1条路到第3条路的权值为3，第二个数组值代表第1条路到第2条路的权值为1，第三个数组值代表第2条路到第3条路的权值为1。如下图所示：
图片说明
——相信根据上图，大家就能很快明白该题的意思，要花费最少的代价将这三户连接起来，只需要将1到2修通，将2到3修通，所需要的权值最小为2，所以返回值为2。所以我们也明白了这道题的意思，就是用prim算法和Kruskal算法求出最小生成树的值。
实例分析：
——Prim算法如下所示：

图片说明
——首先具体连接图如图A所示，权值在图上的点与点之间的线上所标，刚开始找出最小的两点之间的权值为{V1，V3}，将V1与V3相连接形成图B，下面搜索与V3所连接的最小权值，据图发现，权值为4，所以连接{V3，V6}，形成图C，搜索与V6所连接的最小权值图为V4，将V6与V4相连接，形成图D，因为此时V4与周围的结点已经建立了连接了，所以向上返回到V6，V6与V4性质相同，向上返回到V3，寻找与V3最近且未连接的结点为V2，将V3与V2相连接，循环到V2，与V2最近的节点为V5，由此生成了一个最小值的树，最终将所有的值相加即可返回最近的值。这就是prim算法的具体步骤。
Java核心代码：

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        HashSet<Integer> getpoint = new HashSet<>();
        //存储点
        ArrayList<int[]> list = new ArrayList<>();
        //存储边
        Arrays.sort(cost, (l1,l2)->{
            //排序
            return l1[2] - l2[2];
        });
        for (int[] data : cost) {//将数据添加到list中
            list.add(data);
        }
        int res = 0;
        res += cost[0][2];
        getpoint.add(cost[0][0]);
        getpoint.add(cost[0][1]);
        while (true) {
            for (int i = 1; i < list.size(); i++) {//下一条为权值最小的可连接的边
                if ((getpoint.contains(list.get(i)[0]) && !getpoint.contains(list.get(i)[1])) || (!getpoint.contains(list.get(i)[0]) && getpoint.contains(list.get(i)[1]))) {
                    res += list.get(i)[2];
                    getpoint.add(list.get(i)[0]);
                    getpoint.add(list.get(i)[1]);
                    list.remove(list.get(i));
                    //删除已经遍历过的这条边
                    break;
                }
            }
            if (getpoint.size() == n) {
                //所有边都遍历完成，结束
                break;
            }
        }
        return res;
    }
}

——在具体分析的过程中，首先将所有的数据添加到list链表当中，其次，一直通过循环来建立点与最小权值且可连接的边的点，建立完成之后，停止循环。所以其时间复杂度为 $O(N^2)$ ，因为构建了两个存储空间，一个用来存储最终的边，另一个用来存储最终的点，所以空间复杂度为 $O(N + M)$ 。

解法二：
思路分析：既然上述分析采用了prim算法，所以下面肯定采用克鲁斯卡尔算法。
实例分析：
图片说明
——克鲁斯卡尔算法的核心是始终在图中寻找最短路径，如图A所示，第一条最短路径为1，连接点的双方为{V1，V3}，第二条最短路径的权值为2，连接点的双方为{V4，V6}，第三条最短路径为3，连接点的双方为{V2，V5}，第四条最短路径为4，连接点的双方为{V3，V6}，最后一条的权值为5，连接双方为{V2，V3}，最终形成和普里姆算法相同的图。
C++核心代码为：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        for(int i = 0; i <= n; i++) 
            p[i] = i;
        sort(cost.begin(),cost.begin() + m, [](vector<int>& l1, vector<int> & l2){
            //排序
            return l1[2] < l2[2];
        });
        int res = 0;//计算最短权值
        for(int i = 0; i < m; i++)
        {
            if(find(cost[i][0]) != find(cost[i][1]))//不是同一个的话就进入循环
            {
                res += cost[i][2];//将值计算进最终结果中
                p[find(cost[i][0])] = find(cost[i][1]);//合并路径
            }
        }
        return res;
    }
    int p[100010];
    int find(int x)//查找结点与路径
    {
        if(x != p[x])
            p[x] = find(p[x]);
        return p[x];
    }
};

——克鲁斯卡尔算法的核心是通过对所有边权值大小进行排序，然后按照从大到小进行遍历，如果不能使现有的图成环的话就将边加入，然后将权值算入res中，一旦成环，就结束，在该算法中，有一种排序为对边进行排序，因为边数为M，所以对边进行排序的时间复杂度为 $O(MLogM)$ ，总的时间复杂度为 $O(N + MLogM)$ ，N为点，M为边，创建了一个p的内存空间，用来存储点和访问过的路径，所以其空间复杂度为 $O(N + M*2)$ 。