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

我正在尝试找出一种 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.

如果没有可变集合或变量，我似乎无法找到一种很好的方法来做到这一点。任何帮助，将不胜感激。

尾递归解决方案：

  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
  }