P 算法与 K 算法

P 算法与 K 算法作者:Grey
原文地址:
博客园:P 算法与 K 算法
CSDN:P 算法与 K 算法
说明P 算法和 K 算法主要用来解决最小生成树问题 , 即:不破坏连通性删掉某些边 , 使得整体的权重最小 。
测评链接:牛客-最小生成树
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 算法【P 算法与 K 算法】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

经验总结扩展阅读