Изменения

Матрица смежности занимает <tex>O(|V|^2)</tex> памяти. За <tex>O(1)</tex> можно определить вес ребра или его наличие между любыми двумя вершинами. Такой способ хранения графа хорошо подходит для плотных графов, в которых количество ребер примерно равно количеству число рёбер между различными парами вершин в квадрате<tex>\Omega(|V|^2)</tex>.