Графы

Шаг 1. Выбрать начальный узел

Шаг 2. Сформировать начальную кайму, состоящую из вершин, соседних с начальным узлом

Шаг 3. В графе есть вершины, не попавшие в дерево?

Если да, то переход на Шаг 4.

Иначе – переход на Шаг 9.

Шаг 4. Выбрать ребро из дерева в кайму с наименьшим весом

Шаг 5. Добавить конец ребра к дереву

Шаг 6. Изменить кайму, для чего добавить в кайму вершины, соседние с новой

Шаг 7. Обновить список ребер из дерева в кайму так, чтобы он состоял из ребер наименьшего веса

Шаг 8. Переход на Шаг 3

Шаг 9. Конец

На Рис.  3.6 изображен исходный граф:

Рис.  3.6. Исходный граф

Рис.  3.7. Добавление первой вершины. Пунктиры ведут к вершинам каймы

Рис.  3.8. Добавление второй и третьей вершин

Рис.  3.9. Добавление четвертой и пятой вершин

Рис.  3.10. Заключительные шаги алгоритма Дейкстры-Прима

2. Алгоритм Крускала

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

1. Отсортировать ребра в порядке возрастания весов

2. Инициализировать структуру разбиений

edgeCount=l

while edgeCount<=E and includedCount<=N-l do

parentl=FindRoot(edge[edgeCount].start)

parent2=FindRoot(edge[edgeCount].end)

if parentl/=parent2 then

добавить edge[edgeCount] в остовное дерево

includedCount=includedCount+l

Union(parent1,parent2)

end if

edgeCount=edgeCount+l

end while

 

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

Рис.  3.11. Добавление первого ребра

Рис.  3.12. Добавление второго и третьего ребра

Рис.  3.13. Добавление четвертого и пятого ребер

Рис.  3.14. Заключительные шаги алгоритма Крускала

3. Алгоритмы поиска кратчайшего пути

1. Алгоритм Дейкстры

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

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

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

Шаг 1. Выбрать начальную вершину

Шаг 2. Создать начальную кайму из вершин, соединенных с начальной

Шаг 3. Вершина назначения не достигнута?

Если нет, то переход на Шаг 4.

Иначе – переход на Шаг 9

Шаг 4. Выбрать вершину каймы с кратчайшим расстоянием до начальной

Шаг 5. Добавить эту вершину и ведущее в нее ребро к дереву

Шаг 6. Изменить кайму путем добавления к ней вершин, соединенных с вновь добавленной

Шаг 7. Для всякой вершины каймы выполнить: приписать к ней ребро, соединяющее ее с деревом и завершающее кратчайший путь к начальной вершине

Шаг 8. Переход на Шаг 3

Шаг 9. Конец

Проиллюстрируем алгоритм на примере графа, приведенного на Рис.  3.6. Будем искать кратчайший путь от вершины A к вершине G.

Рис.  3.15. Начальная вершина

 

 

Рис.  3.16. Добавление второй и третьей вершин

Рис.  3.17. Добавление четвертой и пятой вершин

Рис.  3.18. Заключительные шаги алгоритма Дейкстры