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?

stackoverflow.com/questions/8716313/graph-traversal-in-scala stackoverflow.com/questions/5471234/… — Dmytro Mitin
– Dmytro Mitin, Commented Dec 24, 2022 at 18:29
I have another example here: scastie.scala-lang.org/BalmungSan/5ckJvLDQTvyRK1s1d7wZag/1 - Although, I don't remember if it was DFS or BFS. — Luis Miguel Mejía Suárez
– Luis Miguel Mejía Suárez, Commented Dec 24, 2022 at 18:34

Jason Scott Lenderman · Accepted Answer · 2022-12-28 09:57:12Z

0

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

answered Dec 28, 2022 at 9:57

Jason Scott Lenderman

1,91811 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recursive DFS graph traversal in Scala

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related