Программная реализация алгоритмов поиска в глубину и ширину в неориентированных графах

8) Процедура VGlubiny организует поиск в глубину в неорграфе: вызывается процедура ishodnaja (переход к пункту 9 с последующим возвращением к пункту 8). В цикле рассматриваемой вершиной i, становится вершина, находящаяся в последнем элементе стека c, в цикле на основе заполнения матрицы а ищутся новые (непросмотренные) смежные с i-той j-тые вершины: если аij=1 и bj=l (т.е. i-тая вершина смежна

с j-той, и j-тая вершина – новая), то на экран выводится пояснение к процессу поиска, вершина «старится» и помещается в последний элемент стека сь номер 1 которого до этого увеличивается на 1, счетчик р засчитывает найденную вершину, осуществляется переход к началу внешнего цикла (из стека извлекается вершина для рассмотрения). Если же не были найдены новые смежные вершины, то внутренний цикл завершается, а во внешнем номер позиции стека уменьшается на 1; выводится сообщение об исчерпанности вершины. Внешний цикл извлекает из стека предыдущую вершину, и процесс поиска новых смежных вершин повторяется до тех пор, пока исходная вершина не исчерпается. Затем выводится сообщение об окончании поиска в глубину, при этом если новых смежных вершин, кроме исходной, не оказалось, то выдается сообщение об изолированности вершины. (Переход к пункту 10).

9) Процедура ishodnaja организует ввод индекса исходной вершины, с которой следует начать поиск, и проверку правильности ввода (в цикле. Предлагается ввести индекс вершины i. Если он не принадлежит промежутку [1; n] или bi=0, т.е. эта вершина была просмотрена (для случая вторичного поиска), то выдается сообщение об ошибке ввода и цикл продолжает работу); выводит пояснение касательно процесса поиска и номер вершины, с которой начинается поиск; «старит» вершину, т.е. делает ее найденной; присваивает номеру последней позиции 1 очереди / стека значение 1; помещает индекс найденной исходной вершины в стек / очередь с; присваивает счетчику найденных вершин р значение 1. (Возврат к пункту 7 или 8, в зависимости от выбранного варианта поиска).

10) После завершения поиска в глубину или ширину вызывается процедура vtorichnaja. Если n не равно р и m не равно р (т.е. общее число вершин и число не достижимых вершин отличаются от количества найденных, то процедура продолжает работу, иначе происходит выход из нее (переход к пункту 5). Процедура vtorichnaja после сравнения обнуляет счетчик недостижимых вершин m; с помощью цикла очищается стек / очередь с (заполняет его нулями), и ищет не просмотренные вершины в массиве b (если находит, то выдает соответствующее сообщение, а счетчик m засчитывает не просмотренную, следовательно, недостижимую вершину). Циклом, если недостижимые вершины найдены (m не равно 0), на экран выводится «подменю». (Пункты «подменю»: вторичный поиск в ширину, вторичный поиск в глубину, выход в основное меню). С клавиатуры считывается символ, соответствующий пункту подменю, и, в зависимости от сделанного выбора, в первом случае вызывается процедура VShiriny (переход к пункту 7, а от него к пункту 10), во втором – процедура VGlubiny (переход к пункту 8, а от него к пункту 10), а в третьем осуществляется выход из процедуры vtorichnaja в основное меню. (Переход к пункту 5). Если была нажата иная клавиша, цикл продолжает работу.

На рисунке 4 представлена структурная схема алгоритма программы.

Рисунок 4 – Структурная схема программы

2.2 Описание диалога с пользователем

Программа начинает свою работу после запуска файла KURSYAK.exe. Когда программа загрузится, на экране ЭВМ появится меню, в котором программа простит задать целое количество вершин, как показано на рисунке 5.

Рисунок 5 – Ввод количества вершин

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

Рисунок 6 – Заполнение матрицы достижимости

После мы с клавиатуры заполняем матрицу достижимости. Когда матрица заполнена, программы выдаёт меню, в котором просит выбрать метод решения поставленной задачи. Где кнопкой S – осущёствляется решение методом поиска в ширину. G – Осуществляет решение методом поиска в глубину. N – Изменение матрицы смежности, а V – выход из программы. Как показано на рисунке 7.

Рисунок 7 – Выбор метода решения

После нажатия кнопки S начинается поиск в ширину. Программа запрашивает, с какой вершины начать поиск. Это показано на рисунке 8.

Рисунок 8 – Запрос начальной вершины, для поиска в ширину

В данном случае мы выбираем вершину 5. После чего программа выдаёт нам результат, который показан на рисунке 9. И снова выводит меню, которое было показано на рисунке 8.

Рисунок 9 – Вывод результата методом поиска в ширину

Дальше мы выбираем метод поиска в глубину и делаем это нажав кнопку G.

После чего программа спрашивает начальную вершину поиска в глубину. Это показано на рисунке 10.

Рисунок 10 – Запрос начальной вершины, для поиска в глубину

В данном случае мы выбираем вершину 3. После чего программа выдаёт нам результат метода поиска в глубину. Как показано на рисунке 11.

Рисунок 11 – Вывод результата методом поиска в глубину

После чего на экране ЭВМ появляется основное меню программы (Рисунок 7 – выбор метода решения). Нажав кнопки N и V программа осуществит: операция по замене матрицы достижимости (Рисунок 6 – заполнение матрицы достижимости.) и выход из программы соответственно.

2.3 Контрольный пример

Дан граф G, изображенный на рисунке 12. Построить остов графа поиском в глубину и поиском в ширину.

Рисунок 12 – Данный граф

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

Начинаем поиск с любой вершины, допустим, с х1. Выбираем вершину, смежную с х1, например х2. Вершины х1, и х2 соединяем ребром Далее выбираем вершину х3 смежную с х2. Вершины х2 и х3 соединяем ребром. Продолжая двигаться дальше, соединяем вершины х3 и х4. У вершины х4 три смежных вершины – x5, x7 и х8. Дня продолжения поиски можно выбрить любую из них, например x5. Соединяем ребром вершины х5 и x6, а затем x6 и x7. Попав в вершину x7, видим, что смежной с ней является вершина x4. Но продолжай, поиск в данном направлении нельзя, так как вершина x4, не является новой и при соединении вершин x7 и х4 граф уже не будет остовом (будет иметь цикл). Согласно алгоритму возвращаемся в предыдущую вершину, то есть в x6. Так как у x6 нет новых вершин, то но вращаемся в вершину x5. Аналогично из x5 переходим в вершину x4. Вершима x8 является новой (еще не просмотренной смежном вершиной) для х4, поэтому, согласно алгоритму, выбираем вершину х8 и соединяем вершины х4 и х8 ребром, затем соединяем х8 и х9. У х9 нет новых вершин, кроме х1, но соединить эти вершины мы не можем, тан как граф тогда не будет остовом. Мы просмотрели все вершины графа G. Возвращаемся в вершину х1. Найденный остов графа G представлен на рис. 5 а.

 Скачать реферат