Lazy Prim MST Algorithm
The Lazy Prim's Minimum Spanning Tree (MST) Algorithm is a graph-based algorithm used to find the minimum spanning tree of a connected, undirected graph with weighted edges. The algorithm was proposed by Robert Prim in 1957, and it is an example of a greedy algorithm, meaning it makes locally optimal choices at each step with the hope of finding a global optimum. The Lazy Prim's MST Algorithm starts with an arbitrary vertex, and at each step, it adds the lightest edge that connects the current set of vertices to a new vertex, ultimately constructing a tree that spans all the vertices of the graph with the minimum possible total edge weight.
The "lazy" aspect of the algorithm comes from the way it handles the priority queue, which stores the edges that are candidates to be added to the MST. In the Lazy Prim's MST Algorithm, the priority queue is not updated at each step; instead, it continues to hold edges that have become irrelevant due to the addition of new vertices to the MST. When extracting the minimum weight edge from the priority queue, the algorithm checks whether the edge is still valid (i.e., it connects the MST to a new vertex) and discards it if it is not. This lazy approach can lead to a larger priority queue, which may have an impact on the algorithm's efficiency, but it still guarantees the correct construction of the MST. In practical applications, the Lazy Prim's MST Algorithm is often used when the graph is dense or when the cost of updating the priority queue at each step is high.
package org.gs.digraph
import org.gs.graph.{Edge, EdgeWeightedGraph}
import org.gs.queue.MinPQ
import org.gs.set.UF
import scala.annotation.tailrec
import scala.collection.mutable.{ArrayBuffer, Queue}
/** Compute a minimal spanning tree in an edge weighted graph
*
* @constructor creates a new LazyPrimMST with an EdgeWeightedGraph
* @param g EdgeWeightedGraph
* @see [[https://algs4.cs.princeton.edu/43mst/LazyPrimMST.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
class LazyPrimMST(g: EdgeWeightedGraph) {
private var _weight: Double = 0.0
private val mst = new Queue[Edge]()
private val marked = Array.fill[Boolean](g.numV)(false)
private val pq = new MinPQ[Edge](new ArrayBuffer((g.e) * 2))
for {
v <- 0 until g.numV
if (!marked(v))
} prim(v)
/** returns sum of edge weights in a MST */
def weight(): Double = _weight
/** returns edges of a MST */
def edges(): List[Edge] = mst.toList
private def scan(v: Int) {
require(!marked(v), s"v:$v is already marked")
marked(v) = true
g.adj(v) foreach (ed => if (!marked(ed.other(v))) pq.insert(ed))
}
private def prim(s: Int): Unit = {
scan(s)
@tailrec
def loop(): Unit = {
def doEdge(edg: Edge) {
val v = edg.either
val w = edg.other(v)
val vM = marked(v)
val wM = marked(w)
require(vM || wM, "Edge:$edg has no marked endpoint")
if (!(vM && wM)) {
mst.enqueue(edg)
_weight += edg.weight
if (!vM) scan(v)
if (!wM) scan(w)
}
}
if (!pq.isEmpty) {
pq.pop match {
case Some(e) => doEdge(e)
case None => throw new NoSuchElementException("Priority queue underflow")
}
loop()
}
}
loop()
}
/** Validate */
def checkIsMinSpanningForest(): Boolean = {
val uf = new UF(g.numV)
def mstEdges(e: Edge) {
mst foreach (f => if (f != e) uf.union(f.either, f.other(f.either)))
}
def minWeightInCrossingCut(e: Edge): Boolean = {
def cutCheck(f: Edge): Boolean = {
if (!uf.connected(f.either, f.other(f.either)) && f.weight < e.weight) false else true
}
@tailrec
def loopE(es: Seq[Edge]): Boolean = es match {
case last +: Seq() => cutCheck(last)
case head +: tail => if(cutCheck(head)) loopE(tail) else false
}
loopE(g.edges)
}
val es = edges
@tailrec
def loopMW(es: Seq[Edge]): Boolean = {
def doEdge(e: Edge): Boolean = {
mstEdges(e)
if (!minWeightInCrossingCut(e)) false else true
}
es match {
case last +: Seq() => doEdge(last)
case head +: tail => if(doEdge(head)) loopMW(tail) else false
}
}
loopMW(es)
}
}
