P 演算法與 K 演算法
P 演算法與 K 演算法
作者：Grey
原文地址：
說明
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++) {
// from
graph[i][0] = in.nextInt();
// to
graph[i][1] = in.nextInt();
// weight
graph[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 = 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<Edge> result = P(graph);
int sum = 0;
for (Edge edge : result) {
sum += edge.weight;
}
System.out.println(sum);
in.close();
}
}
