Ориентированные и неориентированные графы. Алгоритмы на графах

Эффективность алгоритма пирамидальной сортировки

Блок-схема пирамидальной сортировки

Пример работы пирамидальной сортировки

Необходимо отсортировать массив 13, 0, 29, 56, 7, 15, 78. В дальнейшем на рисунках в этой лекции основание пирамиды – это цифры выделенные курсивом и жирным шрифтом, а уже отсортированная последовательность – цифры с подчёркиванием и жирным шрифтом. Элементы, которые меняются местами, выделяются серым тоном.

Получим просеянную начальную пирамиду (рис. 15.2), т.е. Осуществим первую часть алгоритма:

Далее вторая часть (рис. 15.3), где выполняются n-1=7-1=6 перемещений рабочего элемента в вершину с последующим просеиванием:

На рисунке 15.5 приведена блок-схема алгоритма пирамидальной сортировки, а на рис. 15.6 приведена блок-схема алгоритма процедуры proseit_one_element, которая просеивает один элемент. Переменная b – это локальная переменная процедуры proseit_one_element, которой присваиваются при вызове данной процедуры значения сначала n, а потом i-1.

Данная сортировка очень эффективно сортирует массивы большого размера и имеет сложность пропорциональную n*logn.

Что такое «графы»

Если требуется наглядно представить отношения между какими-либо объектами, то для этого используется естественная модель таких отношений – ориентированные и неориентированные графы.

Ориентированный граф.Эта структура так же называется орграф.Она состоит из множества вершин v и множества дуг e. Орграф через вершины и дуги определяют так g=(v, e).

Узлами называют вершины орграфа, а ориентированными ребрами – его дуги. Дугу можно представить в виде упорядоченной пары вершин (рис. 16.1), где v - начало, а w - конец дуги. Дугу записывают как vàw или (v, w), а произносится это так: дуга ведёт от вершины v к вершине w или вершина w смежная с вершиной v.

Путь по орграфу от точки v₁ до точки v_n – это последовательность вершин v₁, v₂, ..., v_n, для которой существуют дуги v₁àv₂, v₂àv₃, ...,v_n-1àv_n. В этом случае длина пути будет равна n-1.

Если к вершинам или к дугам орграфа присоединены метки, то это помеченный орграф. Метка– это имя, вес (стоимость дуги), или значение какого-либо заданного типа

Неориентированный граф. Данная структура так же называется граф. Все выше приведённые определения для орграфа так же применимы и для графа с учётом некоторых особенностей. Граф в отличии от орграфа состоит из рёбер (v, w), которые соединяют неориентированные пары вершин (рис. 16.2). Такой граф обладает свойством (v, w)=(w, v), т.е. Значение метки для ребра не зависит от направления.

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