Graph traversal in Scala

Question

Graph traversal (DFS and BFS) implementations I know use a mutable set of "visited" vertices. How would you implement them with only immutable data structures?

I saw this question. Now I wonder if there are also other solutions

Answer 1

Here is one way to do it:

def traverse[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A]) : Seq[A] = {
  if(toVisit.isEmpty) {
    Seq.empty
  } else {
    val next = toVisit.head
    val succ = (graph(next) -- visited -- toVisit).toSeq
    // DFS :
    // next +: traverse(graph, succ ++ toVisit.tail, visited + next)
    // BFS :
    next +: traverse(graph, toVisit.tail ++ succ, visited + next)
  }
}

def traverseFrom[A](graph : Map[A,Set[A]], initial : A) =
  traverse(graph, Seq(initial), Set.empty)

The trick is simply to pass around the list of nodes to visit (which would correspond to your stack or queue in an imperative algorithm), and the set of visited states.

If you're worried about the call stack growing with each recursive call, you make it tail-recursive by using an extra argument:

@annotation.tailrec
def traverseTR[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A], accumulator : Seq[A]) : Seq[A] = {
  if(toVisit.isEmpty) {
    accumulator
  } else {
    val next = toVisit.head
    val succ = (graph(next) -- visited -- toVisit).toSeq
    // DFS :
    //traverseTR(graph, succ ++ toVisit.tail, visited + next, accumulator :+ next)
    // BFS :
    traverseTR(graph, toVisit.tail ++ succ, visited + next, accumulator :+ next)
  }
}

def traverseFrom[A](graph : Map[A,Set[A]], initial : A) =
  traverseTR(graph, Seq(initial), Set.empty, Seq.empty)

This will give you a version as efficient as if you wrote it using a while loop.