Przy gęstych grafach, zazwyczaj najlepszą implementacją jest macierz (więc std::array
, jak się trzymamy tylko biblioteki standardowej). Przy drzewach (lub ogólnie, grafach rzadkich) już coś dynamicznego: robisz sobie strukturę z id węzła (typowo std::uint_fast_??_t
), wektorem wskaźników (najlepiej std::shared_pointer
lub std::unique_pointer
, w zależności od potrzeb) na potomków (lub par [wskaźnik, waga], jeśli tego potrzebujesz) i zawartością, którą chcesz w nich trzymać.
Jak od razu wiesz, że będziesz potrzebował coś więcej, to dorzuć coś więcej: na przykład jak chcesz iść „pod górę”, od liści do korzenia, to trzymaj też i wskaźnik na rodzica (czy wektor wskaźników na rodziców, jeśli to potrzebne, itd.)
Wielkiej filozofii w tym nie ma, jedyne co jest ciężkie, to efektywne zarządzanie pamięcią, żeby nie mieć miliona alokacji małych obiektów. Ale najpierw opanuj „naiwną” metodę, zanim będziesz w memory pool
e i inne cuda. No chyba że o to właśnie pytałeś — ale to jest pytanie wymagające poznania właściwie całej specyfikacji, by móc coś sensownie doradzić.