如何使用不可变数据类型实现DFS

Question

我试图找出一种遍历图形Scala样式的简洁方法,最好是使用val和不可变数据类型.

给出以下图表,

val graph = Map(0 -> Set(1),
                1 -> Set(2),
                2 -> Set(0, 3, 4),
                3 -> Set(),
                4 -> Set(3))

我希望输出是在给定节点中开始的深度优先遍历.例如,从1开始,应该屈服1 2 3 0 4.

如果没有可变的集合或变量,我似乎无法找到一个很好的方法.任何帮助,将不胜感激.

Answer 1

尾递归解决方案:

  def traverse(graph: Map[Int, Set[Int]], start: Int): List[Int] = {
    def childrenNotVisited(parent: Int, visited: List[Int]) =
      graph(parent) filter (x => !visited.contains(x))

    @annotation.tailrec
    def loop(stack: Set[Int], visited: List[Int]): List[Int] = {
      if (stack isEmpty) visited
      else loop(childrenNotVisited(stack.head, visited) ++ stack.tail, 
        stack.head :: visited)
    }
    loop(Set(start), Nil) reverse
  }

Answer 2

这是递归解决方案（希望我正确理解您的要求）：

def traverse(graph: Map[Int, Set[Int]], node: Int, visited: Set[Int] = Set()): List[Int] = 
    List(node) ++ (graph(node) -- visited flatMap(traverse(graph, _, visited + node)))

traverse(graph, 1)

另请注意，该函数不是尾递归。