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

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

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

Рассмотрим то, как будет вести себя алгоритм на конкретном примере. Приведенный далее неориентированный связный граф имеет в сумме 5 вершин. Сначала необходимо выбрать начальную вершину. Какая бы вершина в качестве таковой не была выбрана, граф в любом случае исследуется полностью, поскольку, как уже было сказано, это связный граф без единого направленного ребра.
Пусть обход начнется с узла 1, тогда порядок последовательности просмотренных узлов будет следующим: 1 2 3 5 4. Если выполнение начать, например, с узла 3, то порядок обхода окажется иным: 3 2 1 5 4.

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

Псевдокод алгоритма:

Здесь DFS (depth-firstsearch) – название функции. Единственный ее параметр st – стартовый узел, передаваемый из главной части программы как аргумент. Каждому из элементов логического массива visited заранее присваивается значение false, т. е. каждая из вершин изначально будет значиться как не посещенная.

Двумерный массив graph – это матрица смежности графа. Большую часть внимания следует сконцентрировать на последней строке. Если элемент матрицы смежности, на каком то шаге равен 1 (а не 0) и вершина с тем же номером, что и проверяемый столбец матрицы при этом не была посещена, то функция рекурсивно повторяется. В противном случае функция возвращается на предыдущую стадию рекурсии.

Код программы на C++:

#include "stdafx.h"
#include <iostream>
using namespace std;
const int n=5;
int i, j;
bool *visited=new bool[n];
//матрица смежности графа
int graph[n][n] =
{
{0, 1, 0, 0, 1},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{1, 0, 1, 1, 0}
};
//поиск в глубину
void DFS(int st)
{
int r;
cout<<st+1<<" ";
visited[st]=true;
for (r=0; r<=n; r++)
if ((graph[st][r]!=0) && (!visited[r]))
DFS(r);
}
//главная функция
void main()
{
setlocale(LC_ALL, "Rus");
int start;
cout<<"Матрица смежности графа: "<<endl;
for (i=0; i<n; i++)
{
visited[i]=false;
for (j=0; j<n; j++)
cout<<" "<<graph[i][j];
cout<<endl;
}
cout<<"Стартовая вершина >> "; cin>>start;
//массив посещенных вершин
bool *vis=new bool[n];
cout<<"Порядок обхода: ";
DFS(start-1);
delete []visited;
system("pause>>void");
}

Код программы на Pascal:

program DepthFirstSearch;
uses crt;
const
n=5;
var
i, j, start: integer;
visited: array[1..n] of boolean;
const graph: array[1..n,1..n] of byte =
((0, 1, 0, 0, 1),
(1, 0, 1, 1, 0),
(0, 1, 0, 0, 1),
(0, 1, 0, 0, 1),
(1, 0, 1, 1, 0));
{поиск в глубину}
procedure DFS(st: integer);
var r: integer;
begin
write(st:2);
visited[st]:=true;
for r:=1 to n do
if (graph[st, r]<>0) and (not visited[r]) then
DFS(r);
end;
{основной блок программы}
begin
clrscr;
writeln('Матрица смежности:');
for i:=1 to n do
begin
visited[i]:=false;
for j:=1 to n do
write(graph[i, j],' ');
writeln;
end;
write('Стартовая вершина >> '); read(start);
writeln('Результат обхода'); DFS(start);
end.

Для простоты понимания результата, выдаваемого двумя программами, взят неориентированный граф, приводимый ранее в качестве примера, и представленный матрицей смежности graph[5][5].