7. Kruskal 算法¶
7.1. Kruskal 算法¶
我们的下一个 MCST 算法通常被称为 Kruskal 算法。 Kruskal 算法也是一个简单的贪心算法。 首先将顶点集合划分为 \(|\mathbf{V}|\) 个 不相交集合， 每个包含一个顶点。 然后按权值顺序处理边。 如果边连接两个不同不相交集合中的顶点， 则将该边添加到 MCST，并合并两个不相交集合。 此过程重复直到只剩下一个不相交集合。
边可以使用最小堆按权值顺序处理。 这通常比先对边排序更快， 因为在实践中，我们只需要在完成 MCST 之前 访问一小部分边。 这是仅查找列表中 少数最小元素 的一个例子。
此算法唯一棘手的部分是确定两个顶点
是否属于同一个等价类。
幸运的是，理想的算法可用于此目的——
UNION/FIND。
以下是 Kruskal 算法的实现。
类 KruskalElem 用于在最小堆上存储边。
// Kruskal's MST algorithm
void Kruskal(Graph G) {
ParPtrTree A = new ParPtrTree(G.nodeCount()); // Equivalence array
KVPair[] E = new KVPair[G.edgeCount()]; // Minheap array
int edgecnt = 0; // Count of edges
for (int i=0; i<G.nodeCount(); i++) { // Put edges in the array
int[] nList = G.neighbors(i);
for (int w=0; w<nList.length; w++) {
E[edgecnt++] = new KVPair(G.weight(i, nList[w]), new int[]{ i,nList[w] } );
}
}
MinHeap H = new MinHeap(E, edgecnt, edgecnt);
int numMST = G.nodeCount(); // Initially n disjoint classes
for (int i=0; numMST>1; i++) { // Combine equivalence classes
KVPair temp = H.removemin(); // Next cheapest edge
if (temp == null) { return; } // Must have disconnected vertices
int v = ((int[])temp.value())[0];
int u = ((int[])temp.value())[1];
if (A.differ(v, u)) { // If in different classes
A.UNION(v, u); // Combine equiv classes
AddEdgetoMST(v, u); // Add this edge to MST
numMST--; // One less MST
}
}
}
// Kruskal's MST algorithm
void Kruskal(Graph G) {
ParPtrTree A = new ParPtrTree(G.nodeCount()); // Equivalence array
KVPair[] E = new KVPair[G.edgeCount()]; // Minheap array
int edgecnt = 0; // Count of edges
for (int i=0; i<G.nodeCount(); i++) { // Put edges in the array
int[] nList = G.neighbors(i);
for (int w=0; w<nList.length; w++) {
E[edgecnt++] = new KVPair(G.weight(i, nList[w]), new int[]{ i,nList[w] } );
}
}
MinHeap H = new MinHeap(E, edgecnt, edgecnt);
int numMST = G.nodeCount(); // Initially n disjoint classes
for (int i=0; numMST>1; i++) { // Combine equivalence classes
KVPair temp = H.removemin(); // Next cheapest edge
if (temp == null) { return; } // Must have disconnected vertices
int v = ((int[])temp.value())[0];
int u = ((int[])temp.value())[1];
if (A.differ(v, u)) { // If in different classes
A.UNION(v, u); // Combine equiv classes
AddEdgetoMST(v, u); // Add this edge to MST
numMST--; // One less MST
}
}
}
Kruskal 算法由处理边所需的时间主导。
如果使用路径压缩和加权合并，
differ 和 UNION 函数几乎是常数时间。
因此，算法的总成本在最坏情况下为
\(\Theta(|\mathbf{E}| \log |\mathbf{E}|)\)，
此时在找到生成树的所有边之前必须处理几乎所有的边。
更常见的是，生成树的边是较短的那些，
只处理约 \(|\mathbf{V}|\) 条边。
如果是这样，在平均情况下成本通常接近
\(\Theta(|\mathbf{V}| \log |\mathbf{E}|)\)。
