Реализация алгоритма без вычислительной системы
Рис. 1. Пример демонстрации обхода графа в глубину
Пример рекурсивных вызовов для графа при реализации процесса поиска в глубину:
1 – начало обхода
Итак, искомый порядок обхода в глубину: 1, 0, 9, 8, 5, 2, 6, 7, 3, 4.
На рис. 1 каждая вновь найденная и непосещенная вершина, выводимая в список обхода и помещаемая в стек, записана в начале каждой строки. В строках со смещением вправо показаны найденные смежные вершины при переходе вглубь графа. Возврат к ранее посещенным вершинам, если смежных и непосещенных вершин с текущей вершиной поиска не найдено, показан смещением на шаг влево.
Поиск в глубину подобен обследованию лабиринта, когда от каждой развилки-вершины путь углубляется и обследуется каждый следующий коридор, возвращаясь назад, только если встречается тупик или ранее обследованный коридор.
Динамика процесса поиска наглядно представляется деревом рекурсивных вызовов (лесом поиска для случая несвязного графа).
Рис. 2 Дерево поиска в глубину DFS для графа,
изображенного на рис. 1
Хранение порядка обхода вершин в дереве DFS обеспечивается стеком.
Рис. 3 Состояние Стека для вершин графа рис.1 до первого рекурсивного возврата
Рассмотрим представление структуры данных Стек. Принцип работы Стека соответствует «первым пришел, последним обслужен» (LIFO queue – Last In First Out). Добавление новых вершин в стек и извлечение вершин из стека возможно только с одного конца – вершины Стека. Стек может хранить информацию о посещенных вершинах или о ребрах, которые соединяют посещенные вершины с непосещенными.
Реализация алгоритма на вычислительной системе (с помощью системы программирования TurboPascal)
Рассмотрим процедуры рекурсивной и нерекурсивной реализации DFS.
Граф представлен матрицей смежности C[i, j], каждый элемент которой индексирован номерами вершин и содержит значение C[i, j] = 1 для смежных вершин i и j , C[i ,j] = 0 для несмежных вершин.
Нерекурсивная реализация процедуры поиска использует структуру данных Стек. Рекурсивная реализации использует встроенные возможности системы программирования - использование стековой памяти для хранения рекурсивных вызовов и возвратов.
Для представления Стека в TurboPascal используем одномерный массив Stek[i], обеспечивающий хранение элементов в порядке их поступления и извлечение этих же элементов в обратном порядке. Вершину Стека запомним в переменной Uk – указатель вершины Стека. Стек поддерживает операции добавления элемента в стек (setStek), извлечения элемента из вершины стека (getStek), инициализации стека (initStek). Запишем программную реализацию этих процедур.
Procedure setStek(v: integer);
Begin
Inc(Uk); Stek[Uk]:=v;
End;
Procedure getStek( var v: integer);
Begin
v:= Stek[Uk]; Dec(Uk);
End;
Procedure initStek;
Begin
Uk:=0;
End;
Посещенные и добавленные в стек вершины отметим специальной меткой, в случае повторного нахождения данной отмеченной вершины как смежной с некоторой текущей вершиной поиска, отмеченную вершину не будем включать в стек повторно. Таким образом, размер стека ограничивается количеством вершин графа. Отмеченные вершины будем хранить в массиве Visit [i], индекс массива соответствует номеру вершины, а элемент – метка (например, true – непосещенные вершины, false – отмечены как посещенные)
program Poisk_v_glubinu;
const n=9; {количество вершин графа}
C: array [0..n,0..n] of 0..1=((0,1,0,0,0,0,0,0,0,1),
(1,0,1,1,1,0,0,0,0,0),
(0,1,0,0,0,1,0,0,0,0),
(0,1,0,0,1,0,0,0,0,0),
(0,1,0,1,0,0,0,0,0,0),
(0,0,1,0,0,0,0,0,1,0),
(0,0,0,0,0,0,0,0,1,0),
(0,0,0,0,0,0,0,0,1,0),
(0,0,0,0,0,1,1,1,0,1),
(1,0,0,0,0,0,0,0,1,0)); {представление графа матрицей смежности}
Visit: array [0..n] of boolean=(true,true,true,true,true,true,true,
true,true,true);
{вершины не посещались}
var v: integer; {вершина начала поиска}
{1 способ - Рекурсивная реализация}
procedure DFS( v:integer);
var t: integer;
begin
write(v: 3); Visit[v]:=false;
for t:=0 to n do
if (C[v,t]=1) and (Visit[t]) then
DFS(t);
end;
{2 способ - Нерекурсивная реализация}
procedure DFS( v:integer);
var Stek: array [1..(n+1)] of 0..n; {стек представлен в виде массива}
Uk: integer; {с указателем на вершину стека}
t: integer; f: boolean;
begin
write(v:3);
{инициализация, стек пуст}
Uk:=0;
{добавить вершину в стек}
Uk:=Uk+1; Stek[Uk]:=v;
{отметить вершину как посещенную}
Visit[v]:=false;
while Uk<>0 do {пока стек не пуст}
begin
{извлекаем элемент из стека}
v:=Stek[Uk];
{нахождение вершины t, связанной с v дугой v->t}
t:=0; f:=false;
repeat
{если вершина t ранее не посещалась и связана дугой с v}
if (C[v,t]=1) and (Visit[t]) then
f:= true
else t:=t + 1;
until f or (t>n);{найдена смежная и непосещенная вершина или все вершины просмотрены}
if f then
begin
{выводим элемент в порядке обхода в глубину}
write(t:3);
Uk:=Uk+1;
Stek[Uk]:=t;
{отмечаем как посещенную вершину}
Visit[t]:=false;
end
else Uk:=Uk-1; {извлекаем вершину из стека}
{вершины просмотрены и смежных нет}
end;
end; {procedure}
begin
writeln(‘Поиск в глубину’);
writeln(‘Введите вершину начала поиска’); readln(v);
DFS(v); { поиск в глубину от исходной вершины v}
end.
Практическая работа
Упражнения:
Задание 1: Выполните обход в глубину для графа, изображенного на рис. 1, не используя программную реализацию. Начало обхода совпадает с вершиной 8. Запишите полученный список вершин.
Задание 2: Выполните программную реализацию поиска на графе в глубину. Исследуйте механизм поиска на примерах различных графов.
Задание 3: Используя приведенный пример программной реализации поиска на графе в глубину, запишите программу с использованием основных операций структуры данных Стек.
Задачи:
Часть 1.
· Постройте программную реализацию поиска в глубину, которая использует стек, состоящий из ребер графа. Граф представлен матрицей смежности.
· Постройте программную реализацию поиска в глубину с использованием стеком ребер графа. Граф представляется списком смежных вершин. (Для хранения списка смежных вершин используйте двумерный массив или два одномерных массива, индексированных номером ребра)
· Решите задачу 2 для случая представления графа списком смежных вершин с использованием динамических структур данных, например массива указателей на связанный список.
· Напишите программу нахождения простого пути в графе из вершины v в w с использованием процесса поиска в глубину. Программа распечатывает простой путь (в виде последовательности вершин найденного пути) из заданной вершины v к искомой вершине. Используйте представление графа в виде матрицы смежности.
· Решите задачу 4 для представления графа списком смежных вершин. Для представления графа используйте массивы.
· Решите задачу 4 для представления графа списком смежных вершин. Для представления графа используйте динамические структуры данных, массив указателей на связанный список.
· Напишите программу, реализующую нахождение дерева поиска DFS, которое представлено в виде родительских связей (массив, индексированный номерами вершин, содержащий элементы – родительскую вершину). Определите высоту полученного дерева (высота дерева определяется как длина пути от корня к самому удаленному листу). Используйте представление графа в виде матрицы смежности.
· Разработайте и напишите программу нахождения количества связных компонент графа, используя поиск в глубину для определения всех вершин, принадлежащих одной связанной компоненте (определяется путь, связывающий между собой любую пару вершин). Рассмотрите случай, когда граф оказывается несвязным.
· Разработайте и напишите программу нахождения фундаментального цикла в графе, используя поиск в глубину для определения всех вершин, которые уже посещались и отмечены. Разработайте реализацию программы, которая определяет существование фундаментального цикла в графе.
· Решите задачу 9, разработав реализацию, которая печатает все возможные фундаментальные циклы в графе.
Часть 2
1. Разработайте программную реализацию построения случайного графа и графического изображения его на плоскости. Выполните нахождение обхода графа в глубину и построение графической визуализации динамики разворачивающегося поиска.
Процесс прохождения вершин визуально отобразите, например сменой цвета вершины или закрашиванием соответствующих ребер с задержкой по времени, задаваемой фиксированной константой в миллисекундах или реализуемой по внешнему событию со стороны пользователя, например щелчок по кнопке.
Используйте для реализации визуальные среды программирования (Visual Basic, Delphi).
2. Разработайте программную реализацию построения случайного графа и графического изображения его на плоскости. Выполните нахождение обхода графа в глубину и построение графической визуализации динамики разворачивающегося поиска простого пути между парой вершин v и w. Путь визуально отобразите сменой цвета соответствующих ребер. Программа должна позволять задавать произвольные значения вершинам начала и конца пути. Используйте для реализации визуальные среды программирования (Visual Basic, Delphi).
Метод поиска в ширину на графе.
Реализация алгоритма ВFS
Цель: Сформировать представление о методе и алгоритме поиска в ширину на графе и его применении при решении задач (класса сложности Р).
Результаты. После выполнения лабораторной работы должны сформироваться умения:
· находить соответствие между объектом исследования (системой) и его концептуальной информационной моделью, логическим и физическим уровнями информационной модели;
· применять метод поиска (перебора) вершин в ширину на графе;
· формулировать и строить абстрактный алгоритм решения задачи поиска (перебора) вершин в ширину;
· применять программирование для реализации алгоритма поиска в ширину;
· выполнять оценку трудности программы для выбранного способа представления графа;
· обосновывать принадлежность алгоритма к категории сложности Р;
· уметь применять поиск в ширину на графе при решении практических задач.
Теоретические сведения