Представление большого графика в C ++

Question

Могут быть похожие вопросы, но у меня все еще есть некоторые детали, которые я не могу понять. Я пытаюсь представить неориентированный график без весов, а просто 1 для подключенного и 0 для не подключенного. Я пытаюсь представить график (чтение из файла), который имеет 80500 узлов и более 5,5 миллионов ребер. Мне было интересно;

1. Будет ли большое влияние, если я поменяю свою матрицу смежности (ту, которую я сейчас использую) на список смежности? У меня нет проблем с реализацией, просто спрашиваю, стоит ли времени конвертировать его в список?
2. Поскольку я просто храню 1 и 0 , существует ли специальный тип данных, не храните это. Я использую in, и я думаю, что byte тип данных сэкономит много времени.
3. Любая другая структура, кроме матрицы или списка смежности, которая может быть лучше для этой типичной проблемы?

Answer 1

Списки смежности гораздо лучше в пространстве. Потому что тогда вам просто нужно сохранить 5,5 миллиона * 2 числа = 11 000 000 целых чисел. Предполагая, что вы сохраняете короткие целые числа (2 байта), вам нужно 22 000 000 байтов.

Если вы представляете это с помощью матрицы смежности, то вам нужно сохранить 80500 * 80500 = 6 480 250 000 элементов. Даже если вы сохраните их как байты, иметь 22 миллиона байтов намного лучше, чем иметь более 6 миллиардов.

EDIT: Если вы сохраняете eges как два 4-байтовых целых числа, то у вас есть 44 000 000 байтов. Если вы очень эффективно сохраняете матрицу с помощью битовой коррекции, вы можете сохранить 8 элементов в одном байте. Но это означает, что вам все равно нужно иметь 810 031 250 байт. Сейчас разница не такая большая, но все равно в 20 раз больше.

Answer 2

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