Когда списки смежности или матрицы являются лучшим выбором?

Мне сказали, что мы будем использовать список, если граф разреженный, и матрицу, если граф плотный . Для меня это просто грубое определение. Я не вижу многого за этим. Можете ли вы уточнить, когда это будет естественным выбором?

Заранее спасибо!

Прежде всего, обратите внимание, что разреженный означает, что у вас очень мало ребер, а плотный означает много ребер, или почти полный граф. В полном графе у вас есть ребер, где n - количество узлов.$n(n-1)/2$$n$

Теперь, когда мы используем матричное представление, мы выделяем матрицу для хранения информации о соединении узлов, например, M [ i ] [ j ] = 1, если между узлами i и j есть ребро , в противном случае M [ i ] [ j ] = 0 . Но если мы используем список смежности, то у нас есть массив узлов, и каждый узел указывает на свой список смежности, содержащий ТОЛЬКО соседние узлы .$n\times n$$M[i][j] = 1$$i$$j$$M[i][j] = 0$

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

Но если граф плотный, то число ребер близко к (полному) или к n 2, если граф направлен с помощью самоконтроля. Тогда нет преимущества использования списка смежности над матрицей.$n(n-1)/2$$n^2$

С точки зрения сложности пространства
Матрица смежности: Список смежности: O ( n + m ) где n - количество узлов, - количество ребер.$O(n^2)$
$O(n + m)$
$n$$m$

Когда граф является неориентированным деревом, тогда
матрица смежности: Список смежности: равно (лучше, чем )$O(n^2)$
$O(n + n)$$O(n)$$n^2$

Когда график направлен, завершен, с самопетлями, тогда
матрица смежности: Список смежности: есть (без разницы)$O(n^2)$
$O(n + n^2)$$O(n^2)$

И, наконец, когда вы реализуете использование матрицы, проверка наличия грани между двумя узлами занимает раз, в то время как со списком смежности это может занять линейное время по n .$O(1)$$n$

Чтобы ответить, приведем простую аналогию. Если бы вам пришлось хранить 6 унций воды, вы бы (вообще говоря) сделали это с контейнером на 5 галлонов или чашкой на 8 унций?

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

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

PS список - это просто матрица из одного столбца !!! (пытаюсь показать вам, насколько произвольно это решение / сценарий)

$N$$E$$N^2$

Сколько бит на самом деле вам нужно?

$N$$E$${N^2 \choose E}$$\log_2 {N^2 \choose E}$

$E \le \frac{N^2}{2}$

$E = \frac{N^2}{2}$$\log_2{N^2 \choose E} = N^2 + o(N^2)$$E \ll N^2$

$\log_2 N$$2E$

$p = \frac{E}{N^2}$$- \log_2{p(1-p)}$$p \approx \frac{1}{2}$