我知道图形遍历(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
循环编写该版本一样。