Эффективный способ сохранить график (двумерный массив)

Question

Кто-нибудь знает более эффективный способ хранения графической информации (т.е. более эффективный, чем сохранение ее в виде двумерного массива), с точки зрения объема памяти или времени сборки?

Вы можете предположить, что его значения ограничены 0-255.

Thanx!

Answer 1

Вот несколько стандартных способов представления (направленного) графа:

Для графа из 4 узлов:

Матрица смежности:

  0  1  2  3 
0 F  F  T  F
1 T  F  T  T
2 T  F  F  F
3 F  F  F  F

Edge List:

((0, 2), (1, 0), (1, 2), (1, 3), (2, 0))

Список смежностей:

(
 (0, (2,)     ), 
 (1, (0, 2, 3)), 
 (2, (0,)     ),
 (4, (,)      ),
)

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

Edge List прост, но медленнее, чем матрица смежности, и эффективен для памяти, если у вас есть разреженный граф(2 * M, где M - количество ребер).

Список смежности немного сложнее (так как вам нужен массив переменного размера), но более эффективен по памяти, чем список краев, если у вас большое количество ребер (2 * N + M, где N - числовершин, M число ребер)

Матрица смежности занимает (N N b) место.Edge List занимает ((2 + b) * N) памяти.А список смежности занимает (2 * N + M * (1 + b)) памяти.

Если вы знаете, что у вас всегда меньше 256 вершин (8 бит), а веса меньше 256 (8 бит), тогда Матрица смежности занимает (N * N * 8) пробел.Edge List занимает (24 * N) памяти.И список смежности занимает (16 * N + M * 16) памяти.

Answer 2

Если вам не нужно изменять график после создания, взгляните на формат сжатого разреженного ряда (CSR).Описание из BGL :

Формат CSR хранит вершины и ребра в отдельных массивах, причем индексы в этих массивах соответствуют идентификатору для вершины или ребра, соответственно.Массив ребер отсортирован по источнику каждого ребра, но содержит только цели для ребер.Массив вершин хранит смещения в массиве ребер, обеспечивая смещение первого ребра, исходящего из каждой вершины.Итерация по ребрам для i-й вершины в графе достигается путем посещения edge_array [vertex_array [i]], edge_array [vertex_array [i] +1], ..., edge_array [vertex_array [i + 1]].Этот формат минимизирует использование памяти до O (n + m), где n и m - количество вершин и ребер соответственно.Константы, умноженные на n и m, основаны на размере целых чисел, необходимых для представления индексов в массивах ребер и вершин соответственно (...)

Здесь представляет собойхорошее объяснение смещенных массивов :

       Offset              Neighbours
   1      1    -------------->  2
   2      3    ------------     3
   3      5    ----------  |->  1
   4      9    --------  |      3
   5     10    ------  | |--->  1
   6     12    ----  | |        2
   7     14    --  | | |        4
                 | | | |        6
                 | | |  ----->  3
                 | |  ------->  6
                 | |            7
                 |  --------->  5
                 |              7
                  ----------->  5
                                6

Эффективная вставка ребер

Возможность вставки ребер после создания может быть достигнута путемNeighbours массив в "связанный список".Смещение указывает на первого соседа, и каждый сосед содержит поле Next.Это указывает на следующее ребро.

Из того же источника:

        Offset                 Node  Next
   1      1    -------------->  2    2
   2      3    ------------     3   -1
   3      5    ----------  |->  1    4
   4      9    --------  |      3   -1
   5     10    ------  | |--->  1    6
   6     12    ----  | |        2    7
   7     14    --  | | |        4    8
                 | | | |        6    9
                 | | |  ----->  3   -1
                 | |  ------->  6   11
                 | |            7   -1
                 |  --------->  5   13
                 |              7   -1
                  ----------->  5   15
                                6   -1

Answer 3

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

Answer 4

Вот список представлений графа, который я нашел здесь полезным:

Структуры данных графа