Задача 4. Лекция. Графы. DFS. Времена входа и выхода ≡

Условие

Времена входа и выхода при обходе в глубину

Вспомним процедуру обхода графа в глубину.

procedure Explore(v: Integer);
var
    i: Integer;
begin
    used[v]  := true;
    Previsit(v);

    for i := 0 to High(adj[v]) do
        if not used[adj[v][i]] then
            Explore(adj[v][i]);

    Postvisit(v);
end;

Поиск в глубину позволяет за линейное время определить, связен ли граф. Но это далеко не все — сейчас мы рассмотрим прием, который лежит в основе многих других применений поиска в глубину. Будем записывать время входа в каждую вершину (вызов Previsit) и время выхода (Postvisit). Для нашего примера эти числа показаны на рис. 1. Например, в момент времени 5 началась обработка вершины I, а в момент времени 21 закончилась обработка вершины D.

Чтобы сохранить эту информацию при поиске в глубину, заведем счетчик time, изначально равный 1, и напишем так:

procedure Previsit(v: integer);
begin
    tin[v] := time;
    time += 1;
end;

procedure Postvisit(v: integer);
begin
    tout[v] := time;
    time += 1;
end;

Рассмотрим отрезки на числовой прямой, образованные временами входа и выхода в каждую из вершин.

Свойство. Для любых двух вершин u и v либо отрезки [tin(u), tout(u)] и [tin(v), tout(v)] не пересекаются, либо один содержится в другом.

В самом деле, [tin(u), tout(u)] — это промежуток времени, в течение которого вершина u была в стеке, и если вершина v была помещена в стек, когда там уже лежала вершина u, то v будет вынута раньше u.

Таким образом, рассмотренные отрезки отражают структуру дерева, построенного при поиске в глубину.

---