Методы решения оптимизационных задач

1.

Методы решения
оптимизационных задач
М. Лапенок
Уральский государственный
педагогический университет, г. Екатеринбург

2. Введение

Примеры дискретных оптимизационных задач
задача о кратчайшем пути:
Пусть имеется несколько городов и известны попарные расстояния между
соседними городами. При этом два города считаются соседними, если есть
дорога, их соединяющая, и не проходящая через какой-либо другой город.
Требуется найти кратчайший путь между некоторой парой городов;
задача оптимального назначения:
Пусть имеется n станков и n деталей, каждую деталь можно обрабатывать на
любом станке, но время обработки детали на одном станке может отличаться
от времени ее обработки на другом. Пусть эти времена для каждой пары
«станок — деталь» заданы. Требуется так организовать производство
деталей, т.е. разместить их по станкам, чтобы суммарное время работы было
наименьшим ;
задача коммивояжера
Путешественник хочет объехать n городов, побывав в каждом ровно по
одному разу, и вернуться в исходный, затратив при этом минимальную сумму
на поездку. Затраты па поездку складываются из затрат на переезды между
парами городов, а эти затраты заранее известны.

3.

Общие свойства дискретных оптимизационных задач
1.
2.
3.
В каждой задаче имеется лишь конечное число
вариантов, из которых требуется осуществить выбор
(путей между городами, способов распределения деталей
по станкам, маршрутов передвижения путешественника).
Каждому варианту выбора сопоставлена некоторая
числовая характеристика (длина пути, суммарное время
работы, стоимость поездки).
Требуется выбрать вариант, числовая характеристика
которого достигает экстремума.
Методы решения подобных задач
1.
полный перебор (поочередно пересмотреть все варианты
и выбрать требуемый);
2.
дискретная оптимизация.

4.

Алгоритмы и их сложности
Типы задач: массовые и индивидуальные задачи.
Все вышеприведенные примеры дают образцы именно
массовых задач.
Индивидуальная задача получается из массовой путем
фиксации набора условий.
Например, индивидуальная задача коммивояжера получается
из массовой, если зафиксировано число городов и
определены затраты на переезды между всеми парами
городов.
С каждой конкретной массовой задачей (в дальнейшем
просто задачей) будем связывать некоторое число (или
несколько чисел), называемое ее размером, которое
выражает меру количества входных данных. Например,
размером задачи коммивояжера естественно считать число
городов n, которые собирается посетить путешественник.

5.

Алгоритмы и их сложности
Говорят, что алгоритм решает некоторую массовую задачу, если он
решает любую ее индивидуальную задачу.
Для оценки качества алгоритмов имеется ряд критериев.
Одним из важнейших таких критериев является понятие вычислительной
сложности (или просто сложности) алгоритма.
Неформально, под сложностью алгоритма решения массовой задачи
будем понимать максимально возможное число шагов, выполняемых
алгоритмом для решения любой из индивидуальных задач,
вычисленное как функция размерности задачи.
Под шагом алгоритма будем понимать выполнение "простой" операции,
обычно аппаратно реализованной на любой ЭВМ, а именно любой
арифметической операции, операции сравнения, пересылки,
косвенной адресации и т.п.
При этом будем рассматривать асимптотическую сложность алгоритма,
(а не точную сложность, зависящую от конкретного вида машинных
команд), т.е. порядок роста числа шагов алгоритма при
неограниченном росте размерности задачи.
При сравнении скорости роста двух неотрицательных функций f(n) и g(n)
будем использовать следующие понятия.

6.

Алгоритмы и их сложности
При сравнении скорости роста двух неотрицательных
функций f(n) и g(n) будем использовать следующие
понятия.
Будем говорить, что функция f(n) имеет порядок роста
не более чем g(n) (запись: f(n) = О(g(n))),
если существуют константы с, N > 0 такие,
что f(n) < c·g(n) для всех n > N.
Говорят, что функция f(n) имеет порядок роста
не менее чем g(n) (запись: f(n) = Ω (g(n)) ),
если существуют константы с, N > 0 такие,
что f(n) ≥ c g(n) для всех n > N.

7.

Алгоритмы и их сложности
Например, справедливы следующие соотношения:
log2n = О(n); n2 = О(2n); n = Ω (log2n):
На практике алгоритм решения некоторой задачи считается
достаточно хорошим, если сложность этого алгоритма есть
O(n·p) при некотором р > 0.
В этом случае говорят, что задача полиномиально
разрешима,
или, что то же самое, задача может быть решена за
полиномиальное время.
Важность понятия сложности алгоритма хорошо
иллюстрируют следующие таблицы.

8.

Алгоритмы и их сложности
Таблица 1.1. Максимальная размерность задач,
разрешимых за данное время
Таблица 1.2. Влияние технического совершенствования ЭВМ на
полиномиальные и экспоненциальные алгоритмы

9.

Алгоритмы и их сложности
Пусть для решения некоторой задачи имеется
алгоритм сложности n3. Тогда, как это
следует из таблицы 1.2, десятикратное
увеличение скорости быстродействия ЭВМ
позволит
увеличить
размер
задачи,
решаемой за 1 минуту в 2,15 раз. Однако
замена этого алгоритма другим, имеющим
сложность n2, позволит решать задачу в 6
раз большего размера (см. таблицу 1.1).
Если в качестве единицы взять 1 час, то
сравнение будет еще более впечатляющим.

10.

Запись алгоритмов
Алгоритмы будем записывать на некотором специальном языке, который
назовем упрощенным Паскалем.
В этом языке возможно использование любого типа данных: тип данных
какой-либо переменной и ее область действия должны быть ясны либо
по ее названию, либо по контексту.
В упрощенном Паскале применяются традиционные конструкции
математики и языков программирования такие, как выражения,
условия, операторы и процедуры. Операторы языка Паскаль
используются, как правило, в соответствии с правилами языка
Паскаль, но иногда будут применяться неформальные конструкции
такие, как, например,
1) циклы for х ϵ X do Р, т.е. выполнять оператор Р для всех элементов х
множества X в произвольной последовательности;
2) x[i] ↔ x[j] — переставить i-ый и j-ый элементы массива; или описание
типа: "пусть х — наименьший элемент множества X".
3) Будем также предполагать, что все операторы, записанные в одной
строке алгоритма, образуют один составной оператор. Поэтому
ключевые слова begin и end, идентифицирующие этот оператор, будут
опускаться.

11.

