Существует три способа хранения графика в памяти:
Я знаю, как писать все три, но я не уверен, что я думал обо всех преимуществах и недостатках каждого из них.
Каковы преимущества и недостатки каждого из этих способов хранения графика в памяти?
Один из способов их анализа - с точки зрения сложности памяти и времени (что зависит от того, как вы хотите получить доступ к графику).
Хранение узлов как объектов с указателями друг на друга
Сохранение матрицы весов ребер
В зависимости от того, какой алгоритм вы используете на графике и сколько узлов есть, вам нужно выбрать подходящее представление.
Еще несколько вещей, которые нужно учитывать:
Матричная модель легче поддается графам со взвешенными ребрами, сохраняя весовые коэффициенты в матрице. Модель объекта/указателя должна была бы хранить вес границ в параллельном массиве, что требует синхронизации с массивом указателей.
Модель объекта/указателя работает лучше с ориентированными графами, чем неориентированные графики, потому что указатели должны поддерживаться парами, которые могут стать несинхронизированными.
Метод объектов и указателей страдает от сложности поиска, как некоторые отметили, но довольно естественны для выполнения таких задач, как построение двоичных деревьев поиска, где есть много дополнительной структуры.
Я лично люблю матрицы смежности, потому что они делают всевозможные проблемы намного проще, используя инструменты из теории алгебраических графов. (К-ю степень матрицы смежности задает, например, количество путей длины k от вершины я до вершины j. Добавьте идентификационную матрицу, прежде чем принимать k-ю степень, чтобы получить число путей длины < = k. Возьмем ранг n-1 минор лапласиана, чтобы получить число остовных деревьев... И так далее.)
Но все говорят, что матрицы смежности - это дорогая память! Они только наполовину правы: вы можете обойти это, используя разреженные матрицы, когда ваш график имеет несколько ребер. Редкие структуры матричных данных выполняют именно работу, просто сохраняя список смежности, но все же имеют полную гамму стандартных матричных операций, предоставляя вам лучшее из обоих миров.
Я думаю, что ваш первый пример немного неоднозначен - узлы как объекты и ребра в качестве указателей. Вы можете отслеживать их, сохраняя только указатель на некоторый корень node, и в этом случае доступ к заданному node может быть неэффективным (например, вы хотите node 4 - если объект node не указан, вам, возможно, придется его искать). В этом случае вы также потеряете части графика, которые недоступны из корня node. Я думаю, что это тот случай, когда радуга радует, когда он говорит, что сложность времени для доступа к данному node равна O (n).
В противном случае вы также можете сохранить массив (или хэш-карту), полный указателей, для каждого node. Это позволяет O (1) получить доступ к данному node, но немного увеличивает объем памяти. Если n - число узлов, а e - число ребер, то пространственная сложность этого подхода будет O (n + e).
Сложность пространства для матричного подхода была бы вдоль линий O (n ^ 2) (предполагая, что ребра являются однонаправленными). Если ваш график разрежен, у вас будет много пустых ячеек в вашей матрице. Но если ваш график полностью связан (e = n ^ 2), это выгодно отличается от первого подхода. Как говорит RG, у вас также может быть меньше промахов в кеше с этим подходом, если вы выделите матрицу как один кусок памяти, что может сделать следующее множество граней вокруг графика быстрее.
Третий подход, пожалуй, наиболее эффективен для большинства случаев - O (e), но сделает поиск всех ребер данной node операцией O (e). Я не могу придумать случай, когда это было бы очень полезно.
Посмотрите сравнительную таблицу на wikipedia. Это дает довольно хорошее представление о том, когда использовать каждое представление графиков.
Хорошо, поэтому, если ребра не имеют весов, матрица может быть двоичным массивом, и использование двоичных операторов может сделать вещи действительно, очень быстрыми в этом случае.
Если граф разрежен, метод object/pointer кажется намного более эффективным. Удержание объекта/указателей в структуре данных, специально предназначенное для их коаксиализации в один кусок памяти, также может быть хорошим планом или любым другим способом заставить их оставаться вместе.
Список смежности - просто список подключенных узлов - по-видимому, наиболее эффективен с точки зрения памяти, но, вероятно, и самый медленный.
Реверсирование ориентированного графа легко с матричным представлением и легко с помощью списка смежности, но не так велико с представлением объекта/указателя.
Существует еще один вариант: узлы как объекты, ребра как объекты, причем каждое ребро одновременно в двух двусвязных списках: список всех ребер, выходящих из одного и того же node, и список всех ребер перейдя в тот же node.
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 указателя на node и 6 указателей на край), но вы получаете
Структура также может представлять собой довольно общий график: ориентированный мультиграф с циклами (т.е. вы можете иметь несколько разных ребер между теми же двумя узлами, включая несколько различных циклов - ребер, идущих от x до x).