Задача 1. Лекция. Графы. Поиск в ширину ≡

Условие

Кратчайшие пути

Поиск в глубину не только быстро находит все вершины, достижимые из начальной, но и строит дерево, содержащее пути к ним (рис. 1). Однако эти пути не обязательно будут кратчайшими: например, от S до C можно добраться по одному ребру, в то время как поиск в глубину находит путь из трех.

Расстоянием(distance) между двумя вершинами неориентированного графа будем называть длину кратчайшего пути между ними, измеренную в ребрах. У этого понятия есть простой физический смысл. Представим себе граф из шариков (вершин), соединенных нитками одинаковой длины (ребрами). Потянем граф вверх за вершину s; за ней потянутся все вершины, достижимые из s. Чтобы найти расстояния от них до s, мы можем теперь просто измерить, насколько они ниже s.

Например, на (рис. 2) расстояние между вершинами S и B равно 2, и есть два кратчайших пути между ними. Когда граф подвешен за S, все ребра этих двух путей натягиваются. А ребро (D, E) провисает, поскольку не входит ни в один из кратчайших путей из вершины S.

Поиск в ширину

Вершины графа рис. 2, подвешенного за S, разбиваются на слои: сама S, вершины на расстоянии 1 от S, вершины на расстоянии 2 и так далее. Можно находить расстояния от S до всех вершин, переходя от уровня к уровню. Когда вершины уровней 0, 1, 2, ..., d определены, легко найти вершины уровня d + 1: это просто еще не просмотренные вершины, смежные с вершинами уровня d. Эти рассуждения наталкивают нас на алгоритм, работающий в каждый момент с двумя уровнями: некоторым уровнем d, который уже полностью известен, и уровнем d + 1, который находится просмотром соседей вершин уровня d.

Для необходимого порядка просмотра вершин нам понадобится структура данных очередь. В такой структуре данных есть три операции:

• Push — добавить элемент в конец очереди
• Pop — удалить начальный элемент очереди (данная функция также возвращает удаленный элемент)
• Empty — узнать, пуста ли очередь

procedure Push(v: integer);
begin
    q[qend] := v;
    qend += 1;
end;

function Pop(): integer;
begin
    Result := q[qbegin];
    qbegin += 1;
end;

function Empty(): boolean;
begin
    Result := (qbegin = qend);
end;

Поиск в ширину (breadth-first search, BFS) непосредственно реализует вышеописанную идею обхода вершин (рис. 4). Изначально очередь Q содержит только вершину S, то есть вершину на расстоянии 0. Для каждого последующего расстояния d = 1, 2, 3, ... найдется момент времени, в который Q содержит все вершины на расстоянии d и только их. Когда все эти вершины будут обработаны (извлечены из очереди), их непросмотренные соседи окажутся добавленными в конец очереди, то есть мы перейдем к следующему значению d.

procedure bfs(start: integer);
var
    i, u, v: integer;
begin
    Push(start);

    used[start] := true;
    dist[start] := 0;

    while not Empty() do begin
        u = Pop();

        for i := 0 to High(adj[u]) do begin
            v = adj[u][i];

            if not used[v] then begin
                used[v] := true;
                Push(v);
                dist[v] := dist[u] + 1;
            end;
        end;
    end;
end;

Запустим этот алгоритм для вершины S в графе (рис. 1). Считаем, что соседи каждой вершины обрабатываются в алфавитном порядке. На (рис. 5) слева показан порядок обхода вершин, а справа изображено дерево поиска в ширину. Оно содержит только ребра, при переходе по которым обнаруживались новые вершины. В отличие от дерево поиска в глубину все пути данного дерева с началом в S являются кратчайшими. Поэтому оно называется деревом кратчайших путей (shortest-path tree).

Порядок обхода	Содержание очереди
	[S]
S	[A C D E]
A	[C D E B]
C	[D E B]
D	[E B]
E	[B]
S	[]

Этот алгоритм можно применять и к ориентированным графам. В них тоже можно определить расстояние от вершины S до вершины T как минимальное число ребер, которое надо пройти (в их направлении), чтобы из S попасть в T. Расстояние при этом уже не будет симметрично, но понятие кратчайшего пути имеет смысл, и наш алгоритм по-прежнему годится.

Корректность и время работы

Убедимся в корректности алгоритма. Мы утверждаем, что для всех d = 0, 1, 2, ... найдется момент времени, когда:

1. для всех вершин на расстоянии не более d это расстояние уже помещено в массив dist;
2. для всех оставшихся вершин значения в dist равны ∞ (бесконечность);
3. очередь содержит в точности вершины на расстоянии d.

Данное утверждение легко доказывается по индукции (проверьте).

Как и в случае поиска в глубину, время работы поиска в ширину линейно, то есть равно O(|V| + |E|). Действительно, каждая вершина помещается в очередь ровно один раз — при ее обнаружении. Поэтому общее количество операций с очередью есть 2|V|. Вся оставшаяся работы производится во внутреннем цикле алгоритма. На это требуется время O(|E|), поскольку каждое ребро в данном цикле просматривается один раз (для ориентированных графов) или два раза для неориентированных).

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

Если в алгоритме поиска в ширину заменить очередь на стек (вынимается первым тот элемент, который положен последним), то он превратится в поиск в глубину (в нерекурсивном варианте).

При поиске в ширину нас интересуют расстояния от s, поэтому мы не перезапускаем поиск в других связных компонентах (недоступные вершины просто игнорируются).

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов