普里姆算法（Prim’s algorithm），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
描述
从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。
- 输入：一个加权连通图，其中顶点集合为 $V$，边集合为 $E$；
- 初始化：$V_{new}={x}$，其中 x 为集合 $V$ 中的任一节点（起始点），$E_{new}={ }$；
- 重复下列操作，直到$V_{new}=V$
- 在集合 $E$ 中选取权值最小的边 $(u,v)$，其中 $u$ 为集合 $V_{new}$ 中的元素，而 $v$ 则是 $V$ 中没有加入 $V_{new}$ 的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
- 将 $v$ 加入集合 $V_{new}$ 中，将 $(u,v)$ 加入集合 $E_{new}$ 中；
- 输出：使用集合 $V_{new}$ 和 $E_{new}$ 来描述所得到的最小生成树。
时间复杂度
- 最小边、权的数据结构 - - - 时间复杂度（总计）
- 邻接矩阵、搜索 - - - $O(|V|^2)$
- 二叉堆、邻接表 - - - $\displaystyle O((|V|+|E|)\log|V|)=O(|E|\log|V|)$
- 斐波那契堆、邻接表 - - - ${\displaystyle O(|E|+|V|\log |V|)}$
通过邻接矩阵图表示的简易实现中，找到所有最小权边共需 $O(|V|^{2})$ 的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为 ${\displaystyle O(|E|\log |V|)}$，其中 $|E|$ 为连通图的边集大小，$|V|$ 为点集大小。如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为 ${\displaystyle O(|E|+|V|\log |V|)}$，这在连通图足够密集时（当 $|E|$ 满足 ${\displaystyle \Omega (|V|\log |V|)}{\displaystyle \Omega (|V|\log |V|)}$ 条件时），可较显著地提高运行速度。
Java 实现
-
问题一：如何判断一个图是否为原图的生成子图
-
问题二：如何判断生成子图是一棵树
-
问题三：如何获得最小生成树
-
利用inMST[]数组来判断所有节点是否已在生成树中，详细实现可见allConnected()方法
-
利用inMST[]数组来记录已加入生成树中的节点，以保证无环
-
利用优先队列按照边的权重从小到大排序，可保证最终的生成子树为最小生成子树
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
|
public class Graph {
private int numOfNodes;
private boolean directed;
private boolean weighted;
private double[][] matrix;
// 该数组保存属于 MST 的边的值，这些边将节点连接到其父节点
private double[] edges;
// 提供有关每个节点的父节点的信息
private double[] parents;
// 正在检查的节点是否已经属于 MST
private boolean[] includedInMST;
private boolean[][] isSetMatrix;
public Graph(int numOfNodes, boolean directed, boolean weighted) {
this.directed = directed;
this.weighted = weighted;
this.numOfNodes = numOfNodes;
// Simply initializes our adjacency matrix to the appropriate size
matrix = new double[numOfNodes][numOfNodes];
isSetMatrix = new boolean[numOfNodes][numOfNodes];
edges = new double[numOfNodes];
parents = new double[numOfNodes];
includedInMST = new boolean[numOfNodes];
for(int i = 0; i < numOfNodes; i++){
edges[i] = Double.POSITIVE_INFINITY;
parents[i] = -1;
includedInMST[i] = false;
}
}
}
|
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
67
|
public class Prim {
// 存在横切边的数据结构
private final Queue<int[]> pq;
// 记录已经成为最小生成树的节点
private boolean[] inMST;
// 记录最小生成树的权重和
private Integer weightSum = 0;
// graph 是用邻接表表示的一幅图
// graph[s] 记录节点 s 所有相邻的边
// 三元组 int[]{from, to, weight} 表示一条边
private final List<int[]>[] graph;
public Prim(List<int[]>[] graph) {
this.graph = graph;
// 按照边的权重从小到大排序
this.pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
// 图中有 n 个节点
int n = graph.length;
this.inMST = new boolean[n];
// 随便从一个点开始切分都可以，我们不妨从节点 0 开始
inMST[0] = true;
cut(0);
// 不断进行切分，向最小生成树中添加边
while (!pq.isEmpty()) {
int[] edge = pq.poll();
int to = edge[1];
int weight = edge[2];
if (inMST[to]) {
// 节点 to 已经在最小生成树中，跳过
// 否则这条边会产生环
continue;
}
// 将边 edge 加入最小生成树
weightSum += weight;
inMST[to] = true;
// 节点 to 加入后，进行新一轮切分，会产生更多横切边
cut(to);
}
}
// 将 s 的横切边加入优先队列
private void cut(int x) {
// 遍历 s 的邻边
for (int[] edge : graph[x]) {
int to = edge[1];
if (inMST[to]) {
// 相邻接点 to 已经在最小生成树中，跳过
// 否则这条边会产生环
continue;
}
// 加入横切边队列
pq.offer(edge);
}
}
// 最小生成树的权重和
public int weightSum() {
return this.weightSum;
}
// 判断最小生成树是否包含图中的所有节点
public boolean allConnected() {
for (int i = 0; i < graph.length; i++) {
if (!inMST[i]) {
return false;
}
}
return true;
}
}
|
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
public class Prim {
public static List<Vertex> vertexList = new ArrayList<Vertex>();//结点集
public static List<Edge> EdgeQueue = new ArrayList<Edge>();//边集
public static List<Vertex> newVertex = new ArrayList<Vertex>();//已经 访问过的结点
public static void main(String[] args) {
primTree();
}
public static void buildGraph() {
Vertex v1 = new Vertex("a");
Prim.vertexList.add(v1);
Vertex v2 = new Vertex("b");
Prim.vertexList.add(v2);
Vertex v3 = new Vertex("c");
Prim.vertexList.add(v3);
Vertex v4 = new Vertex("d");
Prim.vertexList.add(v4);
Vertex v5 = new Vertex("e");
Prim.vertexList.add(v5);
addEdge(v1, v2, 6);
addEdge(v1, v3, 7);
addEdge(v2, v3, 8);
addEdge(v2, v5, 4);
addEdge(v2, v4, 5);
addEdge(v3, v4, 3);
addEdge(v3, v5, 9);
addEdge(v5, v4, 7);
addEdge(v5, v1, 2);
addEdge(v4, v2, 2);
}
public static void addEdge(Vertex a, Vertex b, int w) {
Edge e = new Edge(a, b, w);
Prim.EdgeQueue.add(e);
}
public static void primTree() {
buildGraph();
Vertex start = vertexList.get(0);
newVertex.add(start);
for (int n = 0; n < vertexList.size() - 1; n++) {
Vertex temp = new Vertex(start.key);
Edge tempedge = new Edge(start, start, 1000);
for (Vertex v : newVertex) {
for (Edge e : EdgeQueue) {
if (e.start == v && !containVertex(e.end)) {
if (e.key < tempedge.key) {
temp = e.end;
tempedge = e;
}
}
}
}
newVertex.add(temp);
}
Iterator it = newVertex.iterator();
while (it.hasNext()) {
Vertex v = (Vertex) it.next();
System.out.println(v.key);
}
}
public static boolean containVertex(Vertex vte) {
for (Vertex v : newVertex) {
if (v.key.equals(vte.key))
return true;
}
return false;
}
}
class Vertex {
String key;
Vertex(String key) {
this.key = key;
}
}
class Edge {
Vertex start;
Vertex end;
int key;
Edge(Vertex start, Vertex end, int key) {
this.start = start;
this.end = end;
this.key = key;
}
}
|