Запись алгоритмов
АЛГОРИТМ 1.1. ВЫБОР МИНИМАЛЬНОГО ЭЛЕМЕНТА
Данные: числовое множество X.
Результат: число minX - минимальный элемент X
1.
begin
2.
minX := +∞;
3.
for х ϵ X do
4.
if x < minX then minX := x;
5.
end.
Поясним на этом примере понятие сложности алгоритма.
Размером этой задачи естественно считать n — количество элементов во
множестве X.
Цикл в строках 3-4 работает ровно n раз. В строке 4 при каждом шаге цикла
осуществляется одна операция сравнения и, в худшем случае, одна
операция присваивания.
Таким образом, в строках 3 и 4 проводится не более чем 2n операций. С учетом
оператора присваивания в строке 2 получаем, что число шагов алгоритма
не превосходит 2n+1. Значит сложность этого алгоритма есть О(n).
Алгоритмы такой сложности принято называть линейными.

12.

Запись алгоритмов
Повсюду в дальнейшем будем использовать следующие обозначения. Для
произвольного вещественного числа х через |_x_|
(читается дно х) и |¯х¯| (потолок х) будем обозначить соответственно
наибольшее целое число, не превосходящее х, и наименьшее целое,
не меньшее х.
Все логарифмы являются логарифмами чисел по основанию 2.
Поэтому вместо log2x будем писать logx.

13.

Графы и сети
Многие задачи дискретной оптимизации могут быть
интерпретированы как задачи на сетях и графах.
Поэтому повторим основные понятия теории графов.

14.

Графы и сети
Рис. 2.1. Изображение графов и орграфов,
а) Неориентированный граф, б) Ориентированный граф

15.

Графы и сети
Удобно вершины графа считать пронумерованными
натуральными числами, и на рисунках сразу вместо точки
ставить соответствующий номер
Число ребер, инцидентных данной вершине, называется
степенью вершины.
Вершины степени 1 называют висячими вершинами,
а степени 0 — изолированными.
Например, в графе, изображенном на рис. 2.1.а,
вершины 2, 5, 6 являются висячими.
Степенью захода узла в некотором орграфе называется число
дуг, в нее входящих,
степенью исхода — из нее исходящих. Под степенью узла
будем понимать сумму степеней исхода и захода данного
узла. Например, в орграфе, изображенном на рис. 2.1.б,
степень исхода узла 1 равна 2, а степень захода — 1.

16.

Графы и сети
Цепью (соответственно путем) в графе (орграфе)
G = (V,E) назовем чередующуюся
последовательность вершин и ребер
(узлов и дуг) v0,e0, v1, ... ,ek-1, vk такую,
что каждое ребро ek соединяет вершины vk и vk+1
(соответственно исходит из vk и входит в vk+1).
Вершины (узлы) v0 и vk будем называть
соответственно началом и концом цепи (пути).
Если все вершины (узлы) цепи (пути) различны, то
такую цепь (путь) будем называть
простой цепью (простым путем).

17.

Графы и сети
Цепь в графе (соответственно путь), начальная и
конечная вершины (узлы) которого совпадают,
будем называть циклом {контуром).
Если в цикле (соответственно в контуре) все
промежуточные вершины различны, то такой цикл
(контур) будем называть простым.
Иногда нам будет удобно цепь (путь)
v0,e0,v1, ... , ek-1,vk отождествлять
с множеством ребер (дуг) е0, ... , ek-1
или вершин (узлов) v0,v1, ... ,vk,
его образующих.
Длиной цепи (пути) будем называть число входящих
в нее ребер (дуг).

18.

Графы и сети

19.

Графы и сети
Граф, имеющий ровно одну компоненту связности,
будем называть связным.
Из определения вытекает, что неориентированный граф
G=(V,E) связен
тогда и только тогда, когда для любых вершин v,w V
существует цепь в графе G, их соединяющая.
Всюду в дальнейшем через |А| будем обозначать
количество элементов конечного множества А.
Говоря о некотором графе или орграфе G=(V,E),
через n будем обозначать количество вершин (или
узлов), то есть будем полагать n=|V|,
через m — количество ребер (или дуг), то есть будем
полагать m=|E|.

20.

Графы и сети
Условимся считать, что в графах и орграфах
нет ребер вида {v,v} и дуг вида (v,v)
(так называемых петель), и,
что для любых v,w V существует не более одного
ребра или не более двух дуг им инцидентных
Тогда справедливы неравенства:
m ≤ n∙(n-1 )/2 — для неориентированных графов,
m ≤ n∙(n-l) — для орграфов.

21. Деревья

Одним из важнейших понятий в теории графов является
понятие
дерева.
Деревом
называется
связный
неориентированный граф без циклов.
Теорема1. Пусть G = (V,E) — граф, n=|V|, m=|E|.
Тогда следующие условия эквивалентны:
1.
G — дерево.
2.
Для любых двух вершин
u,v V существует и
притом единственная цепь, их соединяющая.
3.
Граф G связен, и m=n-l.
4.
Граф G не содержит циклов, и m=n-l.
5.
Граф G не содержит циклов, и при соединении
любых двух несмежных вершин ребром
образуется ровно один цикл.

22. Корневое дерево

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

23. Корневое дерево

Корневое дерево
Корневое дерево обычно изображают корнем вверх,
располагая узлы одной глубины на одном уровне.
У корневого дерева на рис. 2.2
узел с номером 1 является корнем, узлы 4, 5, 6, 7 —листья.
Высота этого дерева равна 2.
1
2
4
3
5
6
7
Рис 2.2.Корневое дерево

24. Корневое дерево

Пусть G - (V,E) — корневое дерево, v,w V.
Будем говорить, что узел v является отцом узла w,
a w — сыном узла v, если (v,w) Е.
Если в G существует путь из v до w, то будем говорить,
что w — потомок v, a v — предок w.
Вершина, не имеющая сыновей, называется листом.
Глубина узла v в корневом дереве — это длина пути из
корня в v. При этом глубину корня будем считать равной
нулю.
Высота узла v — это длина самого длинного пути из v
в какой-нибудь лист.
Высотой дерева будем называть высоту его корня.

25. Двоичные (бинарные) деревья

Корневое дерево, каждый узел которого имеет не более двух
сыновей, будем называть двоичным деревом.
Методом математической индукции легко доказать следующее
утверждение.
Лемма 2.2. Двоичное дерево высоты k содержит не более 2k
листьев.
Специфика дискретных оптимизационных задач практически всегда
предполагает, что, как ребра графов, так и дуги орграфов, снабжены
некоторой числовой характеристикой.
Практический смысл этих характеристик может быть самым
разнообразным.
Например, в задачах, сформулированных ранее, это были:
длина дороги между соседними городами (задача о кратчайшем
пути), время обработки конкретной детали на конкретном станке
(задача оптимального назначения), стоимость проезда из одного
города в другой (задача коммивояжера).

26. Двоичные (бинарные) деревья

