История изменений
Исправление monk, (текущая версия) :
На указателях графы делать – полная и тотальная тупость, хотя бы из-за накладных расходов по памяти. У тебя каждый указатель по 8 байт добавляет. Нахрен так вообще жить?
Так массив дороже. Вот возьмём простой граф-кольцо на пару тысяч точек. На указателях у меня будет N28 байт. На массиве будет N*N (пусть бит). Уже для 128 точек даже битовый массивы вырастает до того же размера, как и на структура на указателях. Плюс все операции на нём O(N).
Если же известно, что элементов меньше 256, то «указателем» может быть номер элемента массива узлов. И тогда массив становится неэффективен уже на 16 элементах.
Исходная версия monk, :
На указателях графы делать – полная и тотальная тупость, хотя бы из-за накладных расходов по памяти. У тебя каждый указатель по 8 байт добавляет. Нахрен так вообще жить?
Так массив дороже. Вот возьмём простой граф-кольцо на пару тысяч точек. На указателях у меня будет N28 байт. На массиве будет N*N (пусть бит). Уже для 128 точек даже битовый массивы вырастает до того же размера, как и на структура на указателях. Плюс все операции на нём O(N).
Если же известно, что элементов меньше 256, от «указателем» может быть номер элемента массива узлов. И тогда массив становится неэффективен уже на 16 элементах.