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

发布时间：2020-12-16 09:00:14 所属栏目：安全来源：网络整理

导读：我试图找出一种遍历图形 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

我试图找出一种遍历图形 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
  }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!