Контрольные вопросы
Перечислите свойства динамических структур данных.
Опишите способы управления динамической памятью.
Создание и применение связных линейных списков.
Операции над линейными списками.
Нелинейные разветвленные списки. Назначение, характеристики способы представления.
7. Нелинейные структуры данных
7.1. Графы и деревья
Теория графов является важной частью вычислительной математики. Многосвязная структура граф находит применение при организации банков данных, управлении базами данных, в системах имитационного моделирования сложных комплексов, в системах искусственного интеллекта, в задачах планирования. Алгоритмы обработки нелинейных разветвленных списков, к которым могут быть отнесены и графы, были приведены ранее.
Граф– нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта, обладающая следующими свойствами:
на каждый элемент (узел, вершину) может быть произвольное количество ссылок;
каждый элемент может иметь связь с любым количеством других элементов;
каждая связка (ребро, дуга) может иметь направление и вес.
В узлах графа содержится информация об элементах объекта. Связи между узлами задаются ребрами графа. Ребра могут иметь направленность, показываемую стрелками, тогда они называются ориентированными, ребра без стрелок – неориентированные.
С точки зрения теории графов не имеет значения, какой смысл вкладывается в вершины и ребра. Вершинами могут быть населенными пункты, а ребрами дороги, соединяющие их, или вершинами являться подпрограммы, соединение вершин ребрами означает взаимодействие подпрограмм. Часто имеет значение направления дуги в графе.
Граф, все связи которого ориентированные, называется ориентированнымилиорграфом. Граф со всеми неориентированными связями называетсянеориентированным, а граф со связями обоих типов –смешанным графом. Обозначение связей: неориентированных – (A,B), ориентированных – <A,B>. Примеры изображений графов приведены на рис. 7.1. Скобочное представление имеет вид: а). ((A,B),(B,A)) и б). (< A,B >,< B,A >).
Для ориентированного графа число ребер, входящих в узел, называется полустепенью заходаузла, выходящих из узла –полустепенью исхода. Количество входящих и выходящих ребер может быть любым, в том числе и нулевым. Если ребрам графа соответствуют некоторые значения, то граф и ребра называютсявзвешенными.Мультиграфомназывается граф, имеющий параллельные (соединяющие одни и те же вершины) ребра, в противном случае граф называетсяпростым.
(B) (a) (b) (a)
а). б).
Рис. 7.1. Граф неориентированный (а) и ориентированный (б).
Путь в графе – последовательность узлов, связанных ребрами. Элементарным называется путь, в котором все ребра различны, простым называется путь, в котором все вершины различны. Путь, начинающийся и заканчивающийся в одной и той же вершине, называется циклом, а граф, содержащий такие пути – циклическим. Граф, в котором отсутствуют циклы, называется ациклическим. Два узла графа являются смежными, если существует путь от одного из них до другого. Узел называется инцидентным к ребру, если он является его вершиной, т.е. ребро направлено к узлу.
С помощью графа можно наглядно представить разветвляющиеся связи, которые и привели к общеупотребительному термину «дерево». Деревом называется орграф, для которого существует узел, в которой не входит ни одной дуги – корень и в каждую вершину, кроме корня, входит одна дуга. Степенью узла в дереве называется количество дуг, которое из него выходит. Степень дерева равна максимальной степени узла, входящего в дерево.
Существует несколько способов графического изображения деревьев (рис. 7.1).
Первый способ состоит в использовании для изображения поддеревьев известного метода диаграмм Венна, второй – метода вкладывающихся друг в друга скобок, третий способ, применяемый при составлении оглавлений книг. При применении последнего способа каждой вершине приписывается числовой номер, который должен быть меньше номеров, приписанных корневым вершинам присоединенных к ней поддеревьев. Все эти представления демонстрируют одну и ту же структуру и поэтому эквивалентны.