最小生成树

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
        Arrays.sort(cost, (a, b) -> a[2] - b[2]);    // 先按边升序排列
        UnionFind uf = new UnionFind(n);
        int money = 0;
        for(int i = 0; i < m; i++){
            int from = cost[i][0] - 1;
            int to = cost[i][1] - 1;
            int costMoney = cost[i][2];
            if(!uf.isConnected(from, to)){
                uf.union(from, to);
                money += costMoney;
            }
            if(uf.getCount() == 1){
                // 所有节点已经连为一体了，退出循环
                break;
            }
        }
        return money;
    }
}

class UnionFind {
    private int[] parent;   // 每棵树的根节点
    private int[] rank;     // 每棵树的相对高度
    private int count;      // 连通分量数
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for(int i = 0; i < n; i++){
            parent[i] = i;
            rank[i] = 1;
        }
    }
    
    public int find(int x) {
        while(x != parent[x]){
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        // 两个节点根不相同时进行合并操作
        if(rootX != rootY){
            if(rank[rootX] > rank[rootY]){
                // x的树比y高，将y合并到x下
                parent[rootY] = rootX;
            }else if(rank[rootX] < rank[rootY]){
                // x的树比y矮，将x合并到y下
                parent[rootX] = rootY;
            }else{
                // 树一样高时合并顺序随意，但是合并另一个子树的树高度要改变
                parent[rootX] = rootY;
                rank[rootY] ++;
            }
        }
        count--;      // 缩减一个分量
    }
    
    // 判断两个节点的连通性
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);      // 比较根节点是否相同即可
    }
    
    // 返回连通分量数
    public int getCount() {
        return count;
    }
}

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) {
        Arrays.sort(cost, Comparator.comparingInt(a ->
                    a[2])); // 根据花费从小到大排序

        UnionFind uf = new UnionFind(n +
                                     1); // 创建并查集，注意顶点从1开始，所以大小为 n+1
        int minCost = 0;
        int edgesUsed = 0;

        for (int[] edge : cost) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];

            if (!uf.connected(u, v)) { // 如果u和v不在同一个集合
                uf.union(u, v); // 合并u和v所在的集合
                minCost += weight; // 累加成本
                edgesUsed++; // 使用的边数增加
                if (edgesUsed == n - 1)
                    break; // 如果已经使用了 n-1 条边，构成了最小生成树
            }
        }

        // 如果使用的边数不足 n-1，说明无法连接所有村庄
        return edgesUsed == n - 1 ? minCost : -1;
    }

    // 并查集类
    static class UnionFind {
        private final int[] parent;
        private final int[] rank;

        public UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int find(int p) {
            if (p != parent[p]) {
                parent[p] = find(parent[p]); // 路径压缩
            }
            return parent[p];
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP != rootQ) {
                if (rank[rootP] > rank[rootQ]) {
                    parent[rootQ] = rootP;
                } else if (rank[rootP] < rank[rootQ]) {
                    parent[rootP] = rootQ;
                } else {
                    parent[rootQ] = rootP;
                    rank[rootP]++;
                }
            }
        }

        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
     int my_union[5505];
     int find_root(int x) {
        if(my_union[x] != x) {
            return  find_root(my_union[x]);
        }
        return x;
    }
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        int count=0;
        int aa,bb;
        int w=0;
       
        for(int i=0;i<n;i++) my_union[i+1]=i+1;
        sort(cost.begin(),cost.end(),[](vector<int> &a,vector<int> &b){return a[2] < b[2];});
        for(int i=0;i<m;i++)
        {
            aa=find_root(cost[i][0]);
            bb=find_root(cost[i][1]);
            if( aa!=bb )
            {
                my_union[bb]=aa;
                w=w+cost[i][2];
                count++;
            }
            if(count==n-1) break;
            
        }
        return w;
    }
};

class Solution {
public:
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        //使用Prim算法，从一个根节点来逐渐让树“长大”。
        //加入新节点时是从未加入树中的节点中搜索，因此不用担心构成回路。

