Структуры данных для предоставления графов

Информацию о графах и орграфах можно хранить двумя способами:

1) в виде матрицы примыканий;

2) в виде списка примыканий.

Матрица примыканий обеспечивает быстрый доступ к информации о ребрах графа. Однако, если в графе мало ребер, то эта матрица будет содержать гораздо больше пустых клеток, чем заполненных.

Длина списки примыканий пропорциональна числу ребер в графе, однако, при пользовании списком, время получения информации о ребре увеличивается.

Таким образом, ни один из этих методов не превосходит другой заведомо.