Я прочитал, что это идеально для представления разреженных графов списками смежности и плотных графов матрицей смежности. Но я хотел бы понять основное различие между разреженными и плотными графами.
В чем разница между разреженными и плотными графами?
Ответ 1
Плотный граф - это граф, в котором число ребер близко к максимальному числу ребер. Распределенный граф - это график, в котором число ребер близко к минимальному числу ребер. Разреженный граф может быть отключенным графиком.
Ответ 2
Поскольку названия указывают, что разреженные графики слабо связаны (например: деревья). Обычно число ребер находится в O (n), где n - число вершин. Поэтому списки смежности предпочтительнее, поскольку они требуют постоянного пространства для каждого ребра.
Плотные графы плотно связаны. Здесь число ребер обычно равно O (n ^ 2). Поэтому предпочтительна матрица смежности.
Чтобы дать сравнение, предположим, что граф имеет 1000 вершин.
Независимо от того, является ли граф плотным или разреженным, матрица смежности требует сохранения 1000 ^ 2 = 1 000 000 значений.
Если граф минимально связан (т.е. это дерево), список смежности требует хранения 2997 значений. Если граф полностью подключен, он требует хранения 3 000 000 значений.
Ответ 3
Из структур данных и алгоритмов с объектно-ориентированными шаблонами проектирования в C++, с. 534, Бруно П. Рейсс:
Неформально граф с относительно небольшим количеством ребер редок, а граф с большим количеством ребер плотным.
Определение (разреженный граф): разреженный граф - это граф G = (V, E), в котором | E | = O (| V |).
Определение (плотный граф) Плотный граф - это граф G = (V, E), в котором | E | = Θ (| V | 2).
Ответ 4
Основные интегральные характеристики графа - это число вершин V и количество ребер E. Отношение этих двух определяет, является ли граф разреженным или плотным (wiki page здесь).
Вся теория выбора отображения в памяти в памяти - это определение оптимального времени доступа и компромисса с памятью, учитывая предметную область и особенности использования.
Как правило, вы хотите иметь время доступа O (1) (и, таким образом, хранить график как плотную матрицу смежности), если вы не можете переносить след памяти, и в этом случае вы выбираете наиболее подходящее разреженное представление матрицы (wiki page здесь).
Ответ 5
В математике плотный граф представляет собой график, в котором число ребер близко к максимальному числу ребер. Противоположность, граф с несколькими ребрами, является разреженным графиком. Различие между разреженными и плотными графами довольно неопределенное и зависит от контекста.