Задача 1. Лекция. Графы. Поиск в ширину ≡
| Входной файл: | input.txt | Ограничение времени: | 1 сек | |
| Выходной файл: | output.txt | Ограничение памяти: | 256 Мб |
Условие
Кратчайшие пути
Поиск в глубину не только быстро находит все вершины, достижимые из начальной, но и строит дерево, содержащее пути к ним (рис. 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, ... найдется момент времени, когда:
- для всех вершин на расстоянии не более d это расстояние уже помещено в массив dist;
- для всех оставшихся вершин значения в dist равны ∞ (бесконечность);
- очередь содержит в точности вершины на расстоянии d.
Данное утверждение легко доказывается по индукции (проверьте).
Как и в случае поиска в глубину, время работы поиска в ширину линейно, то есть равно O(|V| + |E|). Действительно, каждая вершина помещается в очередь ровно один раз — при ее обнаружении. Поэтому общее количество операций с очередью есть 2|V|. Вся оставшаяся работы производится во внутреннем цикле алгоритма. На это требуется время O(|E|), поскольку каждое ребро в данном цикле просматривается один раз (для ориентированных графов) или два раза для неориентированных).
Теперь, когда знаем и поиск в глубину, и поиск в ширину, интересно сравнить их способы обхода графа. Поиск в глубину стремится вперед, и возвращается назад, чтобы пойти вбок, только если впереди уже нет новых вершин. Поэтому он может долго добираться до вершины, которая находится совсем близко (рис. 1). Поиск в ширину обходит вершины в порядке увеличения расстояний до них от начальной вершины, как фронт волны на воде.
Если в алгоритме поиска в ширину заменить очередь на стек (вынимается первым тот элемент, который положен последним), то он превратится в поиск в глубину (в нерекурсивном варианте).
При поиске в ширину нас интересуют расстояния от s, поэтому мы не перезапускаем поиск в других связных компонентах (недоступные вершины просто игнорируются).
Формат входного файла
Формат выходного файла
Ограничения
Примеры тестов
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|