Что лучше: списки смежности или матрицы смежности для задач с графами в C++?
Что лучше, списки смежности или матрица смежности, для задач с графами в C++? Каковы преимущества и недостатки каждого?
11 ответов
Это зависит от проблемы.
- Использует O(n^2) памяти
- Это быстро искать и проверять наличие или отсутствие определенного края
между любыми двумя узлами O(1) - Это медленно, чтобы перебрать все края
- Медленное добавление / удаление узла - сложная операция O(n^2)
- Это быстро, чтобы добавить новое ребро O(1)
- Используйте память в ожидании на количество ребер (не количество узлов),
Что может сэкономить много памяти, если матрица смежности является разреженной - Нахождение наличия или отсутствия определенного ребра между любыми двумя узлами
Немного медленнее, чем с матрицей O(k), где k число соседних узлов - Быстро перебирать все ребра
Потому что вы можете получить доступ к любому узлу соседей напрямую - Быстро добавить / удалить узел проще, чем матричное представление
- Это быстро, чтобы добавить новое ребро O(1)
Этот ответ не только для C++, так как все упомянутое касается самих структур данных, независимо от языка. И мой ответ предполагает, что вы знаете основную структуру списков смежности и матриц.
объем памяти
Если память является вашей основной задачей, вы можете следовать этой формуле для простого графика, который допускает циклы:
Матрица смежности занимает n /8/8-байтовое пространство (один бит на запись).
Список смежности занимает пространство 8e, где e - число ребер (32-битный компьютер).
Если мы определим плотность графика как d = e / n 2 (число ребер, деленное на максимальное число ребер), мы сможем найти "точку останова", когда список занимает больше памяти, чем матрица:
8e> n 2/8 при d > 1/64
Таким образом, с этими числами (все еще 32-битными) точка останова достигает 1/64. Если плотность (e / n 2) больше 1/64, тогда матрица предпочтительнее, если вы хотите сэкономить память.
Вы можете прочитать об этом в Википедии (статья о матрицах смежности) и на многих других сайтах.
Примечание: можно повысить эффективность использования пространства матрицы смежности, используя хеш-таблицу, где ключи - это пары вершин (только ненаправленные).
Итерация и поиск
Списки смежности - это компактный способ представления только существующих ребер. Однако это происходит за счет, возможно, медленного поиска определенных ребер. Поскольку каждый список имеет длину, равную степени вершины, время поиска наихудшего случая проверки определенного ребра может стать O(n), если список неупорядочен. Однако поиск соседей вершины становится тривиальным, и для разреженного или небольшого графа стоимость итерации по спискам смежности может быть незначительной.
С другой стороны, матрицы смежности занимают больше места, чтобы обеспечить постоянное время поиска. Поскольку существует любая возможная запись, вы можете проверить наличие ребра в постоянном времени, используя индексы. Однако поиск соседей занимает O(n), так как вам нужно проверить всех возможных соседей. Очевидный недостаток пространства заключается в том, что для разреженных графов добавлено много отступов. См. Обсуждение памяти выше для получения дополнительной информации об этом.
Если вы все еще не знаете, что использовать: в большинстве реальных проблем создаются разреженные и / или большие графы, которые лучше подходят для представления списка смежности. Их может показаться сложнее реализовать, но я уверяю вас, что это не так, и когда вы пишете BFS или DFS и хотите выбрать всех соседей узла, они находятся на расстоянии одной строки кода. Тем не менее, обратите внимание, что я не продвигаю списки смежности в целом.
Хорошо, я скомпилировал сложности времени и пространства основных операций над графами.
Изображение ниже должно быть само за себя.
Обратите внимание на то, что матрица смежности предпочтительнее, когда мы ожидаем, что график будет плотным, и как список смежности предпочтительнее, когда мы ожидаем, что граф будет разреженным.
Я сделал несколько предположений. Спросите меня, если сложность (время или пространство) нуждается в разъяснении. (Например, для разреженного графа я взял En как небольшую константу, так как предполагал, что добавление новой вершины добавит только несколько ребер, потому что мы ожидаем, что граф останется разреженным даже после добавления этого вершина).
Пожалуйста, скажите мне, если есть какие-либо ошибки.
Это зависит от того, что вы ищете.
С помощью матриц смежности вы можете быстро ответить на вопросы о том, принадлежит ли конкретное ребро между двумя вершинами графа, и вы также можете быстро вставлять и удалять ребра. Недостатком является то, что вы должны использовать чрезмерное пространство, особенно для графов со многими вершинами, что очень неэффективно, особенно если ваш граф разрежен.
С другой стороны, со списками смежности сложнее проверить, находится ли заданное ребро в графе, потому что вам нужно искать в соответствующем списке, чтобы найти ребро, но они более компактны.
Однако, как правило, списки смежности являются правильной структурой данных для большинства приложений графов.
Предположим, у нас есть граф, который имеет n количество узлов и m количество ребер,
Пример графика
Матрица смежности : мы создаем матрицу, которая имеет n строк и столбцов, поэтому в памяти будет занимать пространство, пропорциональное n 2. Проверка того, что два узла с именами u и v имеют ребро между ними, займет Θ(1) времени. Например, проверка для (1, 2) ребра в коде будет выглядеть следующим образом:
if(matrix[1][2] == 1)
Если вы хотите идентифицировать все ребра, вам нужно перебрать матрицу, для этого потребуется два вложенных цикла и потребуется Θ (n 2). (Вы можете просто использовать верхнюю треугольную часть матрицы, чтобы определить все ребра, но это будет снова Θ (n 2))
Список смежности: мы создаем список, который каждый узел также указывает на другой список. Ваш список будет иметь n элементов, и каждый элемент будет указывать на список, который имеет количество элементов, равное количеству соседей этого узла (посмотрите изображение для лучшей визуализации). Таким образом, он займет место в памяти, пропорциональное n + m. Проверка того, является ли (u, v) ребром, потребует O(deg(u)) времени, в течение которого deg (u) равно числу соседей u. Потому что самое большее, вы должны перебирать список, на который указывает u. Определение всех ребер займет Θ(n+m).
Список смежности примера графа
Вы должны сделать свой выбор в соответствии с вашими потребностями. Из-за своей репутации я не могу поставить изображение матрицы, извините за это
Если вы смотрите на анализ графов в C++, вероятно, первым делом стоит начать с библиотеки графов форсирования, которая реализует ряд алгоритмов, включая BFS.
РЕДАКТИРОВАТЬ
Этот предыдущий вопрос о SO, вероятно, поможет:
как создать переменный контур и направить его в нужную глубину
На это лучше всего ответить примерами.
Подумайте о Флойд-Варшалле, например. Мы должны использовать матрицу смежности, иначе алгоритм будет асимптотически медленнее.
Или что, если это плотный граф на 30000 вершин? Тогда может иметь смысл матрица смежности, поскольку вы будете хранить 1 бит на пару вершин, а не 16 бит на ребро (минимум, который вам понадобится для списка смежности): это 107 МБ, а не 1,7 ГБ.
Но для таких алгоритмов, как DFS, BFS (и тех, которые его используют, как Edmonds-Karp), поиск по приоритету (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-битных указателей).
Если вы используете хеш-таблицу вместо матрицы или списка смежности, вы получите лучшие или одинаковые значения времени выполнения и пространства big-O для всех операций (проверка на ребро O(1), получая все смежные края O(degree), так далее.).
Тем не менее, есть некоторые постоянные накладные расходы, как для времени выполнения, так и для пространства (хеш-таблица не так быстра, как поиск по списку или массиву, и занимает приличное количество дополнительного пространства для уменьшения коллизий).
В зависимости от реализации матрицы смежности 'n' графа должно быть известно ранее для эффективной реализации. Если график слишком динамичен и время от времени требует расширения матрицы, то это также можно считать недостатком?
Просто коснусь вопроса о преодолении компромисса с обычным представлением списка смежности, поскольку другие ответы охватывают другие аспекты.
Можно представить граф в списке смежности с помощью запроса EdgeExists за амортизированное постоянное время, используя преимущества структур данных Dictionary и HashSet. Идея состоит в том, чтобы хранить вершины в словаре, и для каждой вершины мы сохраняем хэш-набор, ссылающийся на другие вершины, с которыми у него есть ребра.
Одним небольшим компромиссом в этой реализации является то, что он будет иметь пространственную сложность O(V + 2E) вместо O(V + E), как в обычном списке смежности, поскольку ребра представлены здесь дважды (поскольку каждая вершина имеет свой собственный хэш-набор края). Но такие операции, как AddVertex, AddEdge, RemoveEdge, могут выполняться в амортизированном времени O(1) с помощью этой реализации, за исключением RemoveVertex, который принимает O(V) как матрицу смежности. Это будет означать, что, кроме матрицы смежности простоты реализации, не имеет никаких особых преимуществ. Мы можем сэкономить место на разреженном графе с почти такой же производительностью в этой реализации списка смежности.
Посмотрите на реализации ниже в Github C# репозиторий для деталей. Обратите внимание, что для взвешенного графика он использует вложенный словарь вместо словарной комбинации, чтобы приспособить значение веса. Точно так же для ориентированного графа есть отдельные хэш-множества для входных и выходных ребер.
Примечание: я полагаю, что с помощью отложенного удаления мы можем дополнительно оптимизировать операцию RemoveVertex, чтобы амортизировать O(1), даже если я не проверял эту идею. Например, после удаления просто пометьте вершину как удаленную в словаре, а затем лениво очистите потерянные ребра во время других операций.