Я готовлюсь к интервью по кодированию и освежаю свои мысли на графиках. Мне было интересно следующее: во всех местах, которые я видел, предполагается, что списки смежности более эффективны по памяти, чем матрицы смежности для больших разреженных графов, и поэтому должны быть предпочтительными в этом случае. Кроме того, вычисление количества исходящих ребер из узла требует O (N) в матрице, в то время как это O (1) в списке, а также которые являются соседними узлами в O (num смежных узлах) для списка вместо O (N) для матрицы.
К таким местам относится книга Кормена и др. Или StackOverFlow: Размер графика с использованием списка смежности в сравнении с матрицей смежности? или Википедия.
Однако, при использовании разреженного матричного представления, как в представлении «Сжатое хранилище строк», требование к памяти просто в O (число ненулевых элементов) = O (число ребер), что аналогично использованию списков. Число исходящих ребер из узла равно O (1) (оно напрямую сохраняется в CRS), а соседние узлы могут быть перечислены в O (количество соседних узлов).
Почему это не обсуждается? Должен ли я считать, что CSR является своего рода представлением списка смежности графа, представленного матрицей? Или аргумент о том, что матрицы требуют много памяти, потому что они не учитывают разреженные представления матриц?
Спасибо!