Если вы используете хеш-таблицу вместо матрицы смежности или списка, вы получите лучшие или одинаковые значения времени выполнения и пространства big-O для всех операций (проверка на ребро O(1), получение всех смежных ребер O(degree) и т. Д.).
Существуют некоторые постоянные коэффициенты, хотя и для времени выполнения, и для пространства (хеш-таблица не так быстра, как поиск по списку или массиву, и занимает приличное количество дополнительного пространства для уменьшения коллизий).