如何使用不可变的数据类型实现DFS [英] How to implement a DFS with immutable data types

问题描述

我正在尝试一种遍历图Scala样式的整洁方式，最好使用val和不可变的数据类型.

I'm trying to figure out a neat way of traversing a graph Scala-style, preferably with vals and immutable data types.

给出下图，

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.

I'd like the output to be the depth first traversal starting in a given node. Starting in 1 for instance, should yield for instance 1 2 3 0 4.

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

I can't seem to figure out a nice way of doing this without mutable collections or vars. Any help would be appreciated.

推荐答案

尾递归解决方案:

  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
  }

这篇关于如何使用不可变的数据类型实现DFS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！