title: How to implement a DFS with immutable data types
body: <p>I'm trying to figure out a neat way of traversing a graph Scala-style, preferably with vals and immutable data types.</p>
  
  <p>Given the following graph,</p>
  
  <pre><code>val graph = Map(0 -&gt; Set(1),
                  1 -&gt; Set(2),
                  2 -&gt; Set(0, 3, 4),
                  3 -&gt; Set(),
                  4 -&gt; Set(3))
  </code></pre>
  
  <p>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 <code>1 2 3 0 4</code>.</p>
  
  <p>I can't seem to figure out a nice way of doing this without mutable collections or vars. Any help would be appreciated.</p>