Scala入門・幅優先探索

Scala

動機

幅優先探索(などのグラフアルゴリズム)を学部生に教える授業に参加した。
よい機会なので、Scalaになじむため幅優先探索を実装した。

方針

幅優先探索はグラフをたどるだけではなく
たどりつつ、各ノードについてほげほげするのが目的なので
bfsの第2引数を関数にして、ほげほげを抽象化する。
幅優先探索は最初のノードからの深さを計算できるので、ほげほげで使えるようにする。

実装

bfsはテキストほぼそのまま。

package bfs
import scala.collection.mutable

//Directed graph. Each node has one value and children
class Node [A] (v : A){
  var children : List[Node[A]] = List()
  def addChild(n : Node[A]){
    children = n :: children
  }
  
  def clearChildren{
    children = List()
  }
  
  override def toString = "node(" + v.toString + ")"
}

object Bfs {
  def main(args : Array[String]){
    val ns = Array.fromFunction{i : Int => new Node(i)}(5)
    
    ns(0).children = List(ns(1),ns(2),ns(4))
    ns(1).children = List(ns(2),ns(2),ns(3))
    ns(2).children = List(ns(0))
    
    //ノードに来たらプリントしてください。
    bfs(ns(0)){(n , i) =>
      println(n + " @ depth " + i)
    }
  }
  
  //breadth first search
  def bfs[A](n : Node[A])(f : (Node[A], Int) => Unit){
    val visited = mutable.Set[Node[A]]()
    val queue = q((n,0))
    while(!queue.isEmpty){
      val (node, depth) = queue.dequeue()
      if(!visited.contains(node)){
        visited += node
        f(node, depth)
        for(child <- node.children){
            queue += (child, depth+1)
        }
      }
    }
  }
  
  def q[A](elems : A*) : mutable.Queue[A] = {
    val q = new mutable.Queue[A]()
    q.enqueue(elems : _*)
    q
  }
}

実行結果

node(0) @ depth 0
node(1) @ depth 1
node(2) @ depth 1
node(4) @ depth 1
node(3) @ depth 2


いくつかメモ。

  • case classはequalsを実装するのでNodeでは危険
  • varもデフォルトでpublic
  • コレクションnewの際の型を書くのが面倒
  • なぜQueue(object).applyがないのか？
  • Array.fromFunctionは多次元版オーバーロード多数あり
  • はてなでScalaのシンタックスハイライトはしてくれないらしい