Сделай Сам Свою Работу на 5

II. Рекурсивная реализация





Поиск в глубину

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

Очевидно, что для фиксации признака, просмотрена вершина графа или нет, требуется структура данных типа:

Pr : Array[1..N] Of Boolean.

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

Рис. 1 Рис. 2

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

Основные задачи, которые решает поиск в глубину:



1. Обход графа всеми возможными путями (классический алгоритм поиска в глубину без каких-либо изменений);

2. Проверка графа на ацикличность и нахождения циклов;

3. Нахождения количества частей графа, если он является несвязанным
и т. д.

Алгоритмы основанные на поиске в глубину:

1. Алгоритм нахождения Эйлерова цикла (цикл проходящий по всем рёбрам);

2. Алгоритм нахождение Гамильтонова цикла (цикл проходящий по всем вершинам);

В силу важности данного алгоритма рассмотрим 2 варианта его реализации: нерекурсивную и с использованием рекурсии.

I. Нерекурсивная реализация

А – матрица смежности, Pr – массив признаков (посещали мы вершину или нет). Номера просмотренных вершин графа запоминаются в стеке St, указатель вершины стека – переменная Vs.

Программная реализация алгоритма обхода невзвешанного графа с 1-ой вершины:

Var a : array[1..100,1..100] of integer; //матрица смежности//

pr : array[1..100] of boolean; //массив признаков//

i,vs,k,l,n,m : integer;

flag : boolean;

st : array[1..100] of integer; //массив вершин по которым осуществлялся поиск//



 

Begin

assign(input, 'input.txt');

assign(output, 'output.txt');

reset(input);

rewrite(output);

readln(n, m);

fillchar(a, sizeof(a), 0); // обнуляем матрицу смежности//

for i:=1 to m do //создаём матрицу смежности//

begin

readln(k, l);

a[k, l]:=1;

a[l, k]:=1;

end;

fillchar(st, sizeof(st), 0); // обнуляем стек//

fillchar(pr, sizeof(pr), false); // массив признаков заполняем false//

 

vs:=1; // указатель вершины стека перемещаем на первый элемент//

st[vs]:=1; // записываем в стек начальную вершину поиска//

pr[1]:=true; // в массиве признаков помечаем, что мы эту вершину посетили//

While vs<>0 do begin // Пока стек не пуст делать …//

flag:=False;

For i:=1 to n do

if (A[st[vs], i] <>0) and not(pr[i])

then begin flag:=true; break; end;

If flag

then begin

inc(vs);

st[vs]:=i; // добавляем номер вершины в стек//

pr[i] :=true; // помечаем в массиве признаков, что мы посетили эту вершину//

end

else dec(vs); // если из рассматриваемой вершины некуда идти, то убираем её из стека//

end; // конец while//

close(input);

close(output);

End.

II. Рекурсивная реализация

Словесное описание алгоритма, при помощи рекурсии:

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



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

Программная реализация алгоритма обхода невзвешанного графа с 1-ой вершины:

Var a : array[1..100,1..100] of integer; //матрица смежности//

pr : array[1..100] of boolean; //массив признаков//

i,vs,k,l,n,m : integer;

st : array[1..100] of integer; //массив вершин по которым осуществлялся поиск//

 

Procedure pg(v:integer);

var j : integer;

begin

inc(vs);

st[vs]:=v; //заносим вершину в массив, хранящий пусть//

for j:=1 to n do //начинаем поиск смежной вершины//

if (a[v,j]<>0) and (not(pr[j])) then //проверяем: можно ли попасть в вершину//

begin

pr[j]:=true; //помечаем, что мы были в этой вершине//

pg(j); // запуск процедуры, для поиска пути уже из след. вершины//

end;

end;

 

Begin

assign(input,'input.txt');

assign(output,'output.txt');

reset(input);

rewrite(output);

readln(n,m);

fillchar(a, sizeof(a), 0); // обнуляем матрицу смежности//

for i:=1 to m do //создаём матрицу смежности//

begin

readln(k,l);

a[k,l]:=1;

a[l,k]:=1;

end;

fillchar(st, sizeof(st), 0); // обнуляем стек//

fillchar(pr, sizeof(pr), false); // массив признаков заполняем false//

 

vs:=0; // vs – указатель стека, в котором хранятся номера посещенных вершин в порядке их посещения//

pr[1]:=true; //записываем в массив признаков, что мы были в 1-ой вершине//

pg(1); //запускаем поиск в глубину с 1-ой вершины//

for i:=1 to vs do write(st[i],' '); //вывод вершин, по которым был осуществлён поиск//

close(input);

close(output);

End.


Задачи для решения

  1. Задан ориентированный невзвешенный граф. Необходимо найти путь от вершины с номером s до вершины с номером f.

Формат ввода:

Input.txt Output.txt
1 2 1 3 1 3 1 2 3

Первая строка входного файла содержит число n - количество вершин в графе
(1 <= n <= 15 000). Следующие n строк содержат число ki – количество вершин, связанных с i-й вершиной графа, далее в этой же строке ki чисел – вершины, в которые входит дуга из вершины с номером i. В последней строке файла располагаются два числа s и f – номер начальной и конечной вершин пути соответственно.

Формат вывода:

В файл выведите путь из вершины s в вершину f: некоторую последовательность номеров вершин, начинающуюся s и заканчивающуюся f. Все числа находятся в одной строке и разделяются одним пробелом. Если путей существует несколько, то выведите любой. Если пути не существует – выведите -1.

2. Дан граф связанный, неориентированный граф. Найти все возможные пути из вершины V1 в вершину V2. Формат ввода данных: в первой строке вводятся 2 числа N, M, где N и M – кол-во вершин и рёбер графа соответственно; в следующих M строках идёт описание ребра: из какой вершины выходит и в какую идёт; в последней строке вводятся вершины V1, V2.

 

Input.txt Output.txt
5 6 1 2 1 3 2 3 2 5 3 4 4 5 1 5 1 2 3 4 5 1 2 5 1 3 2 5 1 3 4 5

 

3. Дан неориентированный граф. Проверить из скольких частей состоит граф. Формат ввода данных: в первой строке вводятся N и M, где N и M – кол-во вершин и рёбер графа соответственно; в следующих M строках идёт описание ребра: из какой вершины выходит и в какую идёт.

 

Input.txt Output.txt
3 3 1 2 1 3 2 3
6 6 1 2 1 3 2 3 4 5 4 6 5 6

 

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.