Core User Guide: Run-time Characteristics

The default Graph implementation is based on scala.collection.mutable.HashMap thus having a reasonably good performance. Also, it is guaranteed that the only limit for storing Graph instances and calling Graph algorithms is the JVM heap space, as the implementation of all algorithms is tail recursive. Typically, it is fast to instantiate graphs made up of several hundred thousands of nodes and edges.

In terms of the Big-O notation, operation costs on graphs with the default Graph implementation can be summarized as follows:

Operation Cost of Operation
Instance Creation O(V + E)
element addition O(1)
element removal O(1)
element look-up O(1)
set-based traversal O(V + E)
root-based traversal O(V + E)
path search O(V + E)
shortest path search O(VlogV + E)

If you seek better performance with respect to your use case, one option is to ask for a special implementation. But, provided time is not your main concern, you may as well provide it yourself what should be a straightforward process thanks to the extendible nature of the Graph for Scala design.