Граф (орграф) будем называть взвешенным,
если задана функция с: Е→R, иначе говоря,
каждому ребру (дуге) из Е
поставлено в соответствие вещественное число с(е).
Число с(е) назовем весом ребра (дуги) е.
Впрочем, в зависимости от специфики той или иной
задачи дискретной оптимизации,
число с(е) будем также называть стоимостью ребра
(дуги) е,
или пропускной способностью ребра (дуги) е.

27. Машинное представление графов и сетей

Ориентированный взвешенный граф будем
называть сетью.
Таким образом, взвешенный граф или сеть задаются тройкой G =
(V,E,c).
Задать граф (орграф) — значит описать множества его вершин
(узлов) и ребер (дуг),
а в случае взвешенного графа или сети, описать также функцию
весов с: Е→R.
Мы будем предполагать, что вершины графов и узлы сетей
занумерованы натуральными числами от 1 до n. Поэтому для
описания множества вершин (узлов),
если не указана какая-нибудь дополнительная информация,
достаточно задать одно число —
число вершин (узлов) n.

28. Машинное представление графов и сетей

Разберем несколько способов машинного представления
графа (орграфа) G = (V,E), где n= |V |, m= | Е |.
Матрица смежностей
определяется как матрица А размера n х n,
в которой A[v,w]=l тогда и только тогда,
когда ребро {v,w} (соответственно дуга (v,w)) имеется в
графе (орграфе),
и A[v,w]=0 в противном случае.
1
2
4
3
5
А=
0
1
1
1
0
1
0
1
0
0
1
1
0
1
0
1
0
1
0
1
Рис 2.3. а) Неориентированный граф и его матрица смежностей,
0
0
0
1
0

29. Машинное представление графов и сетей

1
4
5
А=
2
3
0
1
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
1
0
1
Рис 2.3. б) Ориентированный граф и его матрица
смежностей
Легко видеть, что матрица смежностей
неориентированного графа является симметричной.
Представление графа матрицей смежностей удобно для тех
алгоритмов, которым многократно нужно выяснять,
есть ли в графе ребро (дуга), соединяющее заданные
вершины v и w,
ибо это осуществляется за один шаг — одно обращение к
матрице.
0
0
1
0
0

30. Машинное представление графов и сетей

Однако, для ответа
на вопросы
Машинное
представление графов и сетей
«к каким вершинам (узлам) ведут ребра (дуги) из V?»
и «какова степень вершины (узла) v?»
нужно просмотреть всю строку матрицы с номером v.
Следовательно, сложность ответа на любой из этих
вопросов для фиксированной вершины есть О(n).
Матрица смежностей является достаточно удобным
способом представления графа, если не принимать во
внимание затраты памяти: граф на n вершинах требует
памяти пропорционально n2, независимо от числа
ребер.
Особенно сильно этот недостаток проявляется для
разреженных графов, т.е. таких, в которых число ребер
невелико по сравнению с числом вершин: в этом
случае матрица смежностей почти целиком состоит из

31. Машинное представление графов и сетей

Взвешенный граф (или сеть) G = (V,E,c),
может быть задан в ЭВМ матрицей весов А,
в которой полагают A[v,w] = c({v,w}) - весу ребра
{v,w} (или весу дуги c((v,w)) ),
и A[v,w] = ∞ — для ребер (дуг), отсутствующих в
графе (сети).
Иногда, в зависимости от специфики конкретной
задачи, уточняют знак бесконечности, выбирая либо
+∞, либо - ∞.

32. Машинное представление графов и сетей

Более экономным, чем матрица смежностей, и
универсальным способом является представление
графов и сетей списками смежностей.
Списком смежностей для вершины (узла) v называется
список всех вершин (узлов) w, смежных с v.
Граф (орграф) представляется с помощью п списков
смежностей: по одному для каждой вершины (узла).
Точнее, каждый элемент такого списка является
записью r, имеющей два поля. Первое поле, обозначим
его r^.строка, предназначается для хранения вершин,
смежных данной; второе — r^.след — для ссылки на
следующую запись в списке. При этом будем считать,
что r^.след = nil для последней записи в списке.

33. Машинное представление графов и сетей

Начало каждого списка хранится в массиве НАЧАЛО,
а именно, HAЧAJIO[v] является указателем на начало
списка, соответствующего вершине (узлу) v;
если v — изолированная вершина (узел), то полагаем
HAЧAЛО[v] = nil.
Весь такой список для неориентированного графа
будем обозначать ЗАПИСЬ[v].
Ясно, что в этом случае каждое ребро (v, w) графа
представлено дважды:
вершиной w в списке ЗАПИСЬ[v] и вершиной v в
списке ЗАПИСЬ[w].

34. Машинное представление графов и сетей

НАЧАЛО
1
3
5
2
4
6
1
2
3
2
1
4
nil
3
1
4
nil
4
1
2
5
6
4
4
nil
3
nil
nil
Рис 2.3. Неориентированный граф и его списки смежностей.
5
nil

35. Машинное представление графов и сетей

Для ориентированных графов возможны два способа формирования
списков смежностей.
В первом в список ЗАПИСЬ[v] включаются лишь те узлы w, для
которых (v, w)
E,
т.е. те узлы, к которым ведут дуги из w.
Такой список будем обозначать СЛЕД[v]. Д
ругой способ — включать в список ЗАПИСЬ[v] лишь те узлы w, из
которых идут дуги в узел v.
Этот список будем обозначать ПРЕДШ[v].
Для представления взвешенного графа или сети достаточно в
соответствующих
списках
смежностей
отвести
одно
дополнительное поле для весов ребер или дуг.

36. Машинное представление графов и сетей

Проанализируем способ представления графов и сетей списками
смежностей.
Понятно, что объем памяти, необходимый для представления графа или
сети, имеет порядок n+m, что, вообще говоря, лучше, чем
представление матрицей смежности. Особенно заметным этот
выигрыш по памяти становится для редких графов (m ˂˂ n2).
Ограничимся далее случаем неориентированного графа. Для ответа на
вопросы
имеется ли в графе (орграфе) ребро {v,w} (дуга (v,w))?
к каким вершинам (узлам) ведут ребра (дуги) из V?
какова степень вершины (узла) v?
достаточно просмотреть список ЗАПИСЬ[v].
Сложность такого просмотра есть О(n) — такая же, как и в случае
матрицы смежностей.

37. Машинное представление графов и сетей

Однако, если определять степень всех вершин графа,
то здесь сложность ответа будет O(n+m), так как каждое ребро
смотрится ровно два раза,
в то время как для матрицы смежностей вычислительная сложность
такого просмотра есть О(n2).
Списки смежностей являются достаточно удобным инструментом для
решения задач добавления или удаления ребер из графа.
Осуществляются подобные процедуры стандартными средствами для
работы со списками.
Понятно, что сложность процедуры добавления ребра является
константой, если известно, что данного ребра в графе нет, и имеет
сложность О(n),
если предварительно требуется осуществить поиск для ответа на вопрос
о том, есть или нет данное ребро в графе. Аналогично обстоит дело
и с процедурой удаления ребра (дуги) из графа (соответственно
орграфа).

