代码随想录算法训练营第六十三天 | prim算法、kruskal算法、复习

53. 寻宝 — prim算法

题目链接：https://kamacoder.com/problempage.php?pid=1053
文档讲解：https://programmercarl.com/kamacoder/0053.%E5%AF%BB%E5%AE%9D-prim.html

思路

本题是最小生成树的模板题，最小生成树可以使用 prim算法，也可以使用 kruskal算法计算出来。
prim算法 是从节点的角度 采用贪心的策略 每次寻找距离 最小生成树最近的节点 并加入到最小生成树中。prim算法核心有三步：

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

其中，minDist数组用来记录每一个节点距离最小生成树的最近距离。minDist数组里的数值初始化为最大数，因为本题 节点距离不会超过 10000，所以初始化最大数为 10001就可以。

代码

import java.util.*;
class Main{
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        int v = in.nextInt();
        int e = in.nextInt();
        int[][] grid = new int[v + 1][v + 1];
        for (int i = 0; i <= v; i++) {
            Arrays.fill(grid[i], 10001);
        }
        int[] minDist = new int[v + 1];
        Arrays.fill(minDist, 10001);
        boolean[] isInTree = new boolean[v + 1];
        for (int i = 0; i < e; i++) {
            int x = in.nextInt(), y = in.nextInt();
            grid[x][y] = in.nextInt();
            grid[y][x] = grid[x][y];
        }
        
        for (int i = 1; i < v; i++) { // 只需要加入v-1条边即可连通
            // 1、prim三部曲，第一步：选距离生成树最近节点
            int cur = -1, minVal = Integer.MAX_VALUE;
            for (int j = 1; j <= v; j++) { // 开始选点
                 //  选取最小生成树节点的条件：
                //  （1）不在最小生成树里
                //  （2）距离最小生成树最近的节点
                if (!isInTree[j] && minDist[j] < minVal) {
                    cur = j;
                    minVal = minDist[j];
                }
            }
            // 2、prim三部曲，第二步：最近节点（cur）加入生成树
            isInTree[cur] = true;
            // 3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
            for (int j = 1; j <= v; j++) {
                if (!isInTree[j] && grid[cur][j] < minDist[j]) {
                    minDist[j] = grid[cur][j];
                }
            }
        }
        
        int res = 0;
        for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边
            res += minDist[i];
        }
        System.out.println(res);
    }
}

53. 寻宝 — kruskal算法

题目链接：https://kamacoder.com/problempage.php?pid=1053
文档讲解：https://programmercarl.com/kamacoder/0053.%E5%AF%BB%E5%AE%9D-Kruskal.html

思路

prim 算法是维护节点的集合，而 kruskal 是维护边的集合。
kruscal的思路：

• 边的权值排序，因为要优先选最小的边加入到生成树里
• 遍历排序后的边
  • 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
  • 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

判断首尾两个节点是否在同一个集合，需要用到并查集。

代码

import java.util.*;
import java.util.stream.Collectors;
class Main{
    static int[] father;
    static int v, e;
    
    static class Edge{
        int left, right, val;
        
        public int getVal(){ return val; }
        
        Edge(int left, int right, int val) {
            this.left = left;
            this.right = right;
            this.val = val;
        }
    }
    
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        v = in.nextInt();
        e = in.nextInt();
        father = new int[v + 1];
        List<Edge> edgeList = new ArrayList<>();
        for (int i = 0; i < e; i++) {
            int m = in.nextInt();
            int n = in.nextInt();
            int dist = in.nextInt();
            edgeList.add(new Edge(m, n, dist));
        }
        // 按边的权值对边进行从小到大排序
        edgeList = edgeList.stream().sorted(Comparator.comparing(Edge::getVal)).
        collect(Collectors.toList());
        init();
        int res = 0;
        for (Edge edge : edgeList) {
            if (!isSame(edge.left, edge.right)) { // 如果不在一个集合中，则加入
                res += edge.val;
                join(edge.left, edge.right);
            }
        }
        System.out.println(res);
    }
    
    public static void init() {
        for (int i = 1; i <= v; i++) father[i] = i;
    }
    
    public static int find(int u) {
        return u == father[u] ? u : (father[u] = find(father[u]));
    }
    
    public static boolean isSame(int u, int v) {
        return find(u) == find(v);
    }
    
    public static void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        father[v] = u;
    }
}

复习二叉树部分

513.找树左下角的值
112.路径总和
113.路径总和ii
106.从中序与后序遍历序列构造二叉树
105.从前序与中序遍历序列构造二叉树