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

Пусть наш граф из N вершин представлен матрицей смежности G. Заведем массив V из N элементов, в котором на i-м месте будет стоять true, если вершина i была рассмотрена нами ранее, и false в противном случае.

Обход в глубину осуществляется по следующему принципу: сначала посещается вершина 1, затем любая вершина A, соединенная с 1, затем любая еще не посещенная вершина B, соединенная с A и т. д. Когда очередную вершину нельзя будет выбрать, алгоритм будет возвращаться к предыдущей рассмотренной. Таким образом обходятся все компоненты связности графа.

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

const
  MaxN = 100;

var
  N : Integer;
  G : array [1 .. MaxN,1 .. MaxN] of Boolean;
  V : array [1 .. MaxN] of Boolean;

procedure DFS_Work(A : Integer);
var
  B : Integer;
begin
  V[A] := True;
  Writeln(A);
  for B := 1 to N do
    if G[A,B] and not V[b] then
      DFS_Work(B);
end;

procedure DFS;
var
  A : Integer;
begin
  FillChar(V,sizeof(V),0);
  for A := 1 to N do
    if not V[A] then
      DFS_Work(A);
end;

Оценим время работы данной реализации алгоритма. Процедура DFS_Work вызывается N раз (по одному разу для каждой вершины), и она делает O(N) действий, не считая рекурсивного вызова; значит, общее время работы O(N^2). Для работы алгоритма требуется O(N) памяти, не считая матрицу смежности (O(N) для хранения массива V и O(N) для хранения стека вызовов процедуры DFS_Work). 

Реализация для графа, заданного списками смежности:

Const
  MaxN = 100;
  MaxM = 10000;

type
  TConn = record
    A,B : Integer;
  end;

var
  N,M : Integer;
  GA : array [1 .. MaxN] of Integer;
  GB : array [1 .. MaxM] of TConn;
  V : array [1 .. MaxN] of Boolean;

procedure DFS_Work(A : Integer);
var
  B : Integer;
begin
  V[A] := True;
  Add(A);
  B := GA[A];
  while B<>0 do
  begin
    if not V[GB[b].A] then DFS_Work(GB[b].A);
    B := GB[b].B;
  end;
end;

procedure DFS;
var
  A : Integer;
begin
  FillChar(V,sizeof(V),0);
  for A := 1 to N do
    if not V[A] then
      DFS_Work(A);
end;

Данная реализация требует O(M+N) времени и O(N) памяти. (M - число ребер графа).

С помощью обхода в глубину легко найти все вершины, достижимые из данной. Для этого вызовем DFS_Work только для данной вершины. В результате в массиве V значение true будет стоять только для тех вершин, которые достижимы из данной.

Отредактировано Berd (2007-06-20 10:22:00)