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.從前序與中序遍歷序列構造二叉樹
)
