?

Log in

No account? Create an account

Entries by category: история

Массив смежности
ejuo
 В догонку к своему прошлому посту...
Массив смежности для хранения графа представляет собой одномерный массив, имеющий неоднородную структуру. Первые N (где N - число вершин(узлов) графа) элементов массива содержат числа, являющиеся индексами последующих элементов данного массива. Последующие элементы содержат номера вершин, смежных с данной. См. схему ниже.

 Мне кажется, что такое хранение графа выгодно при его высокой разреженности (число вершин намного больше числа рёбер). В случае, когда компаненты связности(рёбра) отсутствуют, получаем компактный одномерный массив размера N.
 Странно, что Яндекс по данному запросу в первых страницах(дальше не смотрел) не выдаёт определение такого представления графа.
Tags: