Что лучше, списки смежности или матрицы смежности для задач графа в C ++?

Это зависит от проблемы.

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

• Использует память O (n ^ 2)
• Быстро искать и проверять наличие или отсутствие определенного ребра
  между любыми двумя узлами O (1)
• Медленно перебирать все ребра
• Добавление / удаление узла происходит медленно; сложная операция O (n ^ 2)
• Быстро добавить новое ребро O (1)

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

• Использование памяти больше зависит от количества ребер (и меньше от количества узлов),
  что может сэкономить много памяти, если матрица смежности разреженная.
• Определение наличия или отсутствия определенного ребра между любыми двумя узлами
  происходит немного медленнее, чем с матрицей O (k); где k - количество соседних узлов
• Быстро перебирать все ребра, потому что вы можете получить доступ к любым соседям узла напрямую.
• Добавление / удаление узла происходит быстро; проще, чем матричное представление
• Быстро добавить новое ребро O (1)

Этот ответ предназначен не только для C ++, поскольку все упомянутое касается самих структур данных, независимо от языка. И мой ответ предполагает, что вы знаете базовую структуру списков и матриц смежности.

объем памяти

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

Матрица смежности занимает n ² / 8 байтов (один бит на запись).

Список смежности занимает пространство 8e, где e - количество ребер (32-битный компьютер).

Если мы определим плотность графа как d = e / n ² (количество ребер, деленное на максимальное количество ребер), мы можем найти «точку останова», где список занимает больше памяти, чем матрица:

8e> n ² / 8, когда d> 1/64

Таким образом, с этими числами (все еще 32-битными) точка останова находится на 1/64. Если плотность (e / n ²) больше 1/64, то предпочтительнее использовать матрицу, если вы хотите сэкономить память.

Вы можете прочитать об этом на wikipedia (статья о матрицах смежности) и на многих других сайтах. .

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

Итерация и поиск

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

С другой стороны, матрицы смежности используют больше места для обеспечения постоянного времени поиска. Поскольку существует каждая возможная запись, вы можете проверить наличие края в постоянное время с помощью индексов. Однако поиск соседей занимает O (n), так как вам нужно проверить всех возможных соседей. Очевидный недостаток места в том, что для разреженных графов добавляется много отступов. См. Обсуждение памяти выше для получения дополнительной информации об этом.

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

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

Подскажите пожалуйста, есть ли ошибки.

Это зависит от того, что вы ищете.

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

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

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

Предположим, у нас есть граф с n количеством узлов и m количеством ребер,

Пример графика

Матрица смежности: мы создаем матрицу с n количеством строк и столбцов, поэтому в памяти будет занимать место, пропорциональное n ² . Проверка наличия ребра между двумя узлами с именами u и v займет Θ (1) времени. Например, проверка на (1, 2) - это ребро в коде будет выглядеть следующим образом:

if(matrix[1][2] == 1)

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

Список смежности: мы создаем список, в котором каждый узел также указывает на другой список. В вашем списке будет n элементов, и каждый элемент будет указывать на список, в котором количество элементов равно количеству соседей этого узла (см. Изображение для лучшей визуализации). Таким образом, это займет место в памяти, пропорциональное n + m. Проверка того, является ли (u, v) ребром, займет O (deg (u)) времени, в течение которого deg (u) равно количеству соседей u. Потому что самое большее вам придется перебирать список, на который указывает u. Для идентификации всех ребер потребуется Θ (n + m).

Список смежности примера графа

Вы должны сделать свой выбор в соответствии с вашими потребностями. По репутации я не мог поставить изображение матрицы, извините за это

Если вы изучаете анализ графов на C ++, вероятно, первым делом стоит начать с библиотеки ускоренных графов, которая реализует ряд алгоритмов, включая BFS.

• Документы библиотеки ускоренных графиков

ИЗМЕНИТЬ

Этот предыдущий вопрос о SO, вероятно, поможет:

как сделать- create-ac-boost-unirected-graph-and-traverse-it-in-depth-first-searchc h

Лучше всего ответить на этот вопрос с помощью примеров.

Подумайте, например, о Floyd-Warshall. Мы должны использовать матрицу смежности, иначе алгоритм будет асимптотически медленнее.

