Day57--圖論--53. 尋寶（卡碼網）

Day57–圖論–53. 尋寶（卡碼網）

今天學習：最小生成樹。有兩種算法（Prim和Kruskal）和一道例題。

prim 算法是維護節點的集合，而 Kruskal 是維護邊的集合。

最小生成樹：所有節點的最小連通子圖，即：以最小的成本（邊的權值）將圖中所有節點連接到一起。

53. 尋寶（卡碼網）

方法：Prim最小生成樹

思路：

第一步，選距離生成樹最近節點
第二步，最近節點加入生成樹
第三步，更新非生成樹節點到生成樹的距離（即更新minDist數組）（minDist數組用來記錄每一個節點距離最小生成樹的最近距離。）

import java.util.*;public 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);}for (int i = 0; i < e; i++) {int from = in.nextInt();int to = in.nextInt();int val = in.nextInt();grid[from][to] = val;grid[to][from] = val;}int[] minDist = new int[v + 1];Arrays.fill(minDist, 10001);boolean[] isInTree = new boolean[v + 1];for (int i = 1; i < v; i++) {int cur = -1;int minVal = Integer.MAX_VALUE;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];}}}int sum = 0;for (int i = 2; i <= v; i++) {sum += minDist[i];}System.out.println(sum);}
}

方法：Kruskal最小生成樹

思路：

邊的權值排序，因為要優先選最小的邊加入到生成樹里
遍歷排序后的邊
- 如果邊首尾的兩個節點在同一個集合，說明如果連上這條邊圖中會出現環
- 如果邊首尾的兩個節點不在同一個集合，加入到最小生成樹，并把兩個節點加入同一個集合

import java.util.*;class Disjoint {private int[] father;public Disjoint(int n) {father = new int[n + 1];for (int i = 0; i <= n; i++) {father[i] = i;}}public int find(int a) {if (a == father[a]) {return a;} else {return father[a] = find(father[a]);}}public boolean isSame(int o1, int o2) {return find(o1) == find(o2);}public void join(int o1, int o2) {int root1 = find(o1);int root2 = find(o2);if (root1 == root2) {return;}father[root2] = root1;}
}public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int v = in.nextInt();int e = in.nextInt();Disjoint dj = new Disjoint(v);int[][] edges = new int[e][3];for (int i = 0; i < e; i++) {edges[i][0] = in.nextInt();edges[i][1] = in.nextInt();edges[i][2] = in.nextInt();}Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));int sum = 0;for (int i = 0; i < e; i++) {int n1 = edges[i][0];int n2 = edges[i][1];int val = edges[i][2];if (!dj.isSame(n1, n2)) {dj.join(n1, n2);sum += val;}}System.out.println(sum);}
}