38. ЗАДАЧИ

Докажите, что в любом графе число вершин нечетной степени
четно.
2.
В некоторых задачах удобно представлять граф связанными
списками смежностей. А именно, каждая запись в списке
3AПИСЬ[v] имеет еще одно поле, где в записи, содержащей вер
шину w, в дополнительном поле ставится ссылка на ту запись
списка 3AПИСЬ[w], которая содержит вершину v. Напишите
алгоритмы удаления и добавления ребра в граф, заданный
связанными списками смежностей.
3.
Предложите алгоритм, сложности О(n), записывающий все
вершины в списке ЗАПИСЬ[v] в обратном порядке.
4.
Пусть некоторый граф задан матрицей смежностей.
Рассмотрим следующую процедуру:
1. begin х:=0;
2. for р:=1 to n do
3. for q:=p to n do
4. х:= х + A[p,q];
5. end.
Чему будет равен х в результате работы этой процедуры?
1.

39. Машинное представление графов и сетей

В тех случаях, когда нет необходимости добавлять и
удалять ребра или дуги из графа, все списки
смежностей вместе с массивом НАЧАЛО можно
упаковать в один массив, называемый массивом
смежностей.
Массив смежностей представляет собой одномерный
массив А длины (n+2m+2) для неориентированного
графа, и (n+m+2) — для ориентированного.
Рассмотрим случай неориентированного графа. Первые
n+1 элементов массива А являются адресной
частью, а именно, значением A[v] (v=l,2,...,n)
является адрес (индекс) в массиве А, начиная с
которого в А записаны подряд все вершины,
смежные с вершиной v; А[n+1] указывает на конец
массива.

40. Машинное представление графов и сетей

Поскольку каждое ребро графа встречается в таком
массиве дважды (и имеет индексы в массиве от
А[n+2] до А[n+1]-1), то массив действительно имеет
длину n+2m+2. Отсюда следует, что этот способ
представления графа требует меньше памяти, чем
матрица смежностей и чем списки смежностей (так
как в последнем случае нет нужды в храпении
ссылок на следующие записи).
Для ориентированных графов в массиве смежностей,
так же как и в списках смежностей, можно хранить
дуги по одному разу, записывая либо только
исходящие дуги, либо только входящие. И в том, и в
другом случае массив будет иметь длину n+m+2 .

41. Машинное представление графов и сетей

Пример. Для неориентированного графа
1
2
3
4
массив смежностей должен быть
следующим:
6 8 10 13 14 2 3 1 3 1 2 4 3 32767

42. Машинное представление графов и сетей

Поясним на примере:
Количество вершин n = 4
Количество ребер m = 4
Ниже перечислены для указанного в примере
графа вершины и соответствующие каждой
вершине смежные вершины.
1: 2, 3;
2: 1, 3;
3: 1, 2, 4;
4: 3.

43. Машинное представление графов и сетей

Для взвешенного неориентированного графа
(25)
1
(4)
2
(0)
3
4
(7)
массив смежностей должен быть следующим:
6 10 14 20 nil 2 25 3 4 1 25 3 0 1 4 2 0 4 7 3 7 nil
22 – количество элементов массива
32767

44. Машинное представление графов и сетей

Поясним
Количество вершин n = 4
Количество ребер m = 4
Ниже перечислены для указанного в примере графа вершины
и соответствующие каждой вершине пары вида (вес,
смежная вершина).
1: (25, 2); (4, 3);
2: (25, 1); (0, 3);
3: (4, 1); (0, 2); (7, 4);
4: (7, 3);

45. Машинное представление графов и сетей

Вернемся к предложенным на прошлой паре задачам.
После решения задачи «Предложите алгоритм, сложности
О(n), записывающий все вершины в списке ЗАПИСЬ[v] в
обратном порядке»
Программа, работающая по указанному алгоритму должна
выдавать соответствующие каждой вершине пары вида
(вес, смежная вершина) в обратном порядке.
1: (4, 3); (25, 2);
2: (0, 3); (25, 1);
3: (7, 4); (0, 2); (4, 1);
4: (7, 3).

46. Решение задачи

Входные данные содержат описание графа,
заданного массивом смежности.
В первой строке n - число элементов в массиве.
Далее построчно расположен массив
смежности (не более 10 чисел в одной строке).
Последний элемент массива равен 32767.
22
6 10 14 20 22 2 25 3 4 1
25 3 0 1 4 2 0 4 7 3
7 32767

47. Решение задачи

На выходе программа построчно выдает для каждой вершины
(начиная с первой и до n-ой) пары вида
(вес, смежная вершина) в прямом порядке.
А затем для каждой вершины (опять начиная с первой и до
N-ой) пары вида
(вес, смежная вершина) в прямом порядке.
Количество вершин n = 4
Cписок смежности в прямом порядке:
1: (25, 2); 1: (4, 3);
2: (25, 1); 2: (0, 3);
3: (4, 1); 3: (0, 2); 3: (7, 4);
4: (7, 3);
Cписок смежности в обратном порядке:
1: (4, 3); 1: (25, 2);
2: (0, 3); 2: (25, 1);
3: (7, 4); 3: (0, 2); 3: (4, 1);
4: (7, 3);

48. Программа на C++

// Библиотеки
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
void main() {
int n = 0;
vector < pair < int, pair<int,int> > > g; // ребра: вес - вершина 1 вершина 2
freopen("in.txt","r", stdin);
freopen("out.txt","w", stdout);
int temp;
cin >> temp;// сколько чисел вообще считывать
int *temp_ar = new int [temp];//весь массив смежностей
int *temp_ar_number = new int [temp];//вспомогательный массив для
хранения только позиций (адресов)

49. Программа на C++

for (int i = 0; i < temp; i++) {
temp_ar_number[i] = -1;
}
for(int i = 0; i < temp; i++) {
cin >> temp_ar[i]; // считали из файла массив, где все входные
данные (весь массив смежности)
}
for (int i = 0; i < temp; i++){
temp_ar_number[i] = temp_ar [i]; //массив с адресной частью
if (temp_ar[i] == temp) {
n = i;
break;
}
}
// Определили количество вершин графа (в соответствии с
придуманной и реализованной нами структурой входного
файла)

50. Программа на C++

cout << "\n" <<"Количество вершин n = "<< n << "\n";
Формирование массива смежности
int fict = 1;//фиктивная переменная начало ребра
int k;
for (int i = 0; i < temp; i++){
int numb_begin = temp_ar_number[i]-1;
//взяли первое определяющее число массива
int numb_end = temp_ar_number[i+1]-1;
//взяли второе определяющее число массива
for (int j = numb_begin; j < numb_end; j+=2){
g.push_back(make_pair(temp_ar[j+1], make_pair (fict,
temp_ar[j])));
}
fict++;
if (numb_end == (temp-1)) break;
}

