BFS and DFS in Scala

Question

I would love it if someone could give me some suggestions for these 2 graph search functions. I am new to scala and would love to get some insight into making these more idiomatic.

  type Vertex=Int
  type Graph=Map[Vertex,List[Vertex]]
  val g: Graph=Map(1 -> List(2,4), 2-> List(1,3), 3-> List(2,4), 4-> List(1,3))
 //example graph meant to represent
 //  1---2
 //  |   |
 //  4---3

//I want this to return results in the different layers that it finds them (hence the list of list of vertex)     
def BFS(start: Vertex, g: Graph): List[List[Vertex]]={
  val visited=List(start)
  val result=List(List(start))

  def BFS0(elems: List[Vertex],result: List[List[Vertex]], visited: List[Vertex]): List[List[Vertex]]={
    val newNeighbors=elems.flatMap(g(_)).filterNot(visited.contains).distinct
    if(newNeighbors.isEmpty) result
    else BFS0(newNeighbors, newNeighbors :: result, visited ++ newNeighbors)
    }

  BFS0(List(start),result,visited).reverse
   }

//I would really appreciate some input on DFS, I have the feeling there is a way to do this sans var.

 def DFS(start: Vertex, g: Graph): List[Vertex]={
    var visited=List(start)
    var result=List(start)

  def DFS0(start: Vertex): Unit={
     for(n<-g(start); if !visited.contains(n)){
       visited=n :: visited 
       result=n :: result 
       DFS0(n)
  }}
   DFS0(start)
   result.reverse     
} 

//some examples
scala> BFS(1,g)
res84: List[List[Vertex]] = List(List(1), List(2, 4), List(3))
scala> BFS(2,g)
res85: List[List[Vertex]] = List(List(2), List(1, 3), List(4))
scala> DFS(1,g)
res86: List[Vertex] = List(1, 2, 3, 4)
scala> DFS(3,g)
res87: List[Vertex] = List(3, 2, 1, 4)

Answer 1

OK, so I'm going to start with your DFS method. You're right - you should be able to do it without those vars in the outer function. You should be able to work out why - after all, you have vals in the outer layer of your BFS method. Why? Because your BFS uses a recursive helper function, so the vals are only used once (and could be discarded).

So your DFS function should really use recursion, but I suspect you may have rejected recursion because you couldn't see how visited would be properly preserved as a recursive function popped back and forth. The answer is foldLeft.

def DFS(start: Vertex, g: Graph): List[Vertex] = {

  def DFS0(v: Vertex, visited: List[Vertex]): List[Vertex] = {
    if (visited.contains(v))
      visited
    else {
      val neighbours:List[Vertex] = g(v) filterNot visited.contains 
      neighbours.foldLeft(v :: visited)((b,a) => DFS0(a,b))
    } 
  }
  DFS0(start,List()).reverse
} 

I don't have space here to explain foldLeft, if you've never encountered it - maybe Matt Malone's blog post will help. You can rewrite almost anything with foldLeft, although it isn't always a good idea. Definitely the right thing to do here, though. Notice that I completely dropped your result var since visited is the result, the way you are doing this.

My version of your DFS method is entirely functional, which is how Scala really wants to be used. Note also the lack of braces and brackets in

val neighbours:List[Vertex] = g(v) filterNot visited.contains

It can be written

val neighbours:List[Vertex] = g(v).filterNot(visited.contains)

but the Scala style is to omit the brackets and braces except where essential.

Your BFS method is similarly over-populated. I've slimmed it down a little without altering the basic way it works:

def BFS(start: Vertex, g: Graph): List[List[Vertex]] = {

  def BFS0(elems: List[Vertex],visited: List[List[Vertex]]): List[List[Vertex]] = {
    val newNeighbors = elems.flatMap(g(_)).filterNot(visited.flatten.contains).distinct
    if (newNeighbors.isEmpty) 
      visited
    else
      BFS0(newNeighbors, newNeighbors :: visited)
  }

  BFS0(List(start),List(List(start))).reverse
} 

It still gives the same results.

The other big point to make is that while Scala is a functional language it is also an Object Oriented language. Those DFS and BFS methods should belong to a graph object, preferably at least derived from a generic class. Something like this:

class Graph[T] {
  type Vertex = T
  type GraphMap = Map[Vertex,List[Vertex]]
  var g:GraphMap = Map()

  def BFS(start: Vertex): List[List[Vertex]] = {

    def BFS0(elems: List[Vertex],visited: List[List[Vertex]]): List[List[Vertex]] = {
      val newNeighbors = elems.flatMap(g(_)).filterNot(visited.flatten.contains).distinct
      if (newNeighbors.isEmpty)
        visited
      else
        BFS0(newNeighbors, newNeighbors :: visited)
    }

    BFS0(List(start),List(List(start))).reverse
  }

  def DFS(start: Vertex): List[Vertex] = {

    def DFS0(v: Vertex, visited: List[Vertex]): List[Vertex] = {
      if (visited.contains(v))
        visited
      else {
        val neighbours:List[Vertex] = g(v) filterNot visited.contains
        neighbours.foldLeft(v :: visited)((b,a) => DFS0(a,b))
      }
    }
    DFS0(start,List()).reverse 
  }
}

And then you could do this:

scala> var intGraph = new Graph[Int]
scala> intGraph.g = Map(1 -> List(2,4), 2-> List(1,3), 3-> List(2,4), 4-> List(1,3))
scala> intGraph.BFS(1)
res2: List[List[Int]] = List(List(1), List(2, 4), List(3))
scala> intGraph.BFS(2)
res3: List[List[Int]] = List(List(2), List(1, 3), List(4))
scala> intGraph.DFS(3)
res4: List[Int] = List(3, 2, 1, 4)

or this:

scala> var sGraph = new Graph[String]
scala> sGraph.g = Map("Apple" -> List ("Banana","Pear","Grape"), "Banana" -> List("Apple","Plum"), "Pear" -> List("Apple","Plum"), "Grape" -> List("Apple","Plum"), "Plum" -> List ("Banana","Pear","Grape"))
scala> sGraph.BFS("Apple")
res6: List[List[java.lang.String]] = List(List(Apple), List(Banana, Pear, Grape), List(Plum))