How to implement a DFS with immutable data types

I'm trying to figure out a neat way of traversing a graph Scala-style, preferably with vals and immutable data types.

Given the following graph,

val graph = Map(0 -> Set(1),
                1 -> Set(2),
                2 -> Set(0, 3, 4),
                3 -> Set(),
                4 -> Set(3))

I'd like the output to be the depth first traversal starting in a given node. Starting in 1 for instance, should yield for instance 1 2 3 0 4.

I can't seem to figure out a nice way of doing this without mutable collections or vars. Any help would be appreciated.