1

私は関数型プログラミングをよりよく理解しようとしており、いくつかの古典的なグラフ アルゴリズムを実装することにしました。BFS ループを末尾再帰関数にラップすることで接続を実装しましたが、このコードは命令よりもはるかに優れているようには見えません。それをより適切に実装する方法はありますか (for内包表記、モナドなどを使用)?

object Graph {
  def apply(n: Int) = new Graph(n, Vector.fill(n)(List.empty[Int]))
}

class Graph private (val n: Int, val adj: IndexedSeq[List[Int]])  {
  def addEdge(u: Int, v: Int) = {
    new Graph(n, adj.updated(u, v :: adj(u)).updated(v, u :: adj(v)))
  }


  def connected = {
    @tailrec
    def connectedIter(q: Queue[Int], visited: Seq[Boolean]) : Boolean = {
      if(q.isEmpty) visited.forall(x => x) else {
        val (v, newq) = q.dequeue
        val newVisited = visited.updated(v, true)
        connectedIter(adj(v).foldLeft(newq){(acc, x) => if(visited(x)) acc else acc.enqueue(x)}, newVisited)
      }
    }

    connectedIter(Queue[Int](0), IndexedSeq.fill(n)(false))
  }
}

PS本質的に再帰的なDFSを使用すると、少し見栄えが良くなります

  def reachableDfs(v: Int): Seq[Boolean] = reachableDfs(v, Vector.fill(n)(false))

  private def reachableDfs(v: Int, visited: Seq[Boolean]) : Seq[Boolean] = {
    val newV = visited.updated(v, true)
    adj(v).filterNot{x => newV(x)}.foldLeft(newV){(acc, x) => reachableDfs(x, acc)}
  }
4

2 に答える 2

1

これは操作で表現できますがSet、これは効率が悪いかもしれません。

object Graph {
  def apply(n: Int) = new Graph(n, Vector.fill(n)(Set.empty))
}

class Graph private (val n: Int, val adj: IndexedSeq[Set[Int]]) {
  def addEdge(u: Int, v: Int) = {
    new Graph(n, adj.updated(u, adj(u) + v).updated(v, adj(v) + u))
  }

 def connected = {
  @tailrec
  def connectedIter(q: Queue[Int], visited: Set[Int]): Boolean = {
    if (q.isEmpty) visited.size == n else {
      val (v, newq) = q.dequeue
      connectedIter(newq enqueue (adj(v) -- visited), visited ++ adj(v))
    }
  }

 connectedIter(Queue(0), Set.empty)
 }
}
于 2013-10-16T13:37:16.390 に答える
0

Graph データ型に対して、別のより機能的なアプローチをいつでも試すことができます。

マーティン・エルウィグ。2001.帰納グラフと関数グラフアルゴリズム。Ｊ．Ｆｕｎｃｔ．プログラム。11、5 (2001 年 9 月)、467-492。DOI=10.1017/S0956796801004075

于 2013-10-16T20:53:19.923 に答える