Раздел 9. Структуры и алгоритмы обработки данных

41. Абстрактный тип данных. Линейные и нелинейные структуры данных. Стек, очередь, списки, деревья, графы.

Абстрактный тип данных – математическая модель плюс различные операторы, определенные в рамках этой модели. Для представления АТД используются структуры данных, которые представляют собой набор переменных, возможно, различных типов данных, объединенных определенным образом.

Очередью FIFO (First - In - First- Out - "первым пришел - первым исключается"). называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди).

Стек – это специальный тип списка, в котором все вставки и удаления и выполняются только на одном конце, называемом вершиной (top).

Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди.

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

Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.

Многосвязная структура обладает следующими свойствами:

• 1) на каждый элемент (узел, вершину) может быть произвольное количество ссылок;

• 2) каждый элемент может иметь связь с любым количеством других элементов;

• 3) каждая связка (ребро, дуга) может иметь направление и вес.

Дерево - это граф, который характеризуется следующими свойствами:

• 1. Cуществует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент - и который называется КОРНЕМ (рис. 6.8, 6.9 - A,G,M - корни).

• 2. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно осуществить доступ к любому элементу структуры.

• 3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.

42. Графы: ориентированные и неориентированные графы, представление графов в ЭВМ, алгоритмы поиска минимального остовного дерева; компоненты связности; сильная связность; алгоритмы поиска кратчайших путей в графе.

Орграф – G=(V,E) состоит из множества вершин V и множества дуг Е. Вершины так же называются узлами, а дуги – ориентированными ребрами. Дуга представима в виде упорядоченной пары вершин (v, w), где вершина v называется началом, а w – концом дуги. Дугу (v,w) записывают как v->w. Путь называется простым, если все вершины на нем, за исключением, может быть, первой и последней, различны. Цикл – простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.

Для представления орграфов можно использовать различные структуры данных. Одним из наиболее общих представлений орграфа является матрица смежности. Пример, А[i,j] = true если существует путь из i в j. Время поиска большое - О(n2), поэтому вместо матриц смежности использует список смежности. Таким образом, орграф G можно представить посредством массива HEAD, чей элемент HEAD[i] является указателем на список смежности вершины i.

Кратчайший путь в орграфе. (Дейкстры) Алгоритм строит множество S вершин, для которых кратчайшие пути от источника уже известны. На каждом шаге к множеству S добавляется та из оставшихся вершин, расстояние до которой от источника меньше чем для других оставшихся вершин. С – массив стоимостей, V – множество вершин

Procedure dijkstra;

Begin

S:={1};

For i:=2 to n do

D[i]:=C[1,i];

For i:=1 to n-1 do

Выбор из множества V/S такой вершины w что значение d[w] минимально; добавить w к множеству S

For каждая вершина v из множества V\S do

D[v] := min(d[v], d[w]+c[w,v])

End;

Обход орграфа. Поиск в глубину. Сначала все вершины помечаются как «не посещались», а после посещения метка ставится «посещались». В процессе обхода орграфа методом поиска в глубину только определенные дуги ведут к вершинам, которые ранее не посещались. Такие дуги, ведущие к новым вершинам, называются дугами дерева или и формируют для данного графа остовный лес. Обратные дуги – дуги, которые идут от потомков к предкам. Прямые дуги - дуги, идущие от предкам к истинным потомкам.

Сильно связной компонентной орграфа называется максимальное множество вершин, в котором существуют пути из любой вершины в любую другую вершину. Точная формулировка: G = (V,E) – орграф. Множество вершин разбивается на классы эквивалентности Vi, 1<=i<=r так что вершины v и w будут эквиваленты тогда и только тогда, когда существуют пути из вершины v в вершину w и из вершины w в вершину v. Пусть Еi, 1<=i<=r – множество дуг, которые начинаются и заканчиваются в множестве вершин Vi. Тогда Gi=(Vi,Ei) называются сильно связанными компонентами графа G. Орграф состоящий только из одной сильно связной компоненты, называется сильно связным.

НеОрграф – G=(V,E) состоит из конечного множества вершин V и множества ребер Е. Если для вершин v1 и vn существует путь v1-vn, то эти вершины называются связными. Граф называется связным, если в нем любая пара вершин связная. Пусть есть граф G = (V,E) с множеством вершин V и множеством ребер Е. Граф G’ = (V’,E’) называется подграфом графа G, если: 1) множество V’ является подмножеством множества М; 2) множество Е’ состоит из ребер (v,w) множества Е таких, что обе вершины v и w принадлежат V’.

Представления неорграфов – матрица смежности, список смежности.

Остовным деревом графа G называется свободное дерево, содержащее все вершины V графа G. Свойство остовных деревьев минимальной стоимости (ОДМС). Пусть G = (V,E) – связный граф с заданной функцией стоимости, определенной на множестве ребер. Обозначим через U подмножество множества вершин V. Если (u, v) - такое ребро наименьшей стоимости, что u из U, v из V\U, тогда для графа G существует остовное дерево минимальной стоимости, содержащее ребро (u,v).

Алгоритм прима: Построение начинается с дерева, включающего в себя одну (произвольную) вершину. В течение работы алгоритма дерево разрастается, пока не охватит все вершины исходного графа. На каждом шаге алгоритма к текущему дереву присоединяется самое лёгкое из рёбер, соединяющих вершину из построенного дерева, и вершину не из дерева.

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

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

Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными компонентамиорграфа называются его максимальные по включению сильно связные подграфы.

Алгоритм дейкстры (поиск кратч пути):

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

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

Алгоритм Флойда

Основная идея алгоритма. Пусть есть три вершины i, j, k и заданы расстояния между ними. Если выполняется неравенство A[i,k]+A[k,j]<A[i,j], то целесообразно заменить путь i->j путем i->k->j. Такая замена выполняется систематически в процессе выполнения данного алгоритма.

Шаг 0. Определяем начальную матрицу расстояния A0 и матрицу последовательности вершин S0. Каждый диагональный элемент обеих матриц равен 0, таким образом, показывая, что эти элементы в вычислениях не участвуют. Полагаем k = 1.

Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения замены описанной выше, ко всем элементам A[i,j] матрицы Ak-1. Если выполняется неравенство a[i,k]+a[k,j]<a[I,j], тогда выполняем следующие действия:

создаем матрицу Ak путем замены в матрице Ak-1 элемента A[i,j] на сумму A[i,k]+A[k,j] ;