Что лучше, списки смежности или матрица смежности для задач графа в С++? Каковы преимущества и недостатки каждого?
Что лучше, списки смежности или матрицы смежности для задач графа в С++?
Ответ 1
Это зависит от проблемы.
- Использует O (n ^ 2) памяти
- Это быстро искать и проверять наличие или отсутствие определенного края
между любыми двумя узлами O (1) - Это медленно, чтобы перебрать все края
- Медленное добавление/удаление узла - сложная операция O (n ^ 2)
- Это быстро, чтобы добавить новое ребро O (1)
- Используйте память в ожидании на количество ребер (не количество узлов),
Что может сэкономить много памяти, если матрица смежности является разреженной - Нахождение наличия или отсутствия определенного ребра между любыми двумя узлами
Немного медленнее, чем с матрицей O (k), где k число соседних узлов - Быстро перебирать все ребра
Потому что вы можете получить доступ к любому узлу соседей напрямую - Быстро добавить/удалить узел проще, чем матричное представление
- Это быстро, чтобы добавить новое ребро O (1)
Ответ 2
Этот ответ предназначен не только для С++, поскольку все упомянутое касается самих структур данных, независимо от языка. И, мой ответ предполагает, что вы знаете основную структуру списков смежности и матриц.
Память
Если ваша основная проблема связана с памятью, вы можете следовать этой формуле для простого графика, который допускает циклы:
Матрица смежности занимает n 2/8 байтов (один бит на запись).
Список смежности занимает 8e-пространство, где e - количество ребер (32-битный компьютер).
Если мы определяем плотность графа как d = e/n 2 (количество ребер, деленное на максимальное количество ребер), мы можем найти "точку останова", в которой перебирается список больше памяти, чем матрица:
8e > n 2/8, когда d > 1/64
Таким образом, с этими числами (по-прежнему 32-битные) точка останова находится на уровне 1/64. Если плотность (e/n 2) больше 1/64, тогда матрица предпочтительнее, если вы хотите сохранить память.
Вы можете прочитать об этом в wikipedia (статья о смежных матрицах) и множестве других сайтов.
Боковое примечание. Можно улучшить пространственную эффективность матрицы смежности, используя хеш-таблицу, в которой ключи представляют собой пары вершин (только ненаправленные).
Итерация и поиск
Списки аджакции - это компактный способ представления только существующих ребер. Однако это происходит за счет, возможно, медленного поиска конкретных ребер. Поскольку каждый список имеет длину вершины, наихудшее время поиска для проверки для конкретного ребра может стать O (n), если список неупорядочен. Однако поиск соседей вершины становится тривиальным, а для разреженного или небольшого графика стоимость повторения через списки смежности может быть незначительной.
Матрицы смежности, с другой стороны, используют больше пространства, чтобы обеспечить постоянное время поиска. Поскольку существует всякая возможная запись, вы можете проверить наличие ребра в постоянное время с помощью индексов. Однако поиск соседей принимает O (n), так как вам нужно проверить всех возможных соседей. Очевидным недостатком пространства является то, что для разреженных графиков добавляется множество дополнений. Дополнительную информацию об этом см. В обсуждении памяти выше.
Если вы все еще не уверены в том, что использовать: большинство проблем реального мира создают разреженные и/или большие графики, которые лучше подходят для представлений списка смежности. Они могут показаться сложнее реализовать, но я уверяю вас, что это не так, и когда вы пишете BFS или DFS и хотите получить все соседи из node, они всего лишь одна строка кода. Однако обратите внимание, что я вообще не продвигаю списки смежности.
Ответ 3
Хорошо, я собрал сложности времени и пространства основных операций на графиках.
Изображение ниже должно быть понятным.
Обратите внимание, что матрица смежности предпочтительнее, когда мы ожидаем, что график будет плотным, и как предпочтительный список предпочтений, когда мы ожидаем, что график будет разреженным.
Я сделал некоторые предположения. Спросите меня, требуется ли сложность (время или космос). (Например, для разреженного графика я принял En как небольшую константу, так как предположил, что добавление новой вершины добавит только несколько ребер, потому что мы ожидаем, что график останется разреженным даже после добавления вершина.)
Скажите, пожалуйста, если есть какие-либо ошибки.
Ответ 4
Это зависит от того, что вы ищете.
С матрицами смежности вы можете быстро ответить на вопросы относительно того, относится ли конкретное ребро между двумя вершинами к графу, а также вы можете быстро вставлять и удалять ребра. Недостатком является то, что вам нужно использовать чрезмерное пространство, особенно для графиков со многими вершинами, что очень неэффективно, особенно если ваш график разрежен.
С другой стороны, с списками смежности сложнее проверить, находится ли данное ребро в графике, потому что вам нужно найти соответствующий список, чтобы найти край, но они больше эффективное пространство.
Как правило, списки смежности являются правильной структурой данных для большинства приложений графиков.
Ответ 5
Если вы посмотрите на анализ графа в С++, вероятно, первым местом для начала станет библиотека ускорителей, которая реализует ряд алгоритмы, включая BFS.
ИЗМЕНИТЬ
Этот предыдущий вопрос о SO, вероятно, поможет:
how-to-create-a-c-boost-undirected-graph-and-traverse-it-in-depth-first-searc h
Ответ 6
Предположим, у нас есть граф, который имеет 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).
Список смежности примера графа
Вы должны сделать свой выбор в соответствии с вашими потребностями. Из-за своей репутации я не могу поставить изображение матрицы, извините за это
Ответ 7
На это лучше всего ответить на примеры.
Например, подумайте о Флойде-Варшалле. Мы должны использовать матрицу смежности, или алгоритм будет асимптотически медленнее.
Или что, если это плотный граф на 30 000 вершин? Тогда матрица смежности может иметь смысл, так как вы будете хранить 1 бит на пару вершин, а не 16 бит на край (минимум, который вам нужен для списка смежности): это 107 МБ, а не 1,7 ГБ.
Но для таких алгоритмов, как DFS, BFS (и те, которые используют его, например, Edmonds-Karp), поиск по приоритету (Dijkstra, Prim, A *) и т.д., Список смежности не хуже матрицы. Ну, матрица может иметь небольшое краю, когда граф плотный, но только по незаметному постоянному фактору. (Сколько? Это вопрос экспериментов.)
Ответ 8
Чтобы добавить к keyser5053 ответ об использовании памяти.
Для любого направленного графа матрица смежности (с 1 бит на край) потребляет n^2 * (1) бит памяти.
Для полного графика список смежности (с 64-разрядными указателями) потребляет n * (n * 64) бит памяти, исключая служебные данные списка.
Для неполного графика список смежности потребляет 0 бит памяти, исключая служебные данные списка.
Для списка смежности вы можете использовать следующую формулу, чтобы определить максимальное количество ребер (e), прежде чем матрица смежности будет оптимальной для памяти.
edges = n^2 / s, чтобы определить максимальное количество ребер, где s - размер указателя платформы.
Если вы динамически обновляете график, вы можете поддерживать эту эффективность со средним количеством граней (за node) n / s.
Некоторые примеры (с 64-разрядными указателями).
Для ориентированного графа, где n равно 300, оптимальное количество ребер на node с использованием списка смежности:
= 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-битных указателей).
Ответ 9
В зависимости от реализации Матрицы Adjacency матрица "n" графа должна быть известна ранее для эффективной реализации. Если график слишком динамичен и требует разложения матрицы время от времени, что также можно считать недостатком?
Ответ 10
Если вы используете хеш-таблицу вместо матрицы смежности или списка, вы получите лучшее или такое же большое время выполнения и пространство для всех операций (проверка для ребра O(1), получение всех смежных ребер O(degree) и т.д.).
Там есть некоторые постоянные накладные расходы, как для времени выполнения, так и для пространства (хеш-таблица не так быстро, как связанный список или поиск в массиве, и занимает достаточно места для уменьшения коллизий).
Ответ 11
Просто поговорим о преодолении компромисса с представлением регулярного списка смежности, поскольку другие ответы затрагивают другие аспекты.
Можно представить граф в списке смежности с запросом EdgeExists в режиме амортизированного постоянного времени, используя структуры данных Dictionary и HashSet. Идея состоит в том, чтобы удерживать вершины в словаре, и для каждой вершины мы сохраняем хэш-набор, ссылающийся на другие вершины, с которыми он имеет ребра.
Один из небольших компромиссов в этой реализации состоит в том, что вместо O (V + E) вместо O (V + E) будет иметь место сложность O (V + 2E), как в регулярном списке смежности, так как ребра представлены здесь дважды (поскольку каждая вершина имеет свой собственный хэш-набор края). Но такие операции, как AddVertex, AddEdge, RemoveEdge, могут выполняться в амортизированном времени O (1) с этой реализацией, за исключением RemoveVertex, которая принимает O (V) как матрицу смежности. Это означало бы, что кроме матрицы смежности простоты реализации не имеет каких-либо особых преимуществ. Мы можем сэкономить место на разреженном графике с почти одинаковой производительностью в этой реализации списка смежности.
Взгляните на реализации ниже в репозитории Github С#. Обратите внимание, что для взвешенного графика он использует вложенный словарь вместо комбинации словарно-хеш-набора, чтобы приспособить значение веса. Аналогично для ориентированного графа существуют отдельные хэш-множества для краев in и out.
Примечание. Я полагаю, что с помощью ленивого удаления мы можем дополнительно оптимизировать операцию RemoveVertex до O (1), даже если я не тестировал эту идею. Например, при удалении просто пометьте вершину как удаленную в словаре, а затем лениво очистите осиротевшие края во время других операций.