我知道图形遍历(DFS和BFS)实现使用可变的“访问”顶点集。您将如何仅使用不可变的数据结构来实现它们?

我看到了this question。现在我想知道是否还有其他解决方案

最佳答案

这是一种实现方法:

def traverse[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A]) : Seq[A] = {
  if(toVisit.isEmpty) {
    Seq.empty
  } else {
    val next = toVisit.head
    val succ = (graph(next) -- visited -- toVisit).toSeq
    // DFS :
    // next +: traverse(graph, succ ++ toVisit.tail, visited + next)
    // BFS :
    next +: traverse(graph, toVisit.tail ++ succ, visited + next)
  }
}

def traverseFrom[A](graph : Map[A,Set[A]], initial : A) =
  traverse(graph, Seq(initial), Set.empty)

技巧很简单,就是绕过要访问的节点列表(这将与命令式算法中的堆栈或队列相对应)以及已访问状态集。

如果您担心每次递归调用后调用堆栈都会增加,可以通过使用额外的参数使其变为尾递归:
@annotation.tailrec
def traverseTR[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A], accumulator : Seq[A]) : Seq[A] = {
  if(toVisit.isEmpty) {
    accumulator
  } else {
    val next = toVisit.head
    val succ = (graph(next) -- visited -- toVisit).toSeq
    // DFS :
    //traverseTR(graph, succ ++ toVisit.tail, visited + next, accumulator :+ next)
    // BFS :
    traverseTR(graph, toVisit.tail ++ succ, visited + next, accumulator :+ next)
  }
}

def traverseFrom[A](graph : Map[A,Set[A]], initial : A) =
  traverseTR(graph, Seq(initial), Set.empty, Seq.empty)

这将为您提供一个高效的版本,就像您使用while循环编写该版本一样。

10-08 08:22
查看更多