51. Программа на C++

Вывод (печать) массива смежности
cout <<«Список смежности в прямом порядке:\n";
for( int i = 0; i < g.size(); i++ ) {
cout << g[i].second.first<<": (" << g[i].first << ", " <<
g[i].second.second << "); ";
k = i+1;
if(g[i].second.first != g[k].second.first){
cout << "\n";
}
}

52. Программа на C++

Формирование массива смежности
vector < pair < int, pair<int,int> > > g_convert; // обратные списки
смежности
fict = 1;
for (int i = 0; i < temp; i++){
int numb_begin = temp_ar_number[i]-1;//взяли первое
определяющее число массива
int numb_end = temp_ar_number[i+1]-1;//взяли второе
определяющее число массива
for (int j = numb_end; j > numb_begin; j-=2){
g_convert.push_back(make_pair(temp_ar[j-1],
make_pair (fict, temp_ar[j-2])));
}
fict++;
if (numb_end == (temp-1)) break;
}

53. Программа на C++

Вывод массива смежности
cout <<"\nCписок смежности в обратном порядке:\n";
for( int i = 0; i < g_convert.size(); i++) {
cout << g_convert[i].second.first<<": (" <<
g_convert[i].first << ", " << g_convert[i].second.second
<< "); ";
k = i+1;
if( g_convert[i].second.first != g_convert[k].second.first){
cout << "\n";
}
}
}

54. Индивидуальное задание для реализации на уроке (прямо сегодня!!!)

Индивидуальное задание для реализации на уроке (прямо сегодня!!!
Обучающийся
1) рисует взвешенный граф,
2) «вручную» пишет на листке массив смежности (в
прямом и обратном порядках),
3) подписанный листок с нарисованным графом
сдает преподавателю (мне!!!),
4) пишет программу на Java или на Паскале, которая
решает задачу,
5) после проверки правильности ее работы
преподаватель проверяет работоспособность
программы на нескольких графах (скорее всего,
на графах, предложенных одногруппниками),
6) объясняет код и получает «плюсик».

55. Сортировка данных

Сортировка является неотъемлемой частью многих
алгоритмов решения математических задач.
Задача сортировки формулируется следующим
образом:
Дана последовательность из n элементов a1,...,an,
выбранных из множества, на котором задано
отношение линейного порядка.
Требуется найти перестановку
s = (s(l),…,s(n)) индексов, для которой
as(1) ≤ as(2) ≤ ... ≤ as(n),
т.е. расположить элементы данной последовательности
в неубывающем порядке
(или в невозрастающем, т.е. as(1) ≥ as(2) ≥ ... ≥ as(n)).

56. Сортировка данных

При формулировании задачи сортировки в общем виде
информацию о последовательности элементов
можно получать только с помощью операции
сравнения двух элементов.
Пусть а1,...,аn - последовательность сортируемых
элементов.
Не ограничивая общности, можно считать, что элементы
заданной последовательности помещены в
некоторый массив А
Не ограничивая общности, можно считать, что элементы
заданной последовательности помещены в
некоторый массив А в том же порядке,
m.е.
A[i] = ai при i = 1,2,...,n.

57. Сортировка выбором

Алгоритм сортировки выбором
Данные: массив А[1..n].
Результат:
массив А[1..n] такой, что А[1] ≤ А[2] ≤ ... ≤ A[n].
begin
procedure MIN(i):
begin for j = i to n do
if A[i] < A[j] then A[i]↔A[j];
end;
begin
(* главная программа *)
for i := 1 to n-1 do MIN(i);
end;
end.

58. Сортировка выбором

Процедура MIN(i)
выбирает минимальный элемент из
массива аi,...,аn и ставит его на первое место, т.е. на
место ai.
Алгоритм начинает работу с вызова процедуры
MIN(l), которая перемещает
на первое место наименьший элемент исходного
массива.
Далее процедура повторяется для массива
а2,...,аn и т.д.

59. Сортировка выбором

Сортировка выбором имеет вычислительную
сложность O(n2).
Действительно, в процедуре MIN(i) осуществляется
(n-i) операции сравнения и, в худшем случае, (n-i)
операции обмена.
Значит, общее число шагов, выполняемое процедурой
MIN(i) пропорционально (n-i).
Число сравнений в алгоритме
(n - 1) + (n - 2) + ... + 1 = n(n - 1 )/2
Т.е. сложность алгоритма есть O(n2).

60. Сортировка данных

Приведем теорему, позволяющую оценить снизу сложность любого
алгоритма сортировки.
В любом алгоритме, упорядочивающем с помощью сравнений,
на упорядочение последовательности из n элементов
тратится не менее c∙n∙loq n сравнений
при некотором с > 0 и достаточно большом n.
Для доказательства представим алгоритм в виде корневого дерева.
Любой алгоритм, упорядочивающий с помощью сравнений, можно
схематично представить в виде корневого дерева, называемого двоичным
деревом решений.
Это дерево можно рассматривать как блок-схему алгоритма сортировки, в
котором показаны все сравнения элементов и исходы алгоритма.
Вершины дерева (кроме листьев) соответствуют сравнениям элементов, при
этом корень дерева соответствует первому сравнению, осуществляемому
алгоритмом.
Сыновья вершин изображают возможные исходы сравнения отца.
Листья соответствуют исходу алгоритма в зависимости от начальных
значений переменных.

61. Двоичное дерево решений для сортировки трех элементов

62. Сортировка данных

Поскольку, всякое двоичное дерево высоты к имеет не
более 2к листьев, то получаем, что должно
выполняться неравенство 2к > n!,
т.к. листьев в двоичном дереве решений должно быть
не меньше, чем перестановок из n элементов.
Отсюда, k > log n!
Осталось заметить, что при n > 1 справедлива
следующая цепочка неравенств:
n! ≥ n(n - 1 )(n - 2)... () ≥ (n/2)n/2, так что
log n! ≥ log( n/2 )n/2 = n/2 log n/2 ≥ n/4 log n
Итак, k ≥ n/4 log n — полученное неравенство
завершает доказательство теоремы.

63. Алгоритм СОРТДЕРЕВО

Алгоритм сортировки, называемый
СОРТДЕРЕВО, имеет сложность O(n log n).
В разных учебниках он называется: алгоритмом
пирамидальной сортировки, Heapsort или
Treesort.
Определим структуру корневого двоичного
дерева в массиве А[1..n], считая,
что в корне находится элемент А[1],
и элемент A[i] имеет двух сыновей:
A[2i] (если 2i ≤ n) и A[2i+1] (если 2i+1 ≤ n).
Такую структуру назовем двоичным деревом
массива А.

