Графы. Способы реализации и основные операции.

Граф G – это упорядоченная пара (V, E), где V непустое множество верши, E – множество пар элементов множестваV, называемое множеством рёбер.

Упорядоченная пара элементов из V называется дугой. Если все пары в Eупорядочены, то граф называется ориентированным (орграфом).

Если дуга е ведёт от вершины v1 к вершине v2, то говорят, что дуга е инцидентна вершине v2, а вершина v2 являютсясмежной вершине v1. В случае неориентированного графа ребро е является инцидентной обеим вершинам v1 и v2,а сами вершины – взаимно смежными.

Путь – это любая последовательность вершин орграфа такая, что в этой последовательности вершина б может следовать за вершиной а, только если существует дуга, следующая из а в б. Аналогично можно определить путь, состоящий из дуг.

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

Петля – дуга, соединяющая некоторую вершину сама с собой.

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

 

Выбор структуры данных для хранения графа в памяти имеет принципиальное значение при разработке эффективных алгоритмов. Рассмотрим два матричных и три списочных представления графа:

- матрица смежности

- матрица инцидентности

- списки смежных вершин

- список рёбер

- списки вершин и рёбер

При дальнейшем изложении будем предполагать, что вершины графа обозначены символьной строкой и всего их до n, а рёбер – до m. Каждое ребро и каждая вершина имеют вес – целое положительное число. Если граф не является помеченным, то считается, что вес равен единице.

Матрица смежности – это двумерный массив размером nxn.

При этом

