P 算法與 K 算法作者：Grey
原文地址：
博客園：P 算法與 K 算法
CSDN：P 算法與 K 算法
說明P 算法和 K 算法主要用來解決最小生成樹問題，即：不破壞連通性刪掉某些邊 ， 使得整體的權重最小 。
測評鏈接：?？?最小生成樹
K 算法【P 算法與 K 算法】K 算法使用的核心數據結構是并查集，然后將邊權值排序 。
1）總是從權值最小的邊開始考慮，依次考察權值依次變大的邊
2）當前的邊要么進入最小生成樹的集合，要么丟棄
3）如果當前的邊進入最小生成樹的集合中不會形成環，就要當前邊
4）如果當前的邊進入最小生成樹的集合中會形成環，就不要當前邊
5）考察完所有邊之后，最小生成樹的集合也得到了
邊存在小根堆里面，保證每次彈出的都是權重最小的值
點存在并查集中，每次加入一個邊 ， 就把兩個邊的點 union
完整代碼如下
import java.util.Arrays;import java.util.Comparator;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int[][] graph = new int[m][3];for (int i = 0; i < m; i++) {// fromgraph[i][0] = in.nextInt();// tograph[i][1] = in.nextInt();// weightgraph[i][2] = in.nextInt();}System.out.println(k(graph, n));in.close();}// k算法生成最小生成樹public static int k(int[][] graph, int n) {UnionFind uf = new UnionFind(n);Arrays.sort(graph, Comparator.comparingInt(o -> o[2]));int ans = 0;for (int[] edge : graph) {if (!uf.same(edge[0], edge[1])) {uf.union(edge[0], edge[1]);ans += edge[2];}}return ans;}public static class UnionFind {private final int[] parent;private final int[] size;private final int[] help;public UnionFind(int n) {parent = new int[n + 1];size = new int[n + 1];help = new int[n + 1];for (int i = 1; i < n; i++) {parent[i] = i;size[i] = 1;}}public boolean same(int a, int b) {return find(a) == find(b);}private int find(int a) {int index = 0;while (a != parent[a]) {help[index++] = a;a = parent[a];}index--;while (index > 0) {parent[help[index--]] = a;}return a;}public void union(int a, int b) {int f1 = find(a);int f2 = find(b);if (f1 != f2) {int size1 = size[f1];int size2 = size[f2];if (size1 > size2) {parent[f2] = f1;size[f2] = 0;size[f1] = size1 + size2;} else {parent[f1] = f2;size[f1] = 0;size[f2] = size1 + size2;}}}}}P 算法1）可以從任意節點出發來尋找最小生成樹
2）某個點加入到被選取的點中后，解鎖這個點出發的所有新的邊
3）在所有解鎖的邊中選最小的邊，然后看看這個邊會不會形成環
4）如果會，不要當前邊，繼續考察剩下解鎖的邊中最小的邊，重復3）
5）如果不會 ， 要當前邊，將該邊的指向點加入到被選取的點中 ， 重復2）
6）當所有點都被選取，最小生成樹就得到了
完整代碼如下
import java.util.*;public class Main {public static Set<Edge> P(Graph graph) {// 解鎖的邊進入小根堆PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));// 哪些點被解鎖出來了HashSet<Node> nodeSet = new HashSet<>();Set<Edge> result = new HashSet<>(); // 依次挑選的的邊在result里for (Node node : graph.nodes.values()) { // 隨便挑了一個點// node 是開始點if (!nodeSet.contains(node)) {nodeSet.add(node);for (Edge edge : node.edges) { // 由一個點，解鎖所有相連的邊priorityQueue.add(edge);}while (!priorityQueue.isEmpty()) {Edge edge = priorityQueue.poll(); // 彈出解鎖的邊中，最小的邊Node toNode = edge.to; // 可能的一個新的點if (!nodeSet.contains(toNode)) { // 不含有的時候，就是新的點nodeSet.add(toNode);result.add(edge);for (Edge nextEdge : toNode.edges) {priorityQueue.add(nextEdge);}}}}// 如果有森林 ， 就不能break，如果沒有森林，就可以break//break;}return result;}public static class Graph {public HashMap<Integer, Node> nodes;public HashSet<Edge> edges;public Graph(int n) {nodes = new HashMap<>();edges = new HashSet<>(n);}}public static class Node {public int value;public int in;public int out;public ArrayList<Node> nexts;public ArrayList<Edge> edges;public Node(int value) {this.value = https://www.huyubaike.com/biancheng/value;in = 0;out = 0;nexts = new ArrayList<>();edges = new ArrayList<>();}}public static class Edge {public int weight;public Node from;public Node to;public Edge(int weight, Node from, Node to) {this.weight = weight;this.from = from;this.to = to;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();Graph graph = new Graph(n);for (int i = 0; i < m; i++) {int from = in.nextInt();int to = in.nextInt();int weight = in.nextInt();if (!graph.nodes.containsKey(from)) {graph.nodes.put(from, new Node(from));}if (!graph.nodes.containsKey(to)) {graph.nodes.put(to, new Node(to));}Node fromNode = graph.nodes.get(from);Node toNode = graph.nodes.get(to);Edge fromToEdge = new Edge(weight, fromNode, toNode);Edge toFromEdge = new Edge(weight, toNode, fromNode);fromNode.nexts.add(toNode);fromNode.out++;fromNode.in++;toNode.out++;toNode.in++;fromNode.edges.add(fromToEdge);toNode.edges.add(toFromEdge);graph.edges.add(fromToEdge);graph.edges.add(toFromEdge);}Set