64. Алгоритм СОРТДЕРЕВО

Лемма.
Двоичное дерево массива длины n имеет высоту
logn
Напомним, что высота корневого дерева есть по определению
длина самого длинного пути из корня до какого-нибудь листа.
Например, на рис.3.2 это путь до листа, в котором находится
число 7. Легко видеть, что длина этого пути равна 3.

65. Алгоритм СОРТДЕРЕВО

Пусть k - высота двоичного дерева массива длины n.
Для всех s < k в дереве имеется ровно 2s вершин глубины s.
Пусть h — количество вершин глубины k.
Тогда справедливо неравенство 1 < h < 2k. Поскольку число
вершин равно n — длине массива, то справедливо равенство:
n = 1 + 2 + ... + 2k-1 + h = 2k - 1 + h.
Учитывая, что h ≤ 2k, получаем, что
n = 2k - 1 + h ≤ 2k - 1 + 2k < 2k+1.
Отсюда n < 2k+1. С другой стороны, так как h ≥ 1, то
n= 2k - 1 + h ≥ 2k.
Таким образом, справедливо неравенство 2k ≤ n ≤ 2k+1.
Отсюда, k ≤ logn ≤ k+1, то есть k = logn

66. Алгоритм СОРТДЕРЕВО

Двоичное дерево массива А называется сортирующим деревом
массива А, если выполняются условия:
А[k] ≥ А[2 k] и А[k] ≥ А[2 k +1] для к = l,2,.... n / 2
Непосредственно из определения вытекает, что наибольший
элемент массива находится в корне его сортирующего дерева.
Легко видеть также, что двоичное дерево, изображенное на
представленном выше рис., не является сортирующим.
Именно на представлении массива сортирующим деревом
основан один из теоретически наилучших алгоритмов
сортировки данных — СОРТДЕРЕВО.

67. Алгоритм СОРТДЕРЕВО

На первом этапе двоичное дерево массива А преобразуется в
сортирующее.
Процедуру,
осуществляющую
это
преобразование, будем называть ПСД.
Затем, поскольку по свойству сортирующего дерева,
элемент в корне, а именно, А[1] является наибольшим в А, то,
переставляя А[1] и А[n],
и удаляя А[n] из дерева, получим массив А[1.. n-1] и A[n] = max
А[1..n]. Теперь преобразуем А[1..n-1] в сортирующее дерево,
затем переставим А[1] и А[n-1] и удалим А[n-1]. Процесс
продолжается до тех пор, пока в сортирующем дереве не
останется один элемент. Тогда А[1],...,А[n] — упорядоченная
по неубыванию последовательность.

68. Алгоритм СОРТДЕРЕВО

Перейдем к формальному описанию алгоритма
СОРТДЕРЕВО. Начнем с описания процедуры
ПСД (построение сортирующего дерева). В его
основе
лежит
рекурсивная
процедура
ПЕРЕСЫПК(i,j), имеющая параметры i и j. Они
задают область ячеек массива А, которая в
результате процедуры ПЕРЕСЫПКА будет
обладать свойством сортирующего дерева, при
этом его корень помещается в вершину i.

69. Алгоритм СОРТДЕРЕВО

АЛГОРИТМ 3.2. СОРТДЕРЕВО
1.
Данные: массив элементов А[1..n].
2.
Результат: массив элементов А[1..n], упорядоченный по
неубыванию, то есть А[1] ≤ А[2] ≤ ... ≤ А[n].
3.
begin
4.
ПСД;
(* вначале
строится сортирующее дерево *)
5.
for i := n downto 2 do n / 2
6.
begin
7.
A[l] ↔ A[i];
8.
ПЕРЕСЫПКА( 1,i-1)
9.
end;
10. end

70. Алгоритм СОРТДЕРЕВО

procedure ПСД;
1. begin
2. for i := downto 1 do ПЕРЕСЫПКА(i,n)
3. End
Ниже дано формальное описание процедур
ПЕРЕСЫПКА. Без формального описания
используется функция MAXCЫH(i), значением
которой является тот сын i, который содержит
наибольший из элементов A[2i] и A[2i+1].

71. Алгоритм СОРТДЕРЕВО

procedure ПЕРЕСЫПКА( i ,j);
1. begin
2. if i ≤ then
если i — не лист *)
3. begin k := MAXCЫH(i);
4. if A[i] < A[k] then
5. begin
6. A[i]↔ A[k]; ПЕРЕСЫПКА(k,j)
7. end;
8. end;
9. end;
(*

72. Алгоритм СОРТДЕРЕВО

Разберем пример, иллюстрирующий работу
обеих этих процедур
Пусть задан числовой массив А[1…10]:
I
1 2 3 4 5 6 7 8 9 10
А[I]
2 3 6 1 45 8 0 7 9

73. Алгоритм СОРТДЕРЕВО

74. Алгоритм СОРТДЕРЕВО

Изобразим окончательный результат в
виде таблицы:
I
1 2 3 4 5 6 7 8 9 10
A[I] 9 7 8 2 4 5 6 0 1 3

75. Алгоритм СОРТДЕРЕВО

76. Алгоритм СОРТДЕРЕВО

На рис.3.4 дерево f) является сортирующим
деревом исходного массива А, полученным в
результате работы процедуры ПСД. Затем
происходит перестановка А[1] и А[10]
(дерево g) ). К дереву g) применяется
процедура ПЕРЕСЫПКА(1,9), в результате
которой число 3 проходит путь по правым
ветвям из корня дерева до листа. Затем
вновь происходит перестановка корня с лис
том и т.д. В результате получится массив А,
упорядоченный по возрастанию.

77. Поиск в графе

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

78. Поиск в глубину

Поиск начинается с некоторой
фиксированной вершины v,
называемой корневой вершиной
поиска или корнем. При этом считаем v
просмотренной вершиной. Затем
выбираем какое-нибудь ребро {v,w},
инцидентное v, проходим его и
попадаем в вершину w.

79. Поиск в глубину

Тот факт, что в процессе поиска использовано
именно ребро {v,w} отмечается обычно
следующим образом.
Ребро {v,w} ориентируется из v в w.
Полученную дугу (v,w) считают дугой
корневого дерева с корнем v.
Такое дерево называется ПВГ-деревом с
корнем v, или короче ПВГ(v)—деревом.
При переходе от v к w, вершина v объявляется
отцом вершины w
и обозначается OTEЦ[w], вершина w
объявляется просмотренной, и поиск
продолжается из вершины w.

80. Поиск в глубину

В общем случае, когда мы находимся в
некоторой вершине v, возникают две
возможности:
1) Все вершины, смежные с v, уже
просмотрены. В этом случае
возвращаемся к вершине ОТЕЦ[v] и
продолжаем поиск из нее, а вершину
v с этого момента считаем
использованной.

