1.题

1584

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

Kruskal

package com.Kruskal.Demo1584;

import java.util.*;

public class Demo1584_Kruskal {
    class Solution {
        class QuickUnion {
            private int[] parent;
            private int[] rank;
            public QuickUnion(int n){
                parent=new int[n];
                rank=new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i]=i;
                    rank[i]=0;
                }
            }
            public int find(int p){
                while (p!=parent[p]){
                    parent[p]=parent[parent[p]];
                    p=parent[p];
                }
                return p;
            }
            public void union(int p,int q){
                int root1=find(p);
                int root2=find(q);

                if(root1==root2) return;

                if(rank[root1]>rank[root2]){
                    parent[root2]=root1;
                }else if(rank[root1]<rank[root2]){
                    parent[root1]=root2;
                }else {
                    parent[root1]=root2;
                    rank[root2]++;
                }
            }
        }
        public int minCostConnectPoints(int[][] points) {
            //创建成 节点+边
            List<int[]> edges=new ArrayList<>();
            for (int i = 0; i <points.length; i++) {
                for (int j = i+1; j <points.length; j++) {
                    int weight=Math.abs(points[i][0]-points[j][0])+Math.abs(points[i][1]-points[j][1]);
                    edges.add(new int[]{i,j,weight});
                }
            }

            //排序
            edges.sort((a, b)-> a[2]-b[2]);

            //kruskal
            QuickUnion qu=new QuickUnion(points.length);
            int totalWeight=0;
            int totalEdges=0;
            for (int[] edge : edges) {
                if(qu.find(edge[0])!=qu.find(edge[1])){
                    qu.union(edge[0],edge[1]);
                    int weight=edge[2];
                    totalEdges++;
                    totalWeight+=weight;
                }
                if(totalEdges==points.length-1) break;
            }
            return totalWeight;
        }
    }
}

Prim

package com.Prim.Demo1584;

import java.util.Arrays;

public class Demo1584_Prim {
    class Solution {
        public int minCostConnectPoints(int[][] points) {
            int n=points.length;
            int[] minDist=new int[n];//权值
            boolean[] visited=new boolean[n];//激活节点
            //初始化
            Arrays.fill(minDist,Integer.MAX_VALUE);
            minDist[0]=0;
            int totalWeight=0;
            for (int i = 0; i < n; i++) {
                int cur=-1;
                int minWeight=Integer.MAX_VALUE;
                //找最小权值
                for (int j = 0; j < n; j++) {
                    if(!visited[j] && minDist[j]<minWeight){
                        minWeight=minDist[j];
                        cur=j;
                    }
                }
                if(cur==-1) break;

                visited[cur]=true;
                totalWeight+=minWeight;

                //更新未激活节点的权值
                for (int j = 0; j < n; j++) {
                    int value=Math.abs(points[cur][0]-points[j][0])+Math.abs(points[cur][1]-points[j][1]);
                    if(!visited[j] && value<minDist[j]){
                        minDist[j]=value;
                    }
                }
            }
            return totalWeight;
        }
    }
}

HDU_1863

Kruskal

package com.Demo_HDU_1863;

import java.awt.desktop.PreferencesEvent;
import java.util.*;

public class Demo_HDU_1863_Kruskal {
    static class QuickUnion{
        private int[] parent;
        private int[] rank;
        public QuickUnion(int n){
            parent=new int[n+1];
            rank=new int[n+1];
            for (int i = 1; i <= n; i++) {
                rank[i]=0;
                parent[i]=i;
            }
        }
        public int find(int p){
            while(p!=parent[p]){
                parent[p]=parent[parent[p]];
                p=parent[p];
            }
            return p;
        }
        public void union(int p,int q){
            int root1=find(p);
            int root2=find(q);
            if(root1==root2) return;
            if(rank[root1]>rank[root2]){
                parent[root2]=root1;
            }else if(rank[root1]<rank[root2]){
                parent[root1]=root2;
            }else {
                parent[root2]=root1;
                rank[root1]++;
            }
        }
    }
    static class Edge{
        int a,b,c;
        public Edge(int a,int b,int c){
            this.a=a;
            this.b=b;
            this.c=c;
        }
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        //道路数 N和村庄数 M
        //随后 N行每行给出   村庄1 村庄2 成本
        int N= 0;
        int M= 0;
        List<Edge> edges= null;
        while (true) {
            N = sc.nextInt();
            M = sc.nextInt();
            if(N==0) break;
            edges = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                edges.add(new Edge(sc.nextInt(),sc.nextInt(),sc.nextInt()));
            }
            int result=getMinCost(N,M,edges);
            if(result==-1){
                System.out.println("?");
            }else{
                System.out.println(result);
            }
        }
    }
    public static int getMinCost(int N,int M,List<Edge> edges){
        //Kruskal
        edges.sort((m,n)->m.c-n.c);
        int totalCost=0;
        int totalEdges=0;
        QuickUnion qu=new QuickUnion(M);
        for (Edge edge : edges) {
            if(qu.find(edge.a)!= qu.find(edge.b)){
                qu.union(edge.a, edge.b);
                totalCost+=edge.c;
                totalEdges++;
            }
            if(totalEdges==M-1) break;
        }

        return totalEdges==M-1?totalCost:-1;
    }
}

Prim

