В общем случае хорошим подходом является сохранение списка всех ребер.Это занимает O(E) пространство: мы храним две конечные точки на ребро.Чтобы сохранить его на диске, этого будет достаточно.
Для работы с таким списком он обычно хранится в памяти как V списки смежности, по одному на каждую вершину.Это дублирует каждое ребро (u->v и v->u), если график не является ненаправленным.Тем не менее, обычной операцией для алгоритмов графа является прохождение всех ребер из заданной вершины.Сохраняя список смежности для каждой вершины, мы получаем это в O(number of neighbors), что является наилучшим из возможных.
Матрица смежности занимает O(V^2) пробел, что может быть хорошо для плотных графов, но хужечем O(E) в общем случае.
Матрица инцидентов занимает O(VE) пробел и неэффективна, если ваш граф не является каким-то особенным для этого.
Самые быстрые реализацииАлгоритм Дейкстры занимает O(E log V) времени, поэтому O(E) памяти обычно в порядке.