81. Поиск в глубину

2) Существует еще не просмотренная
вершина w, смежная с вершиной v.
Тогда ребро {v,w} превращаем в дугу
(v,w),
добавляя ее к ПВГ(v)-дереву;
полагаем ОТЕЦ[w]=v;
проходим по дуге из v в w и продолжаем
поиск из w.

82. Поиск в глубину

Поиск в глубину завершается тогда, когда все
вершины графа будут просмотрены. Здесь
возможны две ситуации:
1) Корневая вершина использована (т.е. все смежные с
ней вершины просмотрены), однако в графе еще
есть не просмотренные вершины. В этом случае
выбираем произвольную не просмотренную
вершину, объявляем ее корнем и вновь начинаем
поиск уже из этой вершины. Такая ситуация
возникает только в случае несвязного графа.
2) Корневая вершина и все другие использованы.
Поиск на этом заканчивается.

83. Поиск в глубину

Представим формальное описание изложенного алгоритма поиска в глубину, основанную на
рекурсивной процедуре ПВГ(v) — поиск в глубину из вершины v. В рассматриваемом
алгоритме связность графа не предполагается.
АЛГОРИТМ Поиск в глубину.1
Данные: неориентированный граф G=(V,E), заданный списками смежностей ЗАПИСЬ[v].
Результаты: массив ОТЕЦ, множество Т.
1.
procedure ПВГ (v);
(*поиск в глубину с корнем v)
2.
begin METKA[v]:=l;
3.
for w ЗАПИСЬ[v] do
4.
if METKA[w]=0 then
5.
begin OTEЦ[w]:=v; T:=T{(v,w)}; ПВГ(w);
6.
end;
7.
end;
8.
begin
(*Главная программа)
T := Ø;
9.
for v V do METKA[v]:=0;
(*инициализация)
10.
for v V do
11.
if METKA[v]=0 then
12.
begin OTEЦ[v]:=nil; ПВГ(v);
13.
end;
14.
end.

84. Поиск в глубину

Примечание.
Массив МЕТКА, используемый в алгоритме
имеет по одному элементу для каждой
вершины графа и служит указателем на то,
что просмотрена или нет данная вершина.
Считаем, что METKA[v]=0, если v не
просмотрена, и METKA[v]=1 в противном
случае.
Массив ОТЕЦ описан ранее. Понятно, что он
имеет длину n, где n — число вершин в
графе.
В множестве Т будем хранить дуги ПВГдеревьев.

85. Поиск в глубину

На следующем рис. показано,
как
поиск
в
глубину
исследует
неориентированный
граф
G.
Предполагается, что в списках
смежности этого графа вершины
встречаются в порядке возрастания
номеров, и, что цикл в строках 11-14
алгоритма Поиск в глубину.1 выполнялся
в порядке возрастания номеров
вершин.

86. Поиск в глубину

87. Поиск в глубину

В просмотренном графе G дуги
ПВГ-деревьев
обозначены
стрелками
в
соответствии с ориентацией, полученной в
ходе поиска.
Такие дуги часто называют прямыми дугами
поиска. Прочие ребра графа, называемые
иногда
обратными
дугами
поиска,
обозначены на рисунке пунктирами.
Числа в скобках, стоящие у вершин
просмотренного
графа,
соответствуют
очередности,
в
которой
они
просматривались в ходе поиска.
Отметим, что вершины с номерами 1, 9 и 11
являются корнями ПВГ-деревьев.

88. Поиск в глубину

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

89. Поиск в глубину

Для организации такого процесса понадобится
дополнительно массив указателей
УКАЗ длины n, где n=|V|.
Предполагается,
что
в
начале
работы
процедуры поиска выполняются равенства
УKA3[v]=HAЧAЛO[v], для всех v из V, иначе
говоря, УКАЗ[v] дает адрес первой записи в
списке ЗАПИСЬ[v].
В процессе работы процедуры поиска УКАЗ[v]
меняется таким образом, что указывает на
следующую запись в списке ЗАПИСЬ[v]
после той, которая содержит последнюю
просмотренную из нее вершину.

90. Поиск в глубину

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
procedure ПВГ1(v);
(* нерекурсивная версия *)
begin
СТЕК :=Ø; СТЕК v; METKA[v]:=l;
while СТЕК ≠ Ø do
begin u СТЕК;
while (УКАЗ[u] ≠ nil) and (МЕТКА[УКАЗ[u]^.строка]=1) do
УКАЗ[u] := УКАЗ[u]^.след;
if УКАЗ[u] ≠ nil then
(*найдена непросмотренная вершина *)
begin w := УКАЗ[u]^.строка:
СТЕК w; OTEЦ[w]:=u; METKA[w]:=l;
T := T(u,w); УКАЗ[u]:= УКАЗ[u]^.след;
end;
else СТЕК
(* вершина u использована *)
end;
end.

91. Поиск в глубину

Теорема.
Сложность алгоритма
Поиск в глубину 1
есть O(n+m).
Следствие.
Связные компоненты неориентированного
графа могут быть найдены за время
O(n+m).

92. Поиск в глубину

Поиск в глубину в ориентированном графе
отличается от поиска в неориентированном
графе только тем, что ребра проходятся в
соответствии с их ориентацией.
Поскольку в главе 2 мы условились считать, что в
списке ЗАПИСЬ[у] встречаются только те
вершины w,
для которых (v,w)
E,
то алгоритм Поиск в глубину1 корректно работает и
в ориентированных графах.

93. Поиск в ширину

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

94. Поиск в ширину

Затем проходим все ребра {v,w}, инцидентные v, в
каком-нибудь порядке и ориентируем их из v в
w.
Вершины w, смежные с v, считаем просмотренными
и размещаем их в порядке просмотра ребер в
очередь.
Для всех таких вершин w полагаем
OTEЦ [w]:=v и говорим, что w просмотрена из v.
Ориентированные ребра (v,w) будем называть
ребрами ПВШ(v)-дерева.
Говорят часто, что все такие вершины w образуют
первый фронт распространения волны.
Вершина v после этих действий считается
использованной и удаляется из очереди.

95. Поиск в ширину

Дальнейший
поиск
продолжается
следующим
образом.
Берем
очередную вершину v из очереди,
проходим по всем ребрам, ин
цидентным v, которые соединяют
вершину
v
с
еще
непросмотренными вершинами w.
Все такие вершины w объявляются
просмотренными, для них
полагают OTEЦ[w]:=v, ребра (v,w)
относят к ПВШ(v)-дереву.

96. Поиск в ширину

