# BFS and DFS in Scala

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)

• Your representation of graphs and nodes is broken. Shouldn't that at least be "type Graph=Map[Vertex,Set[Vertex]]"? Because no vertex should be listed twice as a connection for any other node (assuming that all the edges are undirected). Commented Aug 24, 2013 at 17:34
• Why are you searching this graph? It seems you aren't looking for any particular node, just collecting the whole set of nodes. This doesn't seem generally applicable. Hard to adapt to searching for a node with specific properties. Commented Aug 24, 2013 at 19:18
• @itsbruce you are right about the definition. I have changed that to Set to avoid having that issue. As to why I am doing these searches: I was not looking for any node in particular, but rather wanted to check the logic in my DFS to use it to find strongly connected components. Thanks for the review!
– JPC
Commented Aug 26, 2013 at 13:02

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