Списки смежности обычно подходят лучше: занимают O(V+E) и позволяют перебирать существующих соседей. Матрица требует O(V²), даже когда большинство рёбер отсутствует.
Как выбрать структуру хранения разреженного графа
Списки смежности обычно подходят лучше: занимают O(V+E) и позволяют перебирать существующих соседей. Матрица требует O(V²), даже когда большинство рёбер отсутствует.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Граф имеет V вершин и E рёбер, причём E намного меньше V². Требуется часто обходить соседей. Что выбрать: матрицу смежности или списки?
Ответ
Списки смежности обычно подходят лучше: занимают O(V+E) и позволяют перебирать существующих соседей. Матрица требует O(V²), даже когда большинство рёбер отсутствует.
Матрица удобна для постоянной проверки наличия ребра и плотных графов. В списках для такой проверки может понадобиться перебор соседей либо дополнительное множество. Для направленного графа храните нужные направления; для взвешенного — пары сосед/вес. Выбор определяется операциями, а не универсальным предпочтением одной структуры.