Problem: 1584. 连接所有点的最小费用

• Kruskal算法
  • 复杂度
  • Code
• Prim算法
  • 复杂度
  • Code

Kruskal算法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(mlog(m))$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        // 生成所有边以及权重
        Edge[] edges = new Edge[n*(n-1)/2];  //完全图最多生成的边数
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {  //防止生成重复的边
                edges[index++] = new Edge(i,j,Math.abs(points[i][0]-points[j][0])+Math.abs(points[i][1]-points[j][1]));
            }
        }
        // 根据权重排序
        Arrays.sort(edges,(a,b)->a.weight-b.weight);
        // 构造并查集
        UnionSet unionSet = new UnionSet(n);
        int ans = 0;
        // 执行Kruskal算法
        for (Edge edge : edges) {
            // 如果两个点已经连通，则跳过
            if(unionSet.isConnected(edge.start,edge.end)) continue;
            // 否则，将两个点连通，并且加上权重
            unionSet.union(edge.start,edge.end);
            // 执行相加
            ans += edge.weight;
        }
        return ans;
    }

    record Edge(int start, int end, int weight){}

    class UnionSet{
        private int count;
        private int[] parent;

        public UnionSet(int n){
            this.count = n;
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public void union(int x, int y){
            int p = find(x);
            int q = find(y);
            parent[p] = q;
            count--;
        }

        public boolean isConnected(int x, int y){
            return find(x) == find(y);
        }

        public int find(int x){
            if(parent[x] != x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public int getCount(){
            return count;
        }

    }
}

Prim算法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n^2)$

空间复杂度:

添加空间复杂度, 示例： $O(n^2)$

Code

class Solution {
    public int minCostConnectPoints(int[][] points) {
         // 构建邻接矩阵
        int m = points.length;
        int[][] graph = new int[m][m];
        for(int i=0;i<m;i++){
            for(int j=i+1;j<m;j++){
                graph[i][j] = graph[j][i] = Math.abs(points[i][0]-points[j][0])+Math.abs(points[i][1]-points[j][1]);
            }
        }
        // prim算法
        int[] lowCost = new int[m];
        Arrays.fill(lowCost,Integer.MAX_VALUE); 
        boolean[] visited = new boolean[m];
        visited[0] = true;
        int ans = 0;
        for(int i=0;i<m;i++){
            lowCost[i] = graph[0][i];  // 先将第一个顶点的权重加上
        }
        for(int i=1;i<m;i++){
            int minIdx = -1;
            int minCost = Integer.MAX_VALUE;
            for (int j = 0; j < m; j++) {
                // 如果没有被遍历过而且权重较小则记录下来
                if(!visited[j] && lowCost[j]<minCost){
                    minIdx = j;
                    minCost = lowCost[j];
                }
            }
            visited[minIdx] = true;  // 标记遍历过
            ans+=minCost;  // 执行相加
            // 接着与下一个要遍历的顶点比较最小权重，得到最小权重数组
            for(int j=0;j<m;j++){  
                if(!visited[j]&&graph[minIdx][j]<lowCost[j]){
                    lowCost[j] = graph[minIdx][j];
                }
            }
        }
        return ans;
    }
}