        //记录这个节点的父节点是谁。同时也起到了标志该节点有没有被访问过的作用。
        vector<int> parent(n);
        vector<bool> flag(n);
        //记录这个点离S集，或者说离树的距离。只有与树的节点直接相邻的节点，才算可达。
        vector<int> dist(n);
        //缓存此轮循环中被加入的顶点的下标，视作为下一次循环时的父节点。
        int lastparent=0;
        //对所有节点初始化。
        for(int i=0;i<n;i++)
        {
            parent[i]=-1;
            dist[i]=INT_MAX;
            flag[i]=false;
        }
        dist[0]=0;
        flag[0]=true;
        //初始化树根的所有邻接点。
        for(auto edge:cost)
        {
            if( (edge[0]-1) ==0)
            {
                //将它们的父节点设置为树根
               parent[edge[1]-1]=0; 
               dist[edge[1]-1]=edge[2];
            }
        }
        int sum=0;
        
        while(1)
        {
            int mindistance=INT_MAX;
            int minindex=-1;
            //寻找出距离“树”最近的节点。根节点可以无视。
            for(int i=1;i<parent.size();i++)
            {    
                //如果还没被访问过
                //if(parent[i]==-1)
                if(flag[i]==false)
                {
                    if(dist[i]<mindistance)
                    {
                        mindistance=dist[i];
                        minindex=i;
                    }
                }
            }
            //如果所有的节点都被加入到树中了。
            if(minindex==-1)
            {
                break;
            }
            flag[minindex]=true;
            //将找到的节点的所有邻接点设为可达，即将它们的边值更新进dist数组。
            for(auto edge:cost)
            {
                //如果没被访问过
                if( (edge[0]-1) ==minindex && flag[edge[1]-1]==false)
                {
                    //它的邻接点的下标。
                    int adjoinIndex=edge[1]-1;
                    if(edge[2]<=dist[adjoinIndex])
                    {
                        dist[adjoinIndex]=edge[2];
                        parent[adjoinIndex]=minindex;
                    }
                }
            }
            sum+=dist[minindex];                
        }
        
        //构建树结束，现在遍历dist数组。来计算总的代价
        return sum;
    }
};

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回最小的花费代价使得这n户人家连接起来
 * @param n int n户人家的村庄
 * @param m int m条路
 * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
 * @param costRowLen int cost数组行数
 * @param costColLen int* cost数组列数
 * @return int        //only return one value
 */
typedef struct
{
    int adjvex;
    int lowcost;
}close_edge;

int minimum(close_edge* closedge, int n)
{
    int i = 0;
    int index = -1;
    int min = 9000000;
    
    for (i = 1; i <= n; ++i)
        if (closedge[i].lowcost && min > closedge[i].lowcost)
        {
            min = closedge[i].lowcost;
            index = i;
        }
    
    return index;
}

int miniSpanningTree(int n, int m, int** cost, int costRowLen, int* costColLen ) {
    // write code here
    int* vexs = (int*)calloc(n + 1, sizeof(int));
    int i = 0;
    int j = 0;
    
    for (i = 1; i <= n; ++i)
        vexs[i] = i;
    
    int** Matrix = (int**)calloc(n + 1, sizeof(int *));
    for (i = 0; i < n + 1; ++i)
    {
        int* row = (int *)calloc(n + 1, sizeof(int));
        Matrix[i] = row;
    }
    
    for (i = 0; i < n + 1; ++i)
        for (j = 0; j < n + 1; ++j)
            Matrix[i][j] = 800000;
    
    for (i = 0; i < m; ++i)
        Matrix[cost[i][0]][cost[i][1]] = Matrix[cost[i][1]][cost[i][0]] = cost[i][2];
    
    close_edge* closedge = (close_edge *)calloc(n + 1, sizeof(close_edge));
    
    closedge[0].lowcost = 0;
    closedge[1].lowcost = 0;
    for (i = 2; i <= n; ++i)
    {
        closedge[i].adjvex = 1;
        closedge[i].lowcost = Matrix[1][i];
    }
    
    int count = 0;
    int k = -1;
    
    for (i = 1; i < n; ++i)
    {
        k = minimum(closedge, n);
        
        count += closedge[k].lowcost;
        
        closedge[k].lowcost = 0;
        
        for (j = 1; j <= n; ++j)
            if (Matrix[k][j] < closedge[j].lowcost)
            {
                closedge[j].adjvex = vexs[k];
                closedge[j].lowcost = Matrix[k][j];
            }
    }
    
    return count;
}