|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Занятие 13. Графы. Обход в глубину.
На этом занятии мы рассмотрим применение рекурсии на примере алгоритма обхода графа в глубину.
Обход графа в глубину состоит в следующем: если мы попали в какую-то вершину, то мы помечаем ее как "пройденную" и вызываем себя рекусивно от всех непомеченных вершин, соседних с данной. Таким образом, этот алгоритм обходит все вершины, достижимые из начальной, и каждую вершину обрабатывает не более одного раза.
Приведем текст процедуры обхода в глубину. Как видно, он очень короткий и простой:
procedure dfs(v:integer);
var
i:integer;
begin
used[v]:=true;
for i:=1 to n do
if (a[v,i]=1)and(not used[i]) then
dfs(i);
end;
Топологическая сортировка
Топологической сортировкой называют порядок нумерации вершин ориентированного графа, при котором любое ребро идет из вершины с меньшим номером в вершину с большим.
Очевидно, что не любой граф можно отсортировать топологически. Можно доказать, что топологическая сортировка существует для ацеклических графов и не существует для цикличестких.
Итак, займемся построением топологической сортировки.
Заведем счетчик времени - переменную, которая в начале работы программы равна 0 и увеличивается на 1 при прохождении программы через некоторую контрольную точку. В качестве контрольной точки выберем точку выхода из процедуры обхода в глубину. Для каждой вершины запомним значение счетчика времени, которое она получила в процессе обхода в глубину, в глобальном массиве. Эти числа позволяют определить, обработку какой вершины поиск в глубину закончил раньше, а какой позже. Их можно назвать "временем выхода" поиска из данной вершины.
Теперь будем запускать модифицированный таким образом поиск в глубину из всех непомеченных вершин, пока таковых не останется. После этого отсортируем вершины в порядке уменьшения времени выхода.
Легко проверить, что для ациклического графа полученный порядок является его топологической сортировкой. А для циклических графов топологической сортировки не существует.
| Задача 13-1. Обход в глубину |
| Задача 13-2. Банкет |
| Задача 13-3. Построение |