AcWing 858. Prim算法求最小生成树

Problem: AcWing 858. Prim算法求最小生成树

思路

这是一个经典的图论问题，要求找到一个图的最小生成树。最小生成树是一个图的所有顶点和最小的边的集合，使得所有的顶点都被连接在一起，且总的边的权值最小。
解决这个问题的一个常见方法是使用Prim算法。Prim算法的基本思想是从一个顶点开始，每次选择一条连接已经在树中的顶点和不在树中的顶点的最小权值的边，将这条边以及它的另一个顶点加入到树中，直到所有的顶点都被加入到树中。

解题方法

初始化一个优先队列（最小堆），用于存储所有的边，边的权值越小，优先级越高。
从顶点1开始，将所有与顶点1相连的边加入到优先队列中。
从优先队列中取出一条边，如果这条边的另一个顶点已经在树中，则忽略这条边；否则，将这条边以及它的另一个顶点加入到树中，并将所有与这个顶点相连的边加入到优先队列中。
重复步骤3，直到所有的顶点都被加入到树中，或者优先队列为空。
如果所有的顶点都被加入到树中，那么树中的边的权值之和就是最小生成树的权值；否则，说明图不连通，无法构成生成树。

复杂度

时间复杂度:

$O(mlogm)$，其中m是边的数量。每条边都会被加入到优先队列中，并从优先队列中取出，每次操作的时间复杂度都是O(logm)。

空间复杂度:

$O(n+m)$，其中n是顶点的数量，m是边的数量。需要O(n)的空间存储顶点的状态，以及O(m)的空间存储边的信息。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int n, m;
	static ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
	static PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);

	public static void main(String[] args) throws IOException {
		n = nextInt();
		m = nextInt();
		graph.clear();
		heap.clear();
		for (int i = 0; i <= n; i++) {
			graph.add(new ArrayList<>());
		}

		for (int i = 0, u, v, w; i < m; i++) {
			u = nextInt();
			v = nextInt();
			w = nextInt();
			graph.get(u).add(new int[] { v, w });
			graph.get(v).add(new int[] { u, w });
		}

		for (int[] edge : graph.get(1)) {
			heap.add(edge);
		}

		boolean[] set = new boolean[n + 1];
		set[1] = true;
		int ans = 0;
		int nodeCnt = 1;

		while (!heap.isEmpty()) {
			int[] edge = heap.poll();
			if (!set[edge[0]]) {
				nodeCnt++;
				set[edge[0]] = true;
				ans += edge[1];
				for(int[] next : graph.get(edge[0])) {
					heap.add(next);
				}
			}
		}
		out.println(nodeCnt == n ? ans : "impossible");
		out.flush();

	}

	static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66