package com.Demo_HDU_1863;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Demo_HDU_1863_Prim {
    static class Edge{
        int a,b,c;
        public Edge(int a,int b,int c){
            this.a=a;
            this.b=b;
            this.c=c;
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        //道路数 N和村庄数 M
        //随后 N行每行给出   村庄1 村庄2 成本
        int N= 0;
        int M= 0;
        List<Edge> edges= null;
        while (true) {
            N = sc.nextInt();
            M = sc.nextInt();
            if(N==0) break;
            edges = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                edges.add(new Edge(sc.nextInt(),sc.nextInt(),sc.nextInt()));
            }
            int result=getMinCost(N,M,edges);
            if(result==-1){
                System.out.println("?");
            }else{
                System.out.println(result);
            }
        }
    }
    public static int getMinCost(int N,int M,List<Edge> edges){
        int[] minCost=new int[M+1];
        boolean[] visited=new boolean[M+1];
        //初始化
        Arrays.fill(minCost,Integer.MAX_VALUE);
        minCost[1]=0;
        int totalCost=0;
        for (int i = 0; i < M; i++) {
            int cur=-1;
            int min=Integer.MAX_VALUE;
            //找最小权值
            for (int j = 1; j <= M; j++) {
                if(!visited[j]&& min > minCost[j]){
                    min=minCost[j];
                    cur=j;
                }
            }
            if(cur==-1) return -1;
            visited[cur]=true;
            totalCost+=min;
            //更新权值
            for (Edge edge : edges) {
                //a
                if(cur== edge.a && !visited[edge.b] && edge.c<minCost[edge.b]){
                    minCost[edge.b]= edge.c;
                }
                //b
                if(cur== edge.b && !visited[edge.a] && edge.c<minCost[edge.a]){
                    minCost[edge.a]= edge.c;
                }
            }
        }
        return totalCost;
    }
}

2.自我感悟和收获

Kruscal:

他的思路是讲所有的权值进行升序（从小到大的顺序）排列，从小的卡死机进行totalWeight+=;

而每次处理的前提条件是这两个节点不连通，此时就需要借助QuickUnion并查集的find来判断两个是否连通。而且最小生成树的特点是不能形成环，通过判断两个节点不连通就可以巧妙的满足这一点（例如：1-2，2-3，3-4，通过判断1和4是否联通，发现已经联通了，就不会进行成环的操作，也就是不会进行4-1，保证了最小生成树的特征）

Prim:

首先他是一个过程状态表，图中记录着各自节点的权值、激活与否的状态、从哪个节点访问过来的（parent）。

他的思路是先将所有的权值都初始化为最大值并随机选一个节点作为起始节点，让该节点的权值变为0。下一步
1.找所有节点中满足未被激活且权值最小的节点，并记录该新节点及其权值。

2.把该新节点激活，权值加到totalWeight中去。

3.更新该新节点的邻居节点中未被激活的节点的权值，保证该权值比之前存的小。回到1.继续找最小权值节点。

外层for循环的次数等于节点数

重点：if(cur==-1) return -1;[解释：当中间某一轮的时候发现新节点没有满足条件的邻居节点的时候，就没办法更新权值，当新的一轮开始的时候，就找不到最小权值，导致cur没变，仍然是-1，说明该图没办法连通，也就是没办法生成最小生成树，错误就返回-1]

复习：01dx数据结构与算法视频

3.复杂度分析

一、三种算法对比表

算法	时间复杂度	空间复杂度	核心思想	适用场景
Kruskal	O(E log E)	O(E)	排序 + 并查集，贪心选最小边	稀疏图、边数少、点多
Prim 朴素版	O(V²)	O(V²)	维护 minDist，每轮扫描找最小值	稠密图、完全图（如 1584）
Prim 堆优化版	O(E log V)	O(V + E)	优先队列取最小值	稀疏图、边数少、通用

场景1：完全图（如 LeetCode 1584）

• E ≈ V² / 2

• Kruskal：需要排序 O(E log E) ≈ V² log V，太慢

• Prim 朴素版：O(V²) ✅ 最快

• Prim 堆优化：O(E log V) ≈ V² log V，比朴素慢

结论：用 Prim 朴素版

---

场景2：稀疏图（如 TIOJ 1211，E 接近 V）

• Kruskal：O(E log E) ≈ V log V ✅ 很快

• Prim 朴素版：O(V²) ❌ 太慢

• Prim 堆优化版：O(E log V) ≈ V log V ✅ 也快

结论：Kruskal 或 Prim 堆优化版都可以

---

场景3：巨型图（V = 10⁵, E = 10⁵~10⁶）

• Kruskal：排序 E log E ✅ 通常够用

• Prim 朴素版：O(V²) = 10^10 ❌ 完全不可行

• Prim 堆优化：O(E log V) ≈ 10⁶ × 17 ✅ 可行

结论：Kruskal 或 Prim 堆优化版

术语	通俗解释	数学定义
完全图	每两个节点之间都有一条边	E = V × (V-1) / 2
稠密图	边数很多，接近完全图	E ≈ V²
稀疏图	边数很少，远小于 V²	E ≈ V 或 V log V

关键：完全图是一种特殊的稠密图（最稠密的那种），但稠密图不一定是完全图。

总结：

1. 完全图一定是稠密图，但稠密图不一定是完全图 ✅

2. 稀疏图推荐 Kruskal ✅

3. 稠密图推荐 Prim 普通版，Kruskal 能用但没 Prim 高效 ✅

4. Prim 堆优化适合稀疏图 ✅

5. Prim 堆优化版在稀疏图上效率很高，但代码细节多（visited 重复入队、优先队列状态），比 Kruskal 更容易写错。