Мне было интересно быстро написать реализацию графика в С++. Мне нужна структура данных, чтобы легко манипулировать и использовать алгоритмы графа (такие как BFS, DFS, Kruskal, Dijkstra...). Мне нужна эта реализация для олимпиады по алгоритмам, поэтому проще написать структуру данных.
Можете ли вы предложить такие DS (основные структуры или классы и то, что будет в них). Я знаю, что главные возможности имеют список Adjacency и Adjacency, но я имею в виду более подробный код.
Например, я подумал об этом DS в прошлый раз, когда мне пришлось реализовать график для DFS:
struct Edge {
int start;
int end;
struct Edge* nextEdge;
}
а затем использовал массив размером n, содержащий в своем i-м месте список границ (struct Edge), представляющий ребра, начиная с i'th node.
но при попытке DFS на этом графике мне пришлось написать 50-строчный код с примерно 10 циклами.
Какие "хорошие" реализации существуют?