Поиск в глубину, применяется для
*решения произвольных задач на графах, требующих соответствующего порядка обхода ("в глубину") графа; раскрашивая пройденные вершины и/или дуги можно управлять порядком и способами обхода (например, однократное или многократное использование дуг и вершин)
*построения множества истоков и стоков (как истоков на транспонированном графе)
*построения сильносвязных компонент (ССК) графа ССК - это множество вершин, каждая из которых достижима из всех вершин ССК

Задача "Аудиосалон" (Беларусь, 1997 г.)
Ниже приведен пример неориентированного графа с шестью вершинами.

            (1)---(3)     (5)
             I \ / I       I
             I / \ I       I
            (2)---(4)     (6)
При компьютерной обработке граф может задаваться списком ребер (дуг) для каждой вершины. Например, для графа, приведенного на примере, этот список выглядит так

1: 2,3,4  (первая вершина соединена со второй, третьей и четвертой)
2: 1,3,4
3: 2,3,4
4: 1,2,3
5: 6
6: 5
Для хранения этой информации в памяти компьютера можно воспользоваться двумерным массивом G[1..N,1..M], где N - число вершин в графе, M - максимально возможное число ребер (дуг) у одной вершины графа. Для удобства обработки этой информации можно также иметь одномерный массив kG[1..N] - количества ребер (дуг) вершин графа.

Тогда для обработки списка связей текущей вершины U можно написать

for i:=1 to kG[u]
             begin
                V:=G[U,i];
                 ...
             end;

Тем самым, мы получаем обработку дуги, связывающей вершины U и V для всех вершин, непосредственно связанных с U.

Для обработки ВСЕХ связей всех вершин можно использовать поиск в глубину (DFS - Depth-First Search):

 ...
      for U:=1 to N do Color[u]:=WHITE;
      for U:=1 to N do
          if color[u]=WHITE then DFS(U);
      ...
      ...
      Procedure DFS(U:longint);
         var
             j : longint;
         begin
             color[u]:=GRAY;
             for j:=1 to kG[u] do DFS(G[U,j]);
         end;
       ...

Здесь

Color[u] = цвет вершины
WHITE (константа=1) - белый, если мы еще не посещали эту вершину
GRAY (константа=2) - серый, если мы посещали данную вершину
DFS(U) - рекурсивная процедура, которая вызывает себя для всех вершин, потомков данной вершины.
То есть, для обеспечения поиска в глубину на заданном графе G[1..N,1..M] с количествами дуг из вершин G[1..N], вначале мы устанавливаем всем вершинам цвет WHITE, а затем для всех вершин, которые еще не посещались (Color[G[U,j]]=WHITE) вызываем рекурсивную процедуру DFS.

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

Если же по условиям задачи потребуется посещать каждую вершину не более одного раза, чтобы формировать маршруты из несовпадающих вершин, то это может быть обеспечено в процедуре DFS условным вызовом:

Procedure DFS(U:longint);
          var
              j : longint;
          begin
              color[u]:=GRAY;
              for j:=1 to kG[u] do
                  if color[G[U,j]]=WHITE then DFS(G[U,j]);
          end;

Если по условиям задачи требуется каждую дугу использовать не более одного раза, то можно ввести расцветку дуг:

Color[1..N,1..M] - со значениями FREE или DONE

где, как и ранее

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

  procedure DFS(v:byte);
     var j : byte;
     begin
         for j:=1 to kG[v] do
             if (color[v,j]=FREE)
                then
                    begin
                          ...
                        color[v,j]:=DONE;
                        DFS(G[v,j]);
                        color[v,j]:=FREE;
                          ...
                     end;
    end;

Здесь вводятся пометки на дуги Color[v,j] = FREE, если дуга еще не обработана, и DONE, если она включена в текущий путь.

