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

Question

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

Answer 1

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

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

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

Список смежных

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

Answer 2

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

Память

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

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

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

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

8e> n ² / 8 при d> 1/64

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

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

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

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

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

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

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

Answer 3

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

Пожалуйста, сообщите мне, если есть ошибки.

Answer 4

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

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

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

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

Answer 5

Предположим, у нас есть график, который имеет 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).

Список смежных примеров графика

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

Answer 6

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

• Документация библиотеки графиков повышения

EDIT

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

как к созданию-А-С-импульс-неориентированного-граф-и-траверс-он-углубленные-первых, Searc ч

Answer 7

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

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

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

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

Answer 8

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

Answer 9

Добавить к 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-битных указателей).

Answer 10

Просто коснусь вопроса о преодолении компромисса с обычным представлением списка смежности, поскольку другие ответы охватывают другие аспекты.

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

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

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

Продвинутые алгоритмы

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