题目的主要信息：

• n个节点，m条边，边权记录在邻接表cost中
• 求最小生成树的总边权

方法一：kruskal算法+并查集

具体做法：

最小生成树，我们可以连通的点看成是同一个并查集，利用并查集的思想来逐渐加边使所有节点连在一起。同时，最小生成树需要用kruskal算法的贪心思想，先对邻接表按照边权递增排序，然后从最小的边开始遍历，检查边的两边是否在同一个并查集中，如果在则不加这条边，如果不在则将这条边加入总边权，同时设置二者属于同一个并查集。

class Solution {
public:
    static bool cmp(vector<int>& x, vector<int>& y){ //重载比较，按照边权递增
        return x[2] < y[2];
    }
    
    int find(vector<int>& parent, int x){ //向上找到最高的父亲
        if(parent[x] != x)
            parent[x] = find(parent, parent[x]);
        return parent[x];
    }
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        vector<int> parent(n + 1);
        for(int i = 0; i <= n; i++) //初始父亲设置为自己
            parent[i] = i;
        sort(cost.begin(), cost.end(), cmp); //边权递增排序
        int res = 0;
        for(int i = 0; i < cost.size(); i++){ //遍历所有的边，将连通的放入同一个并查集
            int x = cost[i][0];
            int y = cost[i][1];
            int z = cost[i][2];
            int px = find(parent, x); //查找x的最上边父亲
            int py = find(parent, y); // 查找y的最上边父亲
            if(px != py){ //如果二者不在同一个集合
                res += z; //边加入
                parent[px] = py; //设置二者在同一个集合
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(mlo{g}_{2}m+nm)O(mlog\_2m+nm)$，排序的复杂度加上最坏情况对于遍历到的每条边都要采用并查集的查找n次
• 空间复杂度：$O(n)O(n)$，记录并查集的数组及递归栈

方法二：prim算法

具体做法：

还可以用prim算法，如下图所示：

第一次加入最小的边的两点，然后从其中一个点出发每次只加入与这个点相连的最短的边，我们用unordered_set对点进行去重，每次加入一条边，边集合就删去它，直到集合中点的个数为n。（先按边权升序排序，才能每次遇到更短的边。）

class Solution {
public:
    static bool cmp(vector<int>& x, vector<int>& y){ //重载比较，按照边权递增
        return x[2] < y[2];
    }
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        unordered_set<int> points;  //记录不重复的点
        int res = 0;
        sort(cost.begin(), cost.end(), cmp); //排序得到最小值
        res += cost[0][2]; //首先将最小的边加入
        points.insert(cost[0][0]);
        points.insert(cost[0][1]);
        while(1){ 
            if(points.size() == n) //所有的点已连通
                break;
            for(auto iter = cost.begin(); iter != cost.end(); iter++){ //从小到大遍历剩余的边
                //这个边一个点在集合内，一个不在就加入
                if((points.find((*iter)[0]) != points.end() && points.find((*iter)[1]) == points.end()) || (points.find((*iter)[1]) != points.end() && points.find((*iter)[0]) == points.end())){
                    res += (*iter)[2];
                    points.insert((*iter)[0]);
                    points.insert((*iter)[1]);
                    cost.erase(iter);  //删除该边
                    break;
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(nm+mlo{g}_{2}m)O(nm+mlog\_2m)$，排序的复杂度加上最坏情况每个点加入的边都需要遍历数组，删去边的复杂度也为$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，集合的大小最坏为$nn$