52

10.Алгоритмы на графах

Вид занятия – лабораторная работа Цель – исследование и практическая реализация алгоритмов на графах

Продолжительность – 4 часа

Алгоритмы обхода в глубину и по уровням

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

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

Рисунок 10.1. – Иллюстрация алгоритма обхода в глубину

Алгоритм обхода по уровням работает следующим образом (см. рис.10.2):

−При обходе графа по уровням мы, после посещения первого узла, посещаем все соседние с ним вершины.

−При втором проходе посещаются все вершины на расстоянии двух ребер от начальной.

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

Рисунок 10.2 – Иллюстрация алгоритма обхода по уровням

Построение минимального остовного дерева

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

В конце 1950-х годов Эдгар Дейкстра и Прим, работая и публикуя свои результаты независимо друг от друга, предложили следующий алгоритм построения МОД. Разобьем вершины графа на три класса:

1.вершины, вошедшие в уже построенную часть дерева;

2.вершины, окаймляющие построенную часть;

53

3. еще не рассмотренные вершины.

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

Рисунок 10.3. – Алгоритм построения МОД Дейкстры-Прима

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

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

На рисунке 10.4 представлены шаги алгоритма Крускала создающего МОД для тех же исходных данных, что и в предыдущем примере.

Рисунок 10.4. – Иллюстрация алгоритма Крускала

Поиск кратчайшего пути

Результатом алгоритма поиска кратчайшего пути является последовательность ребер, соединяющая две заданные вершины и имеющая наименьшую длину среди всех таких последовательностей. Если изменить рассмотренный ранее алгоритм Дейкстры-Прима построения МОД так, чтобы при выборе ребра, ведущего в кайму, он выбирал ребро, являющееся частью кратчайшего в целом пути из начальной вершины, то мы получим требуемый результат. На этой идее и основан алгоритм Дейкстры.

54

Допустим, что нам требуется построить кратчайший путь из вершины A в вершину G (см. рис. 10.5).

Рисунок 10.5. – Иллюстрация алгоритма Декстры при прокладке кратчайшего пути из A в G

На каждой итерации алгоритма Дейкстры в кайму добавляется ребро с наименьшим весом относительно стартовой вершины. Так как наш алгоритм начинает работать из вершины A, то на первом шаге в кайму добавляется ребро соединяющее узел А c узлом B, так как вес ребра самый малый. На втором шаге мы анализируем веса рёбер исходящих уже из двух этих вершин. “Победителем” становится ребро с весом 4, оно соединяет вершины A и C. Ребро B-E будет добавлено в кайму только на третьем этапе, заметьте, что при включении этого ребра в кайму следует учитывать суммарный вес пути A-B-E=2+3=5.

Задание

Для выполнения заданий воспользуйтесь программой хранения информации об ориентированном графе, разработанной на лабораторной работе на тему “Нелинейные структуры данных”.

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

2.Используя алгоритмы Дейкстры-Прима и Крускала разработайте процедуры строящие МОД произвольного графа.

3.Реализуйте алгоритм поиска кратчайшего пути в графе.