Реализация библиотеки графов

Какой из двух эффективнее и быстрее?

Это зависит от вашего использования и типов графиков, которые вы хотите сохранить.

Пусть n будет количеством узлов, а m будет количеством ребер. Если вы хотите узнать, соединены ли два узла u и v (и вес ребра), матрица смежности позволяет определить это за постоянное время (в O-notation, O(1)), просто получив запись A[u,v]. Со списком смежности вам придется просматривать каждую запись в списке u или списке v — в худшем случае может быть n записей. Таким образом, поиск края для списка смежности выполняется за O (n).

Основным недостатком матрицы смежности является требуемая память. Всего вам нужно хранить n^2 записей. В списке смежности вам нужно хранить только ребра, которые действительно существуют (m записей, предполагая ориентированный граф). Поэтому, если ваш граф разреженный, списки смежности явно занимают гораздо меньше памяти.

Мой вывод будет таким: используйте матрицу смежности, если ваша основная операция — получение веса ребра для двух конкретных узлов; при условии, что ваши графики достаточно малы, чтобы в памяти помещалось n^2 записей. В противном случае используйте список смежности.

Лично я бы выбрал подход со связанными списками, предполагая, что это часто будет разреженный граф (т.е. большинство ячеек массива - пустая трата места).

Пошел в Википедию, чтобы прочитать списки смежности (давно я не использовал графики), и у него есть хороший раздел о компромиссах между двумя подходами. В конечном счете, как и в случае со многими вариантами «или/или», все сводится к «это зависит» в зависимости от того, каковы вероятные варианты использования вашей библиотеки.

Прочитав вики-статью, я думаю, что еще одним аргументом в пользу использования списков будет прикрепление данных к каждому направленному сегменту (или даже разным весам, подумайте о расстоянии ходьбы/велосипеда/автомобиля между двумя точками и т. д.).