Overview
- An identifier
- A load factor, load(v)
- A parent tree(v)
- The adjacent vertices adj(v)
PQ <- V(G)
foreach u in PQ
load(u) <- INFINITY
while PQ nonEmpty
do u <- v in adj(u)
if v in PQ && load(v) < w(u,v)
then
tree(v) <- u
load(v) <- w(u,v)
Graph definition
- numVertices number of vertices
- start index of the root of the minimum spanning tree
- id identifier (arbitrary an integer)
- load dynamic load (or key) on the vertex
- tree reference to the minimum spanning tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| final class Graph(numVertices: Int, start: Int = 0) {
class Vertex(val id: Int,
var load: Int = Int.MaxValue,
var tree: Int = -1)
val vertices = List.tabulate(numVertices)(new Vertex(_))
vertices.head.load = 0
val edges = new HashMap[Vertex, HashMap[Vertex, Int]]
def += (from: Int, to: Int, weight: Int): Unit = {
val fromV = vertices(from)
val toV = vertices(to)
connect(fromV, toV, weight)
connect(toV, fromV, weight)
}
def connect(from: Vertex, to: Vertex, weight: Int): Unit = {
if( !edges.contains(from))
edges.put(from, new HashMap[Vertex, Int])
edges.get(from).get.put(to, weight)
}
// ...
}
|
Priority queue
1
2
3
4
5
6
7
8
9
10
11
12
| class PQueue(vertices: List[Vertex]) {
var queue = vertices./:(new PriorityQueue[Vertex])((pq, v) => pq += v)
def += (vertex: Vertex): Unit = queue += vertex
def pop: Vertex = queue.dequeue
def sort: Unit = {}
def push(vertex: Vertex): Unit = queue.enqueue(vertex)
def nonEmpty: Boolean = queue.nonEmpty
}
type MST = ListBuffer[Int]
implicit def orderingByLoad[T <: Vertex]: Ordering[T] = Ordering.by( - _.load)
|
Notes:
- The type T has to be a sub-class of Vertex. A direct conversion from Vertex type to Ordering[Vertex] is not allowed in Scala.
- We use the PriorityQueue from the Java library as it provides more flexibility than the Scala TreeSet.
Prim's algorithm
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
| def prim: List[Int] = {
val queue = new PQueue(vertices)
@scala.annotation.tailrec
def prim(parents: MST): Unit = {
if( queue.nonEmpty ) {
val head = queue.pop
val candidates = edges.get(head).get
.filter{
case(vt,w) => vt.tree == -1 && w <= vt.load
}
if( candidates.nonEmpty ) {
candidates.foreach {case (vt, w) => vt.load = w }
queue.sort
}
parents.append(head.id)
head.tree = 1
prim(parents)
}
}
val parents = new MST
prim(parents)
parents.toList
}
|
Time complexity
- Minimum spanning tree with linear queue: V2
- Minimum spanning tree with binary heap: (E + V).LogV
- Minimum spanning tree with Fibonacci heap: V.LogV
References
[2] Lecture 7: Minimum Spanning Trees and Prim’s Algorithm Dekai Wu, Department of Computer Science and Engineering - The Hong Kong University of Science & Technology
[3] Graph Theory Chapter 4 Optimization Involving Tree - V.K. Balakrishnan - Schaum's Outlines Series, McGraw Hill, 1997