Программа исследования графа поиском в глубину

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Задание на лабораторную работу

Реализовать алгоритм поиска в глубину в графе и найти каркас графа на основе приведённой теоретический информации. Путем имитационного моделирования оценить эффективность алгоритма по временному критерию.

Цель работы

Закрепить теоретический материал о графах. Реализовать алгоритм поиска в глубину, построить каркас графа и оценить сложность метода.

Краткие теоретические сведения

Поиск в глубину - вероятно, наиболее важная ввиду многочисленности приложений стратегия обхода графа. Идея этого метода - идти вперед в неисследованную область, пока это возможно, если же вокруг все исследовано, отступить на шаг назад и искать новые возможности для продвижения вперед. Метод поиска в глубину известен под разными названиями, например, «бэктрекинг», «поиск с возвращением».

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

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

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

Рис. 1.

алгоритм глубина граф вершина

Обозначим стек для открытых вершин через , остальные обозначения сохраняют тот же смысл, что и в предыдущем разделе. Через  обозначается верхний элемент стека (т.е. последний элемент, добавленный к стеку). Тогда процедура обхода одной компоненты связности методом поиска в глубину со стартовой вершиной  может быть записана следующим образом (DFS - Depth First Search).

Procedure DFS(a)

1. посетить вершину 

2.

3. while  do

4.

5. if имеется неисследованное ребро 

6. then исследовать ребро 

7. if вершина  новая

8. then посетить вершину 

9.

10. else удалить  из 

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

Алгоритм обхода всего графа - тот же, что и в случае поиска в ширину (алгоритм 1 предыдущей лекции), только нужно очередь заменить стеком, а процедуру BFS - процедурой DFS.

Свойства 1 и 2 поиска в ширину, отмеченные в предыдущем разделе, сохраняются и для поиска в глубину. Остается верной и оценка трудоемкости , но ее доказательство требует несколько иных рассуждений, так как каждая вершина теперь может становиться активной несколько раз. Однако каждое ребро рассматривается только два раза (один раз для каждой инцидентной ему вершины), поэтому в операторе if в строке 5 ветвь then (строки 6-9) повторяется  раз. В этом же операторе ветвь else (строка 10) повторяется  раз, так как каждая вершина может быть удалена из стека только один раз. В целом получается , причем остаются справедливыми сделанные в предыдущей лекции замечания об условиях, при которых имеет место эта оценка.

4. Текст программы

Const n=9; {Значение п не должно превышать 254}

Type matr=Array [1..n, 1..n] of byte; vek=Array [1..n] of byte;

Const A: matr = ((0,1,0,1,0,0,0,1,0),

(1,0,1,0,0,1,0,0,0),

(0,1,0,1,1,0,1,0,0),

(1,0,1,0,0,0,1,0,0),

(0,0,1,0,0,0,0,1,1),

(0,1,0,0,0,0,0,0,0),

(0,0,1,1,0,0,0,0,0),

(1,0,0,0,1,0,0,0,0),

(0,0,0,0,1,0,0,0,0));

Var R:vek; j:byte;

Procedure Karkas (Var A:matr; X:byte; Var R:vek);

Var St:vek; c: Boolean; j, k, L:byte;

Begin For j:=1 to n do R[j]:=0;

k:=1; {k - указатель верхушки стека}

St[k]:= X; {Занесение в стек st отправного узла}

R[X]:= n+1; {Отмечаем посещение узла X}

j:=0;

Repeat L:= St[k]; {Номер L текущего узла берем из стека}

с:= false; {Далее идет цикл поиска смежного узла}

Repeat j:=j+1;

If j > n Then c:= true

Else If (A [L, j]=1) And (R[j]=0) Then c:=true

Until с; {Или смежный узел найден, или L-я строка исчерпана}

If j > n Then {Шаг назад, ибо L-я строка исчерпана:}

Begin j:=L; k:=k-1 End {Перемещаем верхушку стека}

Else {Шаг вперед, ибо подходящий смежный узел найден:}

Begin k:=k+1; St[k]:=j; {Заносим в стек новый узел j}

R[J]:= L; {Отмечаем посещение узла j и запоминаем «отца»}

j:=0;

End

Until k = 0

End;

BEGIN Karkas (A, 5, R); {Находим каркас графа G1 для X=5}

j:=8; {Далее проверяем простую цепь, ведущую от Х к узлу 8}

Repeat Write (j, ', '); j:= R[j] {Продвижение к «отцу» узла j}

Until j = n+1; Writeln; Readln;

END.

В блоке Karkas через L обозначен текущий узел, через - очередной, «кандидат» на эту роль. Возвращаясь к некоторому узлу Y, мы не должны рассматривать все смежные узлы, а продолжать анализ его связей. Неприметное действие j:=L (выделено в программе), выполняемое при возврате к Y, восстанавливает номер столбца, на котором мы остановились, уходя от узла Y «вперед». Теперь анализироваться будут лежащие правее элементы Y-й строки матрицы А.

Если граф не связен, поиск в глубину ограничивается компонентой графа связности, в которой выбрали отправным узел X. При этом элементы R[j], относящиеся к узлам j других компонент, сохраняют исходное значение 0. Чтобы продолжить поиск в новой компоненте, надо взять отправной узел j, для которого R[j]=0.

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

6. Вывод

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

Литература

1) Абрамов С.А. и др. Задачи по программированию. - М.: Наука, 1988

2) Подбельский В.В., Фомин С.С. Программирование на языке Си. - М.: Финансы и статистика, 2001.

3) Евстигнеев В.А. Применение теории графов в программировании. - М.: Наука, 1985.

4) Кнут Д. Искусство программирования для ЭВМ. - М.: Мир, 1977.

Размещено на Allbest.ru