После этих действий вершина v считается
использованной и удаляется из очереди.
Говорят
также,
что
вершины,
просмотренные
из
вершин,
принадлежащих фронту с номером k,
образуют (k+1)-ый фронт распространения
волны.
Завершается поиск в ширину с корнем в
заданной вершине таким же образом, как и
поиск в глубину, а именно тогда, когда ни
одной новой вершины просмотреть не
удается.

97. Поиск в ширину

На следующем рисунке (2) показано, как
поиск в ширину исследует граф G,
изображенный ранее на рис. (1).
Дуги
ПВШ-деревьев
изображены
стрелками
в
соответствии
с
ориентацией, полученной в ходе
поиска. Прочие ребра исходного графа
изображены пунктиром.
Предполагалось, что вершины в ходе
поиска просматривались в порядке
возрастания их номеров.

98. Поиск в ширину

99. Поиск в ширину

Отметим, что в ПВШ(1) - дереве поиска
вершины 2, 3, 4 образуют первый
фронт
распространения
волны,
вершины 5, 6 и 7 — второй, а вершина
8 — третий.

100. Поиск в ширину

Отметим, что в ПВШ(1) –
дереве поиска вершины 2, 3, 4 образуют первый
фронт распространения волны,
вершины 5, 6 и 7 — второй,
а вершина 8 — третий.
Далее представлен
АЛГОРИТМ 4.2. ПОИСК В ШИРИНУ
Данные: неориентированный граф G=(V,E),
заданный списками смежностей.
Результаты: массив ОТЕЦ, множество D.

101. Поиск в ширину

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
procedure ПВШ(v);
(* поиск в ширину с корнем v *)
begin ОЧЕРЕДЬ :=Ø; ОЧЕРЕДЬ v; METKA[v]:=1;
while ОЧЕРЕДЬ ≠Ø do
begin u ОЧЕРЕДЬ; ОЧЕРЕДЬ;
for w ЗАПИСЬ[u] do
(* используем вершину u *)
if METKA[w]=0 then
begin ОЧЕРЕДЬ w; OTEЦ[w]:=u; METKA[w]:=1;
D=Du{(u,w)};
end;
end;
end;
begin
(*главная программа*)
D:=Ø; for vV do METKA[v]:=0;
(* инициализация *)
for v V do
if METKA[v]=0 then
(*v – корень*)
begin OTEЦ([v]:=nil; ПВШ(v);
end;
end.

102. Поиск в ширину

В приведенном формальном описании
алгоритма поиска в ширину переменная
МЕТКА имеет тот же смысл, что и ранее в
алгоритме Поиск в глубину 1.
Дуги ПВШ-деревьев хранятся в множестве D.
Смысл переменной ОТЕЦ объяснен выше.
Просмотренные вершины помещаются в
ОЧЕРЕДЬ и удаляются оттуда сразу после
их использования (строка 4 алгоритма).

103. Поиск в ширину

В алгоритме Поиск в ширину 2 связность
графа не предполагается. Для корневых
вершин поиска и только для них
выполняется равенство ОТЕЦ[v]=nil.
Теорема 4.2. Алгоритм ПОИСК В
ШИРИНУ 2 имеет вычислительную
сложность O(n+m).

104. Цепи и пути в графах

Применительно
к
только
связным
неориентированным графам нетрудно
проверить, что и ПВГ-дерево, и ПВШдерево
действительно
являются
деревьями, и более того — корневыми
деревьями, причем корнями этих
деревьев являются те вершины, с
которых начинался поиск
(собственно поэтому они и в ПВГ и в ПВШ
названы корневыми вершинами).

105. Цепи и пути в графах

Если в ориентированном графе имеется дуга
(v,w), то v — отец w, a w — сын v. Легко
видеть,
что
даваемые
алгоритмами
ПоискВглубину1 и ПоискВширину2 значения
переменных ОТЕЦ[w] согласуются с ранее
введенным понятием, а именно, если
v=ОТЕЦ[w], то (v,w)E.
Вершина v называется предком вершины w, и,
соответственно, w — потомком v, если в
корневом дереве существует путь от v до w.
Например, в корневом дереве ПВШ(1)
из рис. вершина 8 является потомком вершины
2.

106. Цепи и пути в графах

Теорема 3. Пусть Т — ПВГ-дерево связного
неориентированного графа G=(V,E), и пусть
{u,w}E. Тогда либо u — потомок w, либо w
потомок u в корневом дереве Т.
Понятно, что ПВШ-дерево не обладает
свойством, сформулированным в теореме3.
Например, в ПВШ(1)-дереве, изображенном на
рис. 2, ни вершина 3 не является потомком
вершины 6, ни вершина 6 не является
потомком вершины 3
(говорят, что такие вершины несравнимы в
корневом дереве).

107. Цепи и пути в графах

Как в ПВГ-дереве, так и в ПВШ-дереве для
каждой вершины w,
существует единственный путь из корня v в w.
Как построить этот путь?
Это несложно делается с помощью массива
ОТЕЦ.
Отметим только, что под путем в орграфе мы
договорились понимать в зависимости от
степени удобства,
либо
последовательность
ребер,
либо
последовательность вершин.

108. Цепи и пути в графах

В
предлагаемом
ниже
алгоритме
ПостроениеПути3 требуемый путь
идентифицируется
последовательностью
вершин.
Предполагается, что перед работой
этого
алгоритма
работала
либо
процедура ПВГ(v), либо процедура
ПВШ(v).

109. Цепи и пути в графах

АЛГОРИТМ ПостроениеПути3.
Данные: корневая вершина поиска v, вершина
w. массив ОТЕЦ.
1. begin
2. СТЕК:=Ø; СТЕК w; u:=w;
3. while u≠v do
4. begin u:=ОТЕЦ[u];
5. CTEK u;
6. end;
7. end.
Результат: СТЕК, содержащий
последовательность вершин, образующих vw-путь.

110. Цепи и пути в графах

Понятно, что последовательность вершин
v=v0,v1,...,vk=w, полученная считыванием
СТЕКА, образует как v-w-путь в корневом
дереве Т (или D), так и v-w-цепь в исходном
графе G.
Оказывается, что пути, построенные поиском в
ширину, обладают очень полезным свойством,
а именно, справедлива.
Теорема 4. Пусть D — ПВШ-дерево с корнем v
связного неориентированного графа G=(V,E).
Тогда для любой вершины w
V единственный
v-w-путь в D определяет кратчайшую по числу
ребер цепь среди всех v-w-цепей в графе G.

111. Цепи и пути в графах

Заметим, что пути, определяемые поиском в
глубину, вообще говоря, не являются
кратчайшими. Например, на рис.1 путь от
вершины 1 до вершины 8 проходит через
вершины 2,3,4,7,6 и имеет длину 6, а поиск в
ширину
(см.рис.2)
определяет
путь,
проходящий через вершины 4,7, длиной 3.