BFS and DFS in Scala
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) =&gt; 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) =&gt; DFS0(a,b))
      }
    }
    DFS0(start,List()).reverse 
  }
}


And then you could do this:

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


or this:

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