プリム法は、重み付き連結グラフの最小全域木を求めるアルゴリズム

prim.scala

import scala.annotation.tailrec

object Main {
  def main(args: Array[String]) {
    prim(sampleGraph).foreach(println)
  }

  // 参考 : http://ja.wikipedia.org/wiki/%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95
  // 例のグラフもwikipediaのものと同じに。
  def prim(g :Graph): Seq[Edge] = {
    val pq = scala.collection.mutable.PriorityQueue[Edge]()
    pq.enqueue(Edge(Vertex("dummy"), Vertex("A"), 0))

    @tailrec
    def f(r: Seq[Edge] = Nil, vd: Seq[Vertex] = Nil): Seq[Edge] = {
      if (pq.isEmpty) r
      else {
        val e = pq.dequeue()
        if (vd.contains(e.to)) f(r, vd)
        else {
          g.es.get(e.to).map { _.foreach { pq.enqueue(_) } }
          f(e +: r, e.to +: vd)
        }
      }
    }
    f()
  }

  case class Graph(es: Map[Vertex, Seq[Edge]])
  case class Vertex(name: String)
  case class Edge(from: Vertex, to: Vertex, weight: Int) extends Ordered[Edge] {
    def compare(e: Edge): Int = e.weight - weight
  }
  type Path = Map[Vertex, Edge]
  def sampleGraph: Graph = Graph(
    Map(
      Vertex("A") -> Seq(
        Edge(Vertex("A"), Vertex("B"), 7),
        Edge(Vertex("A"), Vertex("D"), 5)
      ),
      Vertex("B") -> Seq(
        Edge(Vertex("B"), Vertex("A"), 7),
        Edge(Vertex("B"), Vertex("C"), 8),
        Edge(Vertex("B"), Vertex("D"), 9),
        Edge(Vertex("B"), Vertex("E"), 7)
      ),
      Vertex("C") -> Seq(
        Edge(Vertex("C"), Vertex("B"), 8),
        Edge(Vertex("C"), Vertex("E"), 5)
      ),
      Vertex("D") -> Seq(
        Edge(Vertex("D"), Vertex("A"), 5),
        Edge(Vertex("D"), Vertex("B"), 9),
        Edge(Vertex("D"), Vertex("E"), 15),
        Edge(Vertex("D"), Vertex("F"), 6)
      ),
      Vertex("E") -> Seq(
        Edge(Vertex("E"), Vertex("B"), 7),
        Edge(Vertex("E"), Vertex("C"), 5),
        Edge(Vertex("E"), Vertex("D"), 15),
        Edge(Vertex("E"), Vertex("F"), 8),
        Edge(Vertex("E"), Vertex("G"), 9)
      ),
      Vertex("F") -> Seq(
        Edge(Vertex("F"), Vertex("D"), 6),
        Edge(Vertex("F"), Vertex("E"), 8),
        Edge(Vertex("F"), Vertex("G"), 11)
      ),
      Vertex("G") -> Seq(
        Edge(Vertex("G"), Vertex("E"), 9),
        Edge(Vertex("G"), Vertex("F"), 11)
      )
    )
  )
}