The background of the question might be interesting. My students have just finished a course in Graph Theory where they implemented several graph algorithms in Python. Now some are taking Scala as an elective. For lecture #1, I’m trying to reuse some of the same algorithms that they have fresh in memory and show how to do it in Scala. I’d love it if some of the algorithms appear simpler in Scala.

The problem at hand is given a *graph* in the form of a collection of edges (where collection may be array, set, or list) generate the adjacency *list* which is not a List, but rather a mapping vertex vertex to collection of neighboring vertices. In the lecture I go through about 10 different ways to implement this function in Scala, using Array, Set, and Map, all using immutable data structures.

Here are the different approaches I show them, using pattern matching, recursion, `foldLeft`

, pre-initialized Map/Array, uninitialized Map/Array, `Array.tabulate`

, and several other techniques.

I personally think the examples are good because they give examples to the students of how to use the *basic* data structures on algorithms they already know.