Recursive DFS graph traversal in Scala

Question

I've seen the following code to traverse a graph depth first, in Scala:

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

It seems to me this code is not correct as shown with the following example.

Nodes are 1, 2, 3. Edges are 1 -> 3, 1 -> 2, 2 -> 3

dfs(1, Set.empty) would visit node 1, then node 3, then node 2, then node 3 again because we don't maintain a global Set of seen nodes, but only add them in the recursive call to dfs.

What would instead be a correct implementation of DFS in Scala, without using mutable structures?

https://stackoverflow.com/questions/8716313/graph-traversal-in-scala https://stackoverflow.com/questions/5471234/how-to-implement-a-dfs-with-immutable-data-types — Dmytro Mitin, Dec 24 '22 at 18:29
I have another example here: https://scastie.scala-lang.org/BalmungSan/5ckJvLDQTvyRK1s1d7wZag/1 - Although, I don't remember if it was DFS or BFS. — Luis Miguel Mejía Suárez, Dec 24 '22 at 18:34

score 0 · Answer 1 · answered Dec 28 '22 at 09:57

Something like this should work (though you might consider the foldLeft to be cheating a little):

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)) 
}

Recursive DFS graph traversal in Scala

1 Answers1