Myślę, że twój pierwszy przykład jest trochę niejednoznaczny - węzły jako obiekty i krawędzie jako wskaźniki. Możesz je śledzić, przechowując tylko wskaźnik do jakiegoś węzła głównego, w którym to przypadku dostęp do danego węzła może być nieefektywny (powiedzmy, że chcesz węzła 4 - jeśli obiekt węzła nie jest dostarczony, może być konieczne wyszukanie go) . W takim przypadku stracisz również części wykresu, do których nie można dotrzeć z węzła głównego. Myślę, że tak właśnie jest w przypadku f64 rainbow, który przyjmuje, gdy mówi, że złożoność czasowa dostępu do danego węzła wynosi O (n).
W przeciwnym razie możesz również zachować tablicę (lub tablicę mieszającą) pełną wskaźników do każdego węzła. Umożliwia to O (1) dostęp do danego węzła, ale nieco zwiększa zużycie pamięci. Jeśli n jest liczbą węzłów, a e jest liczbą krawędzi, złożoność przestrzenna tego podejścia wyniosłaby O (n + e).
Złożoność przestrzeni dla podejścia macierzowego byłaby wzdłuż linii O (n ^ 2) (zakładając, że krawędzie są jednokierunkowe). Jeśli wykres jest rzadki, w macierzy będzie dużo pustych komórek. Ale jeśli twój wykres jest w pełni połączony (e = n ^ 2), wypada to korzystnie w porównaniu z pierwszym podejściem. Jak mówi RG, przy takim podejściu możesz mieć mniej błędów pamięci podręcznej, jeśli alokujesz macierz jako jeden fragment pamięci, co może przyspieszyć śledzenie wielu krawędzi wokół wykresu.
Trzecie podejście jest prawdopodobnie najbardziej efektywne pod względem miejsca w większości przypadków - O (e) - ale oznaczałoby, że znalezienie wszystkich krawędzi danego węzła byłoby zadaniem O (e). Nie przychodzi mi do głowy przypadek, w którym byłoby to bardzo przydatne.