Graf [i, j]={ 0, если вершина i не смежна вершине j

вес ребра, если вершина iсмежна вершине j

вес вершины, если i=j

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

Пространственная сложность этого способа V(n)~O(n^2). Способ очень хорошо, когда надо часто проверять смежность или находить вес ребра по двум заданным вершинам.

Матрица инцидентности – это двумерный массив размером nxm.

При этом

Graf [i, j]={ 0, если вершина i не инцидентна ребру j

вес ребра, если вершина iинцидентна ребру j.

Пространственная сложность этого способа V(n, m)~O(n*m). Матрица инцидентности больше всего подходит для операции «перечисление рёбер, инцидентных вершин x».

Списки смежных вершин – это одномерный массив размером n, содержащий для каждой вершины указатели на списки смежных с ней вершин.

Пространственная сложность этого способа Vmax(n)~O(n^2). Хранение списков в динамической памяти позволяет сократить объём расходуемой памяти, так как в этом случае не будет резервироваться место под n соседей для каждой вершины. Можно и сам массив представить в виде динамического списка, но это не имеет особого смысла, так как граф обычно является статичной структурой.

Этот способ хранения лучше всех других подходит для операции «перечисление всех вершин смежных с x».

Список рёбер – это одномерный массив размером m, содержащий список пар вершин, инцидентных с одним ребром графа.

Пространственная сложность этого способа V(m)~O(m). Этот способ хранения графов особенно удобен, если главная операция, которой чаще всего выполняется, это перечисление рёбер или нахождение вершин и рёбер, находящихся в отношениях инцидентности.

Граф можно представить также в виде списочной структуры, состоящей из двух типов – списки вершин и списков рёбер. Пространственная сложность этого способа V(n, m)~O(n+m).

 

16. Общие сведения о деревьях. Двоичные деревья. Основные определения и способы реализации.

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

Деревом называют орграф, для которого:

1. существует узел, в который не входит ни одной дуги (корень)

2. в каждую вершину, кроме корня, входит одна дуга

Вершины дерева подразделяют на три группы

- корень – не входит ни одной дуги

- узлы – входит одна дуга и выходит одна или более дуг

- листья – входит одна дуга и не выходит ни одной дуги

Все вершины, в которые входят дуги, исходящие из одной вершины, называют потомками этой вершины, а сама вершина – предком. Корень не имеет предка, а листья не имеют потомков.

Выделяют уровни дерева. На первом уровне может быть только одна вершина – корень, на втором – потомки корня и т.д.

Поддеревом называется вершина со всеми её потомками.

Высотой поддерева будем считать максимальную длину цепи .........

Высота пустого дерева равна 0, высота дерева из одного корня – единице.

Степенью вершины в дереве называется количество дуг, которое из неё выходит. Степень дерева равна максимальной степени вершины, входящей в дерево. При этом листьями в дереве являются вершины, имеющий степень ноль.

По величине степени деревачасто различают два типа деревьев:

-двоичные – степень дерева не больше 2

- сильноветвящиеся – степень произвольная

Дерево произвольной степени можно реализовывать как любой граф. Однако, учитывая специфику дерева как частного случая графа, можно рассмотреть отдельный способ реализации – как динамическую структуру в виде списка. Списочное представление деревьев произвольнойстепени основано на элементах, соответствующих вершинам дерева. Каждый элемент имеет поле данных и два поля указателей: указательна начало списка потомков вершины и указатель на следующий элемент в списке потомков текущего уровня.

При таком способе представления дерева обязательно следует сохранять указатель на вершину, являющуюся корнем дерева.

 

По степени вершин двоичные деревья бывают:

- строгие – вершины дерева имеют степень нуль (у листьев) или два (у узлов)

- нестрогие –вершины дерев имеют степень нуль, один или два

В общемслучае на к-том уровне двоичного дерева может быть до 2^к-1 вершин.

Двоичное дерево, содержащее только полностью заполненные уровни, называется полным.

Двоичное дерево можно реализовывать как статическую структуруданных в виде одномерного массива, а можно как динамическую структуру – в виде списка.

Списочное представление двоичных деревьев основано на элементах, соответствующих узлам дерева. Каждый элемент имеет поледаных и два поля указателей. Один указатель используется для связывания элемента с правым потомком, а другой – с левым. Листья имеют пустые указатели потомков. При таком представлении дерева обязательно следует сохранять указатель на узел, являющийся корнем дерева.

В виде массива проще всегопредставляетсяполное двоичное дерево, так как оно всегда имеет строго определённое число вершин а каждом уровне. Вершины можно пронумеровать слева направо последовательно по уровням и использовать эти номера в качестве индексов в одномерном массиве. Если число уровней дерева в процессе обработки не будет существенно изменяться, то такой способ представления полного двоичного дерева будет значительно более экономичным, чем любая списковая структура.

Адрес любой вершинывычисляется так

адрес = 2^(к-1) + i- 1

Где к- номер уровня вершины, i – номер на уровне к в полном двоичном дереве.

Адрес корня будет равен 1. Для любой вершины, имеющей индекс jв массиве, можно вычислить адреса левого и правого потомков:

Адрес_левого = 2*j

Адрес_правого = 2*j+1

Главным недостатком статического способа представления двоичного дерево является то, что массив имеет фиксированную длину. Размер массива выбирается исходя из максимального возможного количества уровней дерева, и чем менее полным является дерево, тем менее рационально используется память. Кроме того, недостатком являются большие накладные расходы при изменении структуры дерева (например, при обмене местами двух поддеревьев).

 

Основные операции.

Реализация операций будет рассматриваться для двоичных деревьев, представленных как динамическая структура.

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

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

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

 

Обходы деревьев.

Существует насколько способов обхода всех вершин дерева. Три наиболее часто используемых способа обхода называются:

- в прямом порядке

- в обратном порядке

- в симметричном порядке

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

1. если дерево является пустым деревом, то в список обхода заносится пустая запись

2. если дерево состоит из одной вершины, то в список обхода записывается эта вершина

3. ели дерево – дерево с корнем n и поддеревьями t1, t2, y3 то:

- при прохождении в прямом порядке сначала посещается корень n, затем в прямом порядке вершины поддерева tk

- при прохождении в обратном порядке сначала посещаются в обратном порядке посещаются вершины поддерева t1, далее последовательно в обратном порядке посещаются вершины поддеревьев t2…tk. Последним посещается корень n

- при прохождении в симметричном порядке сначала посещаются в симметричном порядке вершины поддерева t1, далее корень n, затем последовательно в симметричном порядке вершины поддеревьев t2…tk