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

You could always try an alternative and more functional approach to the Graph datatype:

Martin Erwig. 2001. Inductive graphs and functional graph algorithms. J. Funct. Program. 11, 5 (September 2001), 467-492. DOI=10.1017/S0956796801004075

于 2013-10-16T20:53:19.923 回答