Сетевые иерархии
Ключевые слова: иерархия
Иерархическая иерархия строится по принципу - "у одного узла может быть только один родитель". Циклические ссылки не допускаются, т.е. запрещена ситуация, когда у А родитель Б, а у Б родитель А.
Сетевая иерархия более произвольная - "у одного узла может быть любое число родителей".
При этом возможны циклические ссылки. В некоторых сетевых иерархиях их пытаются запретить, но чаще всего это сделать невозможно.
Многие реальные структуры строятся по принципу сетевых иерархий, а не иерархических.
Например, ссылки в книге знаний образуют сетевую иерархию.
Структура подчиненности документов также образует сетевую иерархию.
Представление сетевой иерархии
Сетевая иерархия представляется в виде регистра сведений с измерениями {Родитель, Ребенок}
Дерево сетевой иерархии
Возникает вопрос - можно ли построить конечное иерархическое дерево, представляющее собой сетевую иерархию?
Ответ утвердительный.
Алгоритм построения такой иерархии:
1. Выбираем все элементы верхнего уровня (для которых нет родителей).
2. Для каждого из этих элементов добавляем в подчиненные элементы всех их детей.
3. Для борьбы с зацикливанием - если при раскрытии некоего элемента на некотором уровне встретился этот же элемент, он указывается, как подчиненный элемент, но дальнейшая его расшифровка прекращается.
4. Если остались элементы, не включенные в иерархию, то берем каждый из них и повторяем начиная с пункта 1.
Рассмотрим иерархию (Родитель-Ребенок):
А-Б
Б-В
В-Д
А-В
Б-Е
У-Ю
Ю-Я
Я-У
В результате будет построено иерархическое дерево:
А
-Б
--В
---Д
--Е
-В
---Д
У
-Ю
--Я
---У*
* - звездочкой показаны зацикливания
|