Три способа сохранить график в памяти, преимущества и недостатки

Есть три способа сохранить график в памяти:

1. Узлы как объекты и ребра как указатели
2. Матрица, содержащая все веса ребер между нумерованным узлом x и узлом y
3. Список ребер между пронумерованными узлами

Я знаю, как написать все три, но не уверен, что уловил все преимущества и недостатки каждого из них.

Каковы преимущества и недостатки каждого из этих способов хранения графика в памяти?

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

Хранение узлов как объектов с указателями друг на друга

• Сложность памяти для этого подхода составляет O (n), потому что у вас столько объектов, сколько у вас узлов. Требуемое количество указателей (на узлы) составляет до O (n ^ 2), поскольку каждый объект узла может содержать указатели до n узлов.
• Сложность по времени для этой структуры данных составляет O (n) для доступа к любому заданному узлу.

Сохранение матрицы весов ребер

• Это будет сложность памяти O (n ^ 2) для матрицы.
• Преимущество этой структуры данных состоит в том, что временная сложность доступа к любому заданному узлу составляет O (1).

В зависимости от того, какой алгоритм вы запускаете на графе и сколько узлов, вам нужно будет выбрать подходящее представление.

Еще пара вещей, которые следует учитывать:

1. Матричная модель легче поддается графам со взвешенными рёбрами, сохраняя веса в матрице. Модель объект / указатель должна будет хранить веса ребер в параллельном массиве, что требует синхронизации с массивом указателей.

2. Модель объект / указатель лучше работает с ориентированными графами, чем с неориентированными графами, потому что указатели должны поддерживаться парами, которые могут стать несинхронизированными.

Как отмечают некоторые, метод объектов и указателей страдает от сложности поиска, но вполне естественен для таких вещей, как построение двоичных деревьев поиска, где есть много дополнительной структуры.

Лично мне нравятся матрицы смежности, потому что они значительно упрощают все виды задач, используя инструменты из теории алгебраических графов. (Например, k-я степень матрицы смежности дает количество путей длины k от вершины i до вершины j. Добавьте единичную матрицу, прежде чем брать k-ю степень, чтобы получить количество путей длиной <= k. Возьмите ранг n-1 минор лапласиана, чтобы получить количество остовных деревьев ... И так далее.)

Но все говорят, что матрицы смежности требуют больших затрат памяти! Они правы только наполовину: вы можете обойти это, используя разреженные матрицы, когда у вашего графа мало ребер. Структуры данных с разреженными матрицами выполняют ту же работу, что и просто поддерживают список смежности, но при этом имеют полный набор стандартных матричных операций, предоставляя вам лучшее из обоих миров.

Я думаю, что ваш первый пример немного неоднозначен - узлы как объекты и ребра как указатели. Вы можете отслеживать их, сохраняя только указатель на некоторый корневой узел, и в этом случае доступ к данному узлу может быть неэффективным (скажем, вам нужен узел 4 - если объект узла не предоставлен, вам, возможно, придется его искать) . В этом случае вы также потеряете части графа, которые недоступны из корневого узла. Я думаю, что это тот случай, когда радуга f64 предполагает, когда он говорит, что временная сложность для доступа к данному узлу составляет O (n).

В противном случае вы также можете сохранить массив (или хэш-карту), полный указателей на каждый узел. Это позволяет O (1) доступ к данному узлу, но немного увеличивает использование памяти. Если n - количество узлов, а e - количество ребер, пространственная сложность этого подхода будет O (n + e).

Сложность пространства для матричного подхода будет примерно равна O (n ^ 2) (при условии, что ребра однонаправлены). Если ваш график разреженный, в вашей матрице будет много пустых ячеек. Но если ваш график полностью связан (e = n ^ 2), это выгодно отличается от первого подхода. Как говорит RG, при таком подходе у вас может быть меньше промахов в кэше, если вы выделяете матрицу как один фрагмент памяти, что может ускорить отслеживание множества ребер вокруг графа.

Третий подход, вероятно, наиболее эффективен по пространству для большинства случаев - O (e) - но сделает поиск всех ребер данного узла задачей O (e). Я не могу придумать случая, когда это было бы очень полезно.

Взгляните на сравнительную таблицу в Википедии. Это дает довольно хорошее понимание того, когда использовать каждое представление графиков.

Есть еще один вариант: узлы как объекты, ребра как объекты, причем каждое ребро одновременно находится в двух двусвязных списках: список всех ребер, исходящих из одного узла, и список всех ребер, входящих в один узел .

struct Node {
    ... node payload ...
    Edge *first_in;    // All incoming edges
    Edge *first_out;   // All outgoing edges
};

struct Edge {
    ... edge payload ...
    Node *from, *to;
    Edge *prev_in_from, *next_in_from; // dlist of same "from"
    Edge *prev_in_to, *next_in_to;     // dlist of same "to"
};

Накладные расходы на память велики (2 указателя на узел и 6 указателей на край), но вы получаете

• O (1) вставка узла
• O (1) вставка ребер (с учетом указателей на узлы "от" и "к")
• O (1) удаление края (с учетом указателя)
• O (deg (n)) удаление узла (с учетом указателя)
• O (deg (n)) поиск соседей узла

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

Более подробное объяснение этого подхода доступно здесь .

Итак, если у ребер нет весов, матрица может быть двоичным массивом, и в этом случае использование двоичных операторов может заставить все идти очень, очень быстро.

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

Список смежности - просто список подключенных узлов - кажется наиболее эффективным с точки зрения памяти, но, вероятно, и самым медленным.

Обратить ориентированный граф легко с помощью матричного представления и легко с помощью списка смежности, но не так хорошо с представлением объекта / указателя.