Scala is multi-paradigm: OO and functional, mutable and immutable.
Complex graphs are one example of a data structure that, as you have identified, may be easier to work with in a mutable context. If so, make the data structure mutable.
Idiomatic Scala is to use the right paradigm to solve your problem.