Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр 7

В этой прграмме стек реализуется с помощью рекурсии. Рассмотрим порядок нахождения путей на примере. Пусть имеется граф (......)

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

• 1;

• 1,3;

• 1,3,2;

• 1,3,2,4;

• 1,3,2;

• 1,3,2,5;

• 1,3,2,5,4;

• 1,3,2,5;

• 1,3,2;

• 1,3,4;

• 1,3;

• 1,3,6;

• 1,3;

• 1;

• 1,4;

• 1;

• .

Последовательность обхода вершин графа можно представить деревом (......)

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

4.4. Поиск путей на графе в ширину

При поиске в глубину короткие по числу звеньев пути могут находиться далеко не в первую очередь. Так самым коротким в рассмотренном примере является прямой путь из 1 в 4, но этот путь находится последним.

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

• 1,4;

• 1,3,4;

• 1,3,2,4;

• 1,3,2,5,4.

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

4.5. Алгоритмы поиска кратчайших путей Дейкстры и Флойда

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

Рассмотрим два алгоритма поиска кратчайших путей между вершинами: Дейкстры и Флойда. Будем считать, что длина дуги из вершины V_i в вершину V_j задана элементом матрицы a_ij, причем a_ii=0 и a_ij =, если дуга из вершины V_i в вершину V_j отсутствует.

В алгоритме Дейкстры находится кратчайший путь из вершины S в вершину T. Вершинам присваиваются временные и окончательные метки, которые будем обозначать соответственно буквами C и D с индексами вершин.

1. Вершине S присваивается окончательная метка 0, то есть C_s:=0, временным меткам остальных вершин – значение .

2. Пусть i – номер последней вершины, которой присвоена окончательная метка C_i. Каждой вершине j, имеющей временную метку D_j, присваивается новая временная метка по правилу D_j:=min(C_i+a_ij , D_j). Если значение D_j меняется, то вместе с ним сохраняется номер предыдущей вершины i.

3. Наименьшая из временных меток объявляется окончательной. Пусть k – номер этой вершины. Следовательно, C_k:=D_k. Если вершина T не получила окончательной метки, то i:=k и переход к 2.

4. Конец.

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

Пусть имеется следующий граф.(.....)

Требуется найти кратчайший путь из вершины A в вершину C.

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

№ шага	A	B	C	D
1	0			
2	0	1(A)		2(A)
3	0	1(A)		2(A)
4	0	1(A)	4(B)	2(A)
5	0	1(A)	4(B)	2A)
6	0	1(A)	3(D)	2(A)
7	0	1(A)	3(D)	2(A)

Итак, длина кратчайшего пути равна 3. Окончательная метка 3 для вершины C получена из предыдущей вершины D. В свою очередь окончательная метка 2 для вершины D получена из вершины A. Следовательно, кратчайший путь составляют вершины A, D, C.

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

Здесь кратчайший путь из A в C проходит через вершину B и равен -1, тогда как по алгоритму Дейкстры вершина C сразу получит окончательную метку 1.

Трудоемкость алгоритма Дейкстры пропорциональна величине N ², где N – количество вершин графа.

Алгоритм Флойда определяет кратчайшие пути между всеми парами вершин. Снова будем считать, что длина дуги из вершины V_i в вершину V_j задана элементом матрицы a_ij, причем a_ii=0 и a_ij =, если дуга из вершины V_i в вершину V_j отсутствует.

Пусть элемент a_ij^(k) матрицы A^(k) равен длине кратчайшего пути из вершины V_i в вершину V_j, с номерами промежуточных вершин, не превосходящими k. Тогда выполняется рекуррентное соотношение

(*)

Действительно, кратчайший путь из V_i в V_j с номерами промежуточных вершин, не превосходящими k+1, может не проходить через вершину V_k+1 . В противном случае он представляет собой кратчайший путь из V_i в V_k+1, а затем из V_k+1 в V_j.

В качестве A⁽⁰⁾ выбирается исходная матрица A. Матрица A⁽ⁿ⁾ даст длины кратчайших путей между всеми парами вершин без каких-либо ограничений на промежуточные вершины. Значение a_ij⁽ⁿ⁾ =  означает отсутствие пути из вершины V_i в вершину V_j.

Параллельно с описанными матрицами строится последовательность матриц B⁽ⁱ⁾ для нахождения самих кратчайших путей. Элемент b_ij^(k) матрицы B^(k) устанавливается равным номеру второй вершины на кратчайшем пути из V_i в V_j с номерами промежуточных вершин, не превосходящими k, и 0 в случае отсутствия путей. Элемент b_ij^(k+1) не меняется, если в формуле (*) минимум достигается на первом значении, и полагается равным b_ik+1^(k), если минимально второе выражение, так как в этом случае кратчайший путь проходит через вершину V_k+1.

Первоначально b_ij⁽⁰⁾ матрицы B⁽⁰⁾ полагается равным j, если есть дуга из V_i в V_j, и 0, если такая дуга отсутствует. Матрица B⁽ⁿ⁾ позволяет восстановить кратчайший путь между любыми двумя вершинами. Действительно, если s=b_ij⁽ⁿ⁾ дает вторую вершину на кратчайшем пути из V_i в V_j, то t=b_sj⁽ⁿ⁾ даст третью вершину, w=b_tj⁽ⁿ⁾ - четвертую и так далее до попадания в вершину V_j. Значение b_ij⁽ⁿ⁾ =0 означает отсутствие пути из вершины V_i в вершину V_j.

Рассмотрим в качестве примера следующий граф, в котором вершины идентифицированы номерами (.....)

3

1

1

2

Для него матрицы A⁽⁰⁾ и B⁽⁰⁾ имеют соответственно вид

4.6. Остовные деревья

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

Здесь рассматриваются свободные (бескорневые) деревья, в которых корнем можно считать любую вершину.

Ряд практических задач связан с нахождением остовных деревьев. Например, множество населенных пунктов требуется связать между собой дорогами, телефонной связью, водопроводом и т. п. Если в графе заданы стоимости ребер, то встает естественная задача нахождения остовного дерева с минимальной суммарной стоимостью ребер. Наиболее распространены два алгоритма нахождения остовных деревьев: Прима и Крускала [4, 14].

Алгоритм Прима начинает построение минимального остовного дерева U с включения в него произвольной вершины u. Далее находится ребро (u, v) минимальной стоимости, связывающее множество вершин U с вершинами, не входящими в U. Вершина v и ребро (u, v) включаются в U. Процесс продолжается, пока в U не войдут все вершины графа.

Рассмотрим для примера следующий граф.(.....)

Пусть выбрана начальная вершина 1. В остовное дерева будут последовательно добавляться вершина 3 и ребро (1, 3), вершина 6 и ребро (3, 6), вершина 4 и ребро (6, 4), вершина 2 и ребро (3, 2), вершина 5 и ребро (2, 5). Получим следующее минимальное остовное дерево (.....)

Трудоемкость алгоритма Прима пропорциональна N², где N – число вершин графа.