Graph algorithms

A graph has a finite number of nodes, also commonly called vertices, connected via edges. Trees are special cases of graphs, with additional constraints.

There are undirected and directed graphs. We will be looking at directed graphs, also known as digraphs. I will explain the terms as they come along; however, http://algs4.cs.princeton.edu/42digraph/ would help as a quick refresher/introduction.

A list of pairs will be used to model these directed graphs. The second element of the pair is should be a successor of the first. For example, the m node's successors are {n,p,o}:

The preceding graph is modeled in the following code. Each edge is denoted by a pair, and the graph is a list of such pairs:

scala> val graph = List(("m", "n"), ("m", "o"), ("m", "p"), 
     |              ("n", "q"), ("o", "r"), ("p", "q"), 
     |              ("q", "r"), ("q", "s")) 
graph: List[(String, String)] = List((m,n), (m,o), (m,p), (n,q), (o,r), (p,q), (q,r), (q,s)) 

The succSet method collects...