Гнездовое хранение структуры

При этом способе хранения структуры каждая вершина задается гнездом следующего вида:

где:

О_i - номер объекта;

А₁ - первый адрес перехода к следующей вершине;

А₂ - второй адрес перехода к следующей вершине.

Гнездо построено в предположении, что от каждой вершины отходит не больше двух дуг. Пусть структура операции выражена следующим образом:

Тогда хранение структуры с помощью гнезд можно выразить следующим способом:

Каждое гнездо состоит из 3^х слов. Общий объем занимаемой памяти составит

Матрица смежности с битовым заданием строк и хранение гнездами занимают одинаковый объем памяти, однако гнездовой способ не имеет ограничения n < 16 или n < 32 и, в тоже время, является более гибким. Например, для удаления перехода Р₅ нужно уничтожить связь Р₄ Р₅. Для этого необходимо лишь в гнезде с адресом А₃ убрать адрес А₄ и поставить * (отсутствие адреса). В то время как в 1-ом способе для удаления лишнего перехода понадобиться проделать ряд операций над битовыми строками.

Сложность использования гнездового способа возникает, когда из вершины графа структуры выходит больше двух вершин. В этом случае необходимо либо применять гнезда с большим количеством адресов, либо использовать псевдопереходы.