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

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

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

Рисунок 9.2 – Неориентированный связный граф

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

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

Заголовок функции DFS(st)

Вывести (st)

visited[st] посещена;

Для r1 до n выполнять

Если (graph[st, r] ≠ 0) и (visited[r] не посещена) то DFS(r)

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

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

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() //главная функция

{

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;

}

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

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 {основной блок программы}

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].