Если в задаче требуется вывести найденный путь, то для его хранения заводится специальный массив SLED [1..Q], где Q - максимальное количество ребер в пути. И вершины текущего пути заносятся в этот массив и удаляются из него в процессе обхода графа:

 procedure DFS(v:byte);
     var   j : byte;
     begin
        for j:=1 to kG[v] do
            begin
                ...
                inc(ks); sled[ks]:=G[v,j];
                DFS(G[v,j]);
               dec(ks);
              ...
            end;
     end;

Приведенная теоретическая информация иллюстрируется далее примерами решения конкретных задач.

Задача "Дороги"
Республиканская олимпиада по информатике 1997г

Дана система односторонних дорог, определяемая набором пар городов. Каждая такая пара (i,j) указывает, что из города i можно проехать в город j, но это не значит, что можно проехать в обратном направлении.

Необходимо определить, можно ли проехать из заданного города А в заданный город В таким образом, чтобы посетить город С и не проезжать ни по какой дороге более одного раза.

Входные данные задаются в файле с именем PATH.IN следующим образом. В первой строке находится натуральное N(N<=50) - количество городов (города нумеруются от 1 до N). Во второй строке находится натуральное M(M<=100) - количество дорог. Далее в каждой строке находится пара номеров городов, которые связывает дорога. В последней (M+3)-й строке находятся номера городов А, В и С.

Ответом является последовательность городов, начинающаяся городом А и заканчивающаяся городом В, удовлетворяющая условиям задачи, который должен быть записан в файл PATH.OUT в виде последовательности номеров городов по одному номеру в строке. Первая строка файла должна содержать количество городов в последовательности. При отсутствии пути записать в первую строку файла число -1.

Пример                Ответ
3                     3
2                     1
1 2                   2
2 3                   3
1 3 2
Кратко идея решения может быть изложена следующим образом:

Поиск в глубину.
Если встречаем вершину B, устанавливаем соответствующий флаг.
Если встречаем вершину C и флаг B установлен - выводим результат и завершаем работу.
После завершения поиска (требуемый маршрут не найден) выводим -1.
Изложим решение более подробно.

Ввод исходных данных осуществляется следующим образом:

read(N,M);
  for i:=1 to M do
      begin
           read(x,y); inc(kG[x]); G[x,kG[x]]:=y; color[x,kG[x]]:=FREE;
      end;
  read(A,B,C);

Здесь, как и прежде,

kG[i] - количество дуг из вершины i
G[i,j] - (для j от 1 до kG[j]) - вершины, с которыми вершина i связана соответствующей дугой
Кроме того, введен цвет дуги FREE - свободна (DONE - занята, FREE/DONE - константы)
Главная программа фактически включает только следующие операторы:

  LabC:=0;          { Установить метку - вершину C еще не посещали}
  DFS(A);            { Поиск в глубину от вершины A }
  writeln(-1);       { Вывод признака отсутствия требуемого пути}
Рекурсивная процедура поиска в глубину от вершины V выглядит следующим образом:

procedure DFS(v:byte);
      var   j : byte;
      begin
          for j:=1 to kG[v] do
              if (color[v,j]=FREE)
                 then
                     begin
                         if (G[v,j]=B) and (LabC=1)
                            then begin OutRes; halt; end;
                         if G[v,j]=C then LabC:=1;
                         color[v,j]:=DONE; inc(ks); sled[ks]:=G[v,j];
                         DFS(G[v,j]);
                         color[v,j]:=FREE; sled[ks]:=0; dec(ks);
                         if G[v,j]=C then LabC:=0;
                     end;
      end;

То есть для всех еще необработанных (color[v,j]=FREE) дуг от текущей вершины выясняем - если она ведет в конечный пункт, а город C уже проходили - вызов процедуры вывода результата и останов.

Если текущая дуга ведет в город С, устанавливаем соответствующую метку (LabC=1).

Помечаем дугу как обработанную, заносим ее в массив SLED, который содержит текущий обрабатываемый путь, KS - количество элементов в нем.

Вызываем процедуру DFS от вершины (G[v,j]), в которую ведет текущая дуга.

Перед выходом из процедуры DFS восстанавливаем состояние, "исходное" перед ее вызовом: снимаем отметку обработки с дуги ( color[v,j]:=FREE), удаляем ее из массива SLED (dec(ks), оператор sled[ks]:=0; делать необязательно, но он предоставляет удобства отладки - что бы в масcиве SLED ненулевыми были только реально входящие в путь элементы).

И, наконец, процедура вывода результата:

 procedure OutRes;
      begin
          writeln(ks+2);
          writeln(A); for i:=1 to ks do writeln(sled[i]); writeln(B);
      end;

Поскольку по алгоритму построения начальный (A) и конечный (B) города не заносились в массив SLED, то они выводятся отдельно, а количество городов в пути (KS) перед выводом увеличивается на 2.

Полный текст программы приводится ниже.

program by97d2s3;
const
    FREE=1;
    DONE=2;
var
  G,color                    : array[1..50,1..100] of byte;
  D                             : array[1..50] of longint;
  kG,sled                    : array[1..50] of byte;
  path                          : array[1..100] of byte;
  MinD,is                    : longint;
  i,j,x,y,A,B,C,N,M,ks,LabC  : byte;
  Yes                           : boolean;

  procedure OutRes;
      begin
          writeln(ks+2);
          writeln(A); for i:=1 to ks do writeln(sled[i]); writeln(B);
     end;

procedure DFS(v:byte);
    var j : byte;
    begin
        for j:=1 to kG[v] do
           if (color[v,j]=FREE)
              then
                 begin
                     if (G[v,j]=B) and (LabC=1)
                         then begin OutRes; halt; end;
                     if G[v,j]=C then LabC:=1;
                     color[v,j]:=DONE; inc(ks); sled[ks]:=G[v,j];
                     DFS(G[v,j]);
                     color[v,j]:=FREE; sled[ks]:=0; dec(ks);
                     if G[v,j]=C then LabC:=0;
                 end;
    end;

begin
   assign(input,'path.in'); reset(input);
   assign(output,'path.out'); rewrite(output);
   read(N,M);
   for i:=1 to M do
       begin
           read(x,y); inc(kG[x]); G[x,kG[x]]:=y; color[x,kG[x]]:=FREE;
       end;
   read(A,B,C);
   LabC:=0;
   DFS(A);
   writeln(-1);
   close(input); close(output);
end.

Вот ещё пример задачи на поиск в глубину.

Грядки

Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.

Входные данные

В первой строке входного файла INPUT.TXT находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. (1 <= N, M <= 200)

Выходные данные

В выходной файл OUTPUT.TXT выведите количество грядок на садовом участке.

Примеры

INPUT.TXT

5 10
##......#.
.#..#...#.
.###....#.
..##....#.
........#.

OUTPUT.TXT

3

Основной код

var g:array [1..200,1..200] of char; k,i,j,n,m:integer;
procedure dfs(x,y:longint);
begin

g[x,y]:='o';
if (y<m )and(g[x,y+1]='#') then dfs(x,y+1);
if (y>1 )and(g[x,y-1]='#') then dfs(x,y-1);
if (x<n )and(g[x+1,y]='#') then dfs(x+1,y);
if (x>1 )and(g[x-1,y]='#') then dfs(x-1,y);

end;
begin
 assign(input, 'input.txt'); reset(input);
  assign(output, 'output.txt'); rewrite(output);
 readln(n,m);
 k:=0;
 for i:=1 to n do begin
                   for j:=1 to m do
                   read(g[i,j]);
  readln;
 end;
 for i:=1 to n do
  for j:=1 to m do begin
                    if (g[i,j]='#')
                     then begin
                           k:=k+1;
                           dfs(i,j);
                          end;
                    end;
 writeln(k);
end.

Отредактировано Санчоус (2011-10-16 16:37:23)