Первая страница / Визуализаторы / Графы. Основные алгоритмы / Обход в глубину / в ширину /

Описание алгоритма

Обход графа в глубину

Описание алгоритма

Поиск в глубину (DFS, depth-first search) представляет собой классический гибкий алгоритм, который применяется для решения задачи связанности и множества других задач обработки графов. Возможны две реализации этого базового алгоритма: одна в виде рекурсивной процедуры, другая — с использованием явно заданного стека. Мы будем использовать стек магазинного типа. Применение правила LIFO (Last In First Out — последним пришел, первым обслужен), которое характеризует работу стека магазинного типа, соответствует исследованию соседних коридоров в лабиринте: из всех еще не исследованных коридоров выбирается последний из тех, с которым мы столкнулись. Словом стратегия поиска в глубину такова: идти «вглубь», пока это возможно (есть непройденные исходящие ребра), и возвращаться и искать другой путь, когда таких ребер нет. Так делается, пока не обнаружены все вершины, достижимые из исходной.

Цвет. Алгоритм поиска в глубину использует три цвета. Каждая из вершин вначале белая. Будучи обнаруженной (discovered), она становится темно-серой; затем когда она будет полностью обработана (finished), то есть когда список смежных с ней вершин будет просмотрен, мы красим ее в черный цвет.

Процедура обхода графа в глубину

procedure push(const n: longint);
 1  t := t + 1;
 2  stack[t] := n;
 3  visited[n] := 1;
function pop;
 1  t := t - 1;
 2  pop := stack[t];
procedure DFS(adjMatrix: array [0..n-1] of longint);
 1  for i := 0 to n - 1 do visited[i] := 0;
 2  for i := 0 to n - 1 do begin
 3      if (visited[i] <> 1) then begin
 4          t := 0;
 5          push(i);
 6          flag := false;
 7          while t > 0 do begin
 8              if flag then k := pop else k := stack[t];
 9              flag := true;
10              for i := 0 to n - 1 do
11                  if (adjMatrix[k, j] > 0) and (visited[j] <> 1) and flag then begin
12                      push(j);
13                      flag := false;
14                  end;
15          end;
16      end;
17  end;

Пояснения

Процедура Push
добавляет элемент в стек;
красит элемент в темно-серый цвет.
Функция Pop
удаляет элемент из стека, когда у него больше нет смежных вершин;
возвращает предпоследний элемент;
красит удаленную вершину в черный цвет.
Процедура DFS
Строка 1 — все вершины красятся в белый цвет.
Строки 2–3 — находим начальный элемент новой компоненты связанности.
Строки 4–6 — добавляем начальный элемент в стек.
Строка 7 — проверяем, есть ли в стеке элементы.
Строка 8 — проверяем, есть ли у элемента смежные вершины.
Строки 10–14 — ищем смежную с элементом k вершину и добавляем ее в стек.

Обход графа в ширину

Описание алгоритма

Замена стека, используемого в обходе в глубину очередью FIFO (First In First Out — первым пришел, первым обнаружен) приводит к другому классическому алгоритму — к алгоритму поиска в ширину (BFS, breath-first search), который используется для решения других задач обработки графов, связанных с нахождением кратчайших путей. Поиск в ширину — один из базисных алгоритмов, составляющий основу многих других. Например, алгоритм Дейкстры поиска кратчайших путей и алгоритм Прима поиска минимального покрывающего дерева могут рассматриваться как обобщения поиска в ширину. Алгоритм поиска в ширину перечисляет все достижения из начальной вершины (вершины в порядке возрастания от начальной). Словом мы идем «вширь», а не «вглубь» (сначала просматривая все соседние вершины, затем соседей соседей и т. д.)

Цвет. Для наглядности мы будем считать, что в процессе работы алгоритма вершины графа могут быть белыми, темно серыми и черными. Вначале они все белые, но в ходе работы алгоритма вершина может стать темно-серой, а затем — черной. Точнее, при помещении вершины в очередь вершина становится темно-серой, а при удалении черной.

Процедура обхода графа в ширину

procedure push(const n: longint);
 1  queue[head] := n;
 2  head := head + 1;
 3  visited[n] := 1;
function pop;
 1  pop := queue[tail];
 2  tail := tail + 1; 
procedure BFS(adjMatrix: array [0..n-1] of longint);
 1  for i := 0 to n - 1 do visited[i] := 0;
 2  for i := 0 to n - 1 do begin
 3      if (visited[i] <> 1) then begin
 4          push(i);
 5          while tail <> head do begin
 6              k := pop;
 7              for i := 0 to n - 1 do
 8                  if (adjMatrix[k, j] > 0) and (visited[j] <> 1) then
 9                      push(j);
10          end;
11      end;
12  end;

Пояснения

Процедура Push
добавляет элемент в конец очереди;
красит элемент в темно-серый цвет;
Функция Pop
удаляет элемент из начала очереди, когда у него больше нет смежных вершин;
возвращает следующий элемент;
красит удаленную вершину в черный цвет;
Процедура BFS
Строка 1 — все вершины красятся в белый цвет.
Строки 2–3 — находим начальный элемент новой компоненты связанности.
Строка 4 — добавляем начальный элемент в очередь.
Строка 5 — проверяем, есть ли в очереди элементы.
Строка 6 — если есть элеметы, то берем первый элемент k из очереди.
Строки 7–9 — ищем смежные с элементом k вершины и добавляем их в очередь.