Или что, если это плотный граф на 30 000 вершин? Тогда матрица смежности может иметь смысл, поскольку вы будете хранить 1 бит на пару вершин, а не 16 бит на ребро (минимум, который вам понадобится для списка смежности): это 107 МБ, а не 1,7 ГБ.

Но для таких алгоритмов, как DFS, BFS (и тех, которые его используют, например Эдмондса-Карпа), приоритетного поиска (Dijkstra, Prim, A *) и т. Д., Список смежности ничем не хуже матрицы. Что ж, матрица может иметь небольшое ребро, когда граф плотный, но только с незначительным постоянным множителем. (Сколько? Это вопрос экспериментов.)

Чтобы добавить к keyser5053 ответ об использовании памяти.

Для любого ориентированного графа матрица смежности (с 1 битом на ребро) потребляет n^2 * (1) бит памяти.

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

Для неполного графа список смежности потребляет 0 бит памяти, исключая служебные данные списка.

Для списка смежности вы можете использовать следующую формулу, чтобы определить максимальное количество ребер (e), прежде чем матрица смежности станет оптимальной для памяти.

edges = n^2 / s, чтобы определить максимальное количество ребер, где s - размер указателя платформы.

Если ваш график динамически обновляется, вы можете поддерживать эту эффективность со средним числом ребер (на узел) n / s.

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

Для ориентированного графа, где n равно 300, оптимальное количество ребер на узел с использованием списка смежности:

= 300 / 64
= 4

Если мы вставим это в формулу keyser5053, d = e / n^2 (где e - общее количество ребер), мы увидим, что мы находимся ниже точки останова (1 / s):

d = (4 * 300) / (300 * 300)
d < 1/64
aka 0.0133 < 0.0156

Однако 64 бита для указателя может быть излишним. Если вместо этого вы используете 16-битные целые числа в качестве смещения указателя, мы можем уместить до 18 ребер до точки разрыва.

= 300 / 16
= 18

d = ((18 * 300) / (300^2))
d < 1/16
aka 0.06 < 0.0625

Каждый из этих примеров игнорирует накладные расходы самих списков смежности (64*2 для векторных и 64-битных указателей).

В зависимости от реализации матрицы смежности «n» графа должно быть известно раньше для эффективной реализации. Если график слишком динамичный и требует время от времени расширять матрицу, это тоже можно считать недостатком?

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

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

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

Можно представить граф в списке смежности с помощью запроса EdgeExists за амортизированное постоянное время, воспользовавшись преимуществами структур данных Dictionary и HashSet. Идея состоит в том, чтобы хранить вершины в словаре, и для каждой вершины мы сохраняем хэш-набор, ссылающийся на другие вершины, с которыми у нее есть ребра.

Один незначительный компромисс в этой реализации заключается в том, что она будет иметь пространственную сложность O (V + 2E) вместо O (V + E), как в обычном списке смежности, поскольку ребра представлены здесь дважды (потому что каждая вершина имеет свой собственный хэш-набор ребер). Но такие операции, как AddVertex, AddEdge, RemoveEdge, могут быть выполнены с амортизированным временем O (1) с этой реализацией, за исключением RemoveVertex , который будет амортизирован за O (V), как в матрице смежности с поисковым словарем индекса массива. Это означало бы, что кроме простоты реализации, матрица смежности не имеет особых преимуществ. Мы можем сэкономить место на разреженном графе с почти такой же производительностью в этой реализации списка смежности.

Взгляните на реализации ниже в репозитории Github C # для получения подробной информации. Обратите внимание, что для взвешенного графа он использует вложенный словарь вместо комбинации словаря и хеш-набора, чтобы учесть значение веса. Аналогично для ориентированного графа существуют отдельные хеш-наборы для входных и выходных ребер.

Расширенные алгоритмы

Примечание: я считаю, что с помощью ленивого удаления мы можем дополнительно оптимизировать операцию RemoveVertex до амортизации O (1), хотя я не тестировал эту идею. Например, при удалении просто отметьте вершину как удаленную в словаре, а затем лениво очистите потерянные ребра во время других операций.