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

Question

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

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

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

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

Answer 1

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

Сохранения узлов как объекты с указателями на один другой

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

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

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

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

Answer 2

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

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

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

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

Answer 3

Хорошо, поэтому, если ребра не имеют весов, матрица может быть двоичным массивом, и использование двоичных операторов может сделать вещи действительно, действительно быстрыми в этом случае.

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

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 (град (п) удаление узла) (данный указатель)
• O (град (п)) обнаружение соседей узла

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

Answer 7

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