Scala中的递归DFS图遍历

zed5wv10 于 2022-12-29 发布在 Scala

关注(0)|答案(1)|浏览(136)

我在Scala中看到过以下代码，它首先遍历图的深度：

def dfs(node: Node, seen: Set[Node]) = {
    visit(node)
    node.neighbours.filterNot(seen).foreach(neighbour => dfs(node, seen + node))
}

在我看来，这段代码是不正确的，如下面的示例所示。
结点为1、2、3。边为1 -〉3、1 -〉2、2 -〉3
dfs(1, Set.empty)将访问节点1，然后是节点3，然后是节点2，然后再次访问节点3，因为我们没有维护全局可见节点集，而只是在递归调用dfs时添加它们。
在Scala中，如果不使用可变结构，正确的DFS实现是什么？

scala

来源：https://stackoverflow.com/questions/74909544/recursive-dfs-graph-traversal-in-scala

1条答案

按热度按时间

bis0qfac1#

类似这样的东西应该可以工作（尽管你可能会认为foldLeft有一点欺骗）：

def dfs(node: Node): Set[Node] = {
  def helper(parent: Node, seen: Set[Node]): Set[Node] = {
    neighbors(parent).foldLeft(seen)({ case (nowSeen, child) =>
      if (nowSeen.contains(child)) nowSeen else {
        visit(child)
        helper(child, nowSeen + child)
      }
    })        
  }

  visit(node)
  helper(node, Set(node)) 
}

赞(0）回复(0）举报 2022-12-29

我来回答

Scala中的递归DFS图遍历

1条答案

相关问题

热门标签

最新问答