Матрица смежности: различия между версиями

[непроверенная версия][отпатрулированная версия]
Содержимое удалено Содержимое добавлено
Строка 47:
Использование матрицы смежности предпочтительно только в случае неразреженных графов, с большим числом рёбер, так как она требует хранения по одному биту данных для каждого элемента. Если граф разрежён, то большая часть памяти напрасно будет тратиться на хранение нулей, зато в случае неразреженных графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно <math>n^2</math> бит памяти, что может быть на порядок лучше списков смежности.
 
В алгоритмах, работающих со [[Взвешенный граф|взвешенными]] графами (например, в [[Алгоритм Флойда-Уоршелла|алгоритме Флойда-Уоршелла]]), элементы матрицы смежности вместо чисел 0 и 1, указывающих на присутствие или отсутствие ребра, часто содержат веса самих ребер. При этом на место отсутствующих ребер ставят некоторое специальное граничное значение ({{lang-en|sentinel}}), зависящее от решаемой задачи, обычно 0 или <math>\infty</math>.
 
== См. также ==