1. Use Rust's runtime safety checks, using Rc, Weak, RefCell, etc. It will be as ergonomic as GC'ed languages (no productivity loss). While this has a runtime performance penalty, it will still be mostly comparable to other languages. This works for most use cases.
2. If you need the last ounce of performance, just drop all automated safety checks and do it manually using unsafe. Even if you make a mistake, your debugging will be limited to the unsafe blocks. This approach isn't unusual in Rust.
3. Use either the standard library or something on crates.io that does what's given in 2. Rust's generics make it easy.
This resource deals with these topics in-depth: https://rust-unofficial.github.io/too-many-lists/
2. No, I don't need every last bit of performance. C++ performance is OK. Or any other sane language like Nim, Crystal, etc. I need async, though, which is yet another hell in Rust.
3. This absolutely can't be done with standard library. There are libraries like PetGraph, which solve this particular problem (by some very unobvious approaches and bits of unsafe code), but there are many problems like it which don't have any libraries for it yet.
I do have hard problems. I want a language which makes hard problems easy, and impossible problems hard. Rust is definitely _not_ such a language, and it makes me like 5 times less productive, and sucks all joy out of programming.