In-place maybe not, but what language would be more suitable for graph based algorithms? Of course it depends on how you represent the graph, but writing something like breadth-first search is quite nice and easy to implement in Haskell, in my experience.
This is maybe just me but I find any kind of self referenced data structure a bit awkward to define in haskell. The thing mentioned in http://wiki.haskell.org/Tying_the_Knot .
I generally express graphs as a `Map k (Set k)` or similar, with extra data as desired. Using keys and lookups means you don't need self-references. I guess in a way this approach sacrifices some purity, but I find it works very well.
When you say 'algorithms would look better' this is pretty subjective. Graph based algorithms or inplace algorithms doesn't look too good in haskell.