当前位置：首页 > article >正文

day55 图论章节刷题Part07（[53.寻宝]prim算法、kruskal算法）

article 2024/11/14 12:28:01

前言：使用最小生成树的方法解决将所有节点连接起来所需的最小路径问题。

prim算法

Prim算法是一种贪心算法，从任意一个顶点开始构建最小生成树。每次选择当前已加入生成树的顶点中，距离最近的尚未加入生成树的顶点，直到所有顶点都被加入生成树。

适用场景

稠密图：Prim算法在稠密图（边数接近 n2 ）中表现较好，因为它的复杂度为O(n^2)，其中 n 为节点数量。
单源最短路径：Prim算法可以从任意一个顶点开始构建最小生成树，适合需要从特定顶点开始的情况。

代码实现

prim三部曲：
第一步，选距离生成树最近节点
第二步，最近节点加入生成树
第三步，更新非生成树节点到生成树的距离（即更新minDist数组）

minDist数组用来记录每一个节点距离最小生成树的最近距离。由于题目中说了边的权重最大为10000，这里将边的最大值初始化为10001。

代码如下：

import java.util.*;
public class Main{
    public static void main (String[] args) {
        Scanner scan=new Scanner(System.in);
        int v=scan.nextInt();
        int e=scan.nextInt();
        int[][] grid=new int[v+1][v+1];
        //初始化距离为1001
        for(int i=0;i<=v;i++){
            Arrays.fill(grid[i],10001);
        }
        //根据输入的边的权值建立地图
        for(int i=0;i<e;i++){
            int s=scan.nextInt();
            int t=scan.nextInt();
            int k=scan.nextInt();
            grid[s][t]=k;
            grid[t][s]=k;
        }
        //初始化最小距离为10001
        int[] minDist=new int[v+1];
        Arrays.fill(minDist,1001);
        //建立数组判断节点是否在树中
        boolean[] isInTree=new boolean[v+1];
        //先选择第一个节点加入树中
        minDist[1]=0;
        //外部循环，遍历每一个节点
        for(int i=1;i<=v;i++){
            int minVal=Integer.MAX_VALUE;
            int cur=-1;
            //找到不在树中且距离最近的节点
            for(int j=1;j<=v;j++){
                if(!isInTree[j] && minDist[j]<minVal){
                    minVal=minDist[j];
                    cur=j;
                }
            }
            //将当前节点加入树中
            isInTree[cur]=true;
            //更新节点到数的距离，主要更新与新加入的节点相连的节点
            for(int j=1;j<=v;j++){
                if(!isInTree[j] && grid[cur][j]<minDist[j]){
                    minDist[j]=grid[cur][j];
                }
            }
        }
        //prim算法的循环结束，计算路径总和
        int result=0;
        for(int i=2;i<=v;i++){
            result+=minDist[i];
        }
        System.out.println(result);
    }
}

注意：外部循环是为了确保每个节点都被遍历到。第一个内部循环是找到距离最小生成树最近的节点；第二个内部循环是更新minDist。

kruskal算法

Kruskal算法也是一种贪心算法，但它是从全局角度出发，先将所有边按权重从小到大排序，然后依次选择不形成环的边加入生成树，直到生成树包含所有顶点。

适用场景

稀疏图：Kruskal算法在稀疏图（边数远小于 n2）中表现较好，因为它的复杂度为 nlogn，其中n 为边的数量。
全局最优：Kruskal算法从全局角度出发，适合需要考虑所有边的情况。

代码实现

在代码中，我们可以使用并查集将两个节点加入同一个集合并判断两个节点是否在同一个集合。
时间复杂度：nlogn （快排） + logn （并查集），所以最后依然是 nlogn ，n为边的数量。

代码如下：

import java.util.*;
//定义边的类
class Edge{
    int l,r,val;
    
    Edge(int l,int r,int val){
        this.l=l;
        this.r=r;
        this.val=val;
    }
}

public class Main{
    //题目中节点最多10000，所以初始化并查集的节点10001
    public static int n=10001;
    public static int[] father=new int[n];
    
    public static void init(){
        for(int i=0;i<n;i++){
            father[i]=i;
        }
    }
    
    public static int find(int u){
        return u==father[u]?u:(father[u]=find(father[u]));
    }
    
    public static void join(int u,int v){
        u=find(u);
        v=find(v);
        if(u==v) return;
        else father[v]=u;
    }
    
    public static void main (String[] args) {
        Scanner scan=new Scanner(System.in);
        int v=scan.nextInt();
        int e=scan.nextInt();
        
        List<Edge> edgeList=new LinkedList<>(); 
        for(int i=0;i<e;i++){
            int l=scan.nextInt();
            int r=scan.nextInt();
            int val=scan.nextInt();
            edgeList.add(new Edge(l,r,val));
        }
        
        //排序
        edgeList.sort(Comparator.comparingInt(edge -> edge.val));
        init();
        int result=0;
        for(Edge edge:edgeList){
            int x=find(edge.l);
            int y=find(edge.r);
            if(x!=y){
                result+=edge.val;
                join(x,y);
            }
        }
        System.out.println(result);
    }
}