Модификации алгоритмов

С помощью алгоритмов поиска в глубину и в ширину легко решаются следующие задачи:

1. Определение числа связных компонент графа.

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

2. Поиск маршрута (пути) между двумя фиксированными вершинами u и v и определение его длины.

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

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

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

3. Построение остова графа.

Напомним, что остовом называется остовный подграф, являющийся деревом. Такой подграф можно построить с помощью алгоритма поиска любого вида. Для этого во время поиска параллельно строится новый граф: если найдена новая еще непомеченная вершина u в списке инцидентности вершины v, то ребро (v,u) добавляется в строящийся граф. Если исходный граф - несвязный, то задача не имеет решения. Для связного исходного графа получим, что построенный граф является связным, так как новые ребра достраиваются к уже просмотреннымвершинам, которые между собой связаны. Этот граф не содержит циклов, так как в него не добавляется ребро оба конца которого просмотрены, то есть связаны маршрутом. Следовательно, построенный граф является деревом.

Задание для самостоятельной работы.

I. Написать и отладить программу в соответствии с вариантом задания №2 (см. приложение). Содержание программы аналогично заданию п.1.

II. Продемонстрировать работу программы на контрольном примере.

III. Текст программы, граф и исходный файл контрольного примера, результаты работы программы оформить в отчет.

Дата добавления: 2015-06-27