На этом шаге мы рассмотрим поиск в ширину.

Рассмотрим еще один способ систематического обхода всех вершин обыкновенного графа G, называемый поиском в ширину. Для описания поиска в ширину введем в рассмотрение очередь Q, элементами которой являются вершины графа G. Поиск начинается с некоторой вершины v. Эта вершина помещается в очередь Q и с этого момента считается просмотренной. Затем все вершины, смежные с v, включаются в очередь и получают статус просмотренных, а вершина v из очереди удаляется.

Более обще, пусть в начале очереди находится вершина u. Обозначим через u₁, ..., u_p вершины, смежные с u и еще непросмотренные. Тогда вершины u₁, ..., u_p помещаются в очередь Q и с этого момента считаются просмотренными, а вершина u удаляется из очереди и получает статус использованной. В этой ситуации вершина u называется отцом для каждой из вершин u_i (u = father[u_i], 1 ≤ i ≤ р). Каждое из ребер uu_i, 1 ≤ i ≤ p, будем называть древесным ребром. В тот момент, когда очередь Q окажется пустой, поиск в ширину обойдет компоненту связности графа G. Если остались непросмотренные вершины (это возможно лишь в случае, когда граф G несвязен), поиск в ширину продолжается из некоторой непросмотренной вершины.

Поиск в ширину просматривает вершины в определенном порядке. Как и раньше, этот порядок фиксируется в массиве num. Если u - отец вершин u₁, ..., u_p, то num[u_i] = num[u]+i, 1 ≤ i ≤ p (для определенности мы полагаем, что сначала в очередь помещается u₁, затем u₂ и т.д.). Для начальной вершины v естественно положить num[v] = 1.

Поиск в ширину реализует описанная ниже процедура BFS (название процедуры является аббревиатурой от англ. breadth first search). Эта процедура использует описанные ранее массивы num и father. Кроме того, она вычисляет множество всех древесных ребер Т. Массив num удобно использовать для распознавания непросмотренных вершин: равенство num[u] = 0 означает, что вершина и еще не просмотрена.

Алгоритм 4.

1.  procedure BFS(v);
2.  begin
3.    Q:= nil; Q <= v; num[v]:= i; i:= i+1;
4.    while Q  ≠ nil do
5.    begin
6.    u <= Q;
7.    for w ∈ list[u] do
8.      if num[w] = 0 then
9.      begin
10.        Q <= w; father[w]:= u;
11.        num[w]:= i; i:= i +1; T:= T ∪ {uw};
12.     end
13.   end
14. end
15. begin
16.   i:= 1; T:= 0;
17.   for v ∈ V do  num[v]:= 0;
18.   for v ∈ V do
19.     if num[v] = 0 then
20.     begin father[v]:= 0; BFS(v) end
21. end.

Полезно сравнить процедуру BFS с нерекурсивной версией процедуры DFS и убедиться, что по-существу, первая процедура получается из второй заменой стека на очередь.

Заметим также, что, применяя этот алгоритм к связному графу G, можно цикл в строках 18-20 заменить однократным обращением к процедуре BFS.

Теорема 7.

Пусть G - связный (n, m)-граф. Тогда

поиск в ширину просматривает каждую вершину в точности один раз;
поиск в ширину требует O(n + m) операций;
подграф (V, Т) графа G является деревом.

Эта теорема доказывается аналогично теореме 1.

В связном графе G поиск в ширину из вершины v строит корневое дерево с множеством ребер Т и корнем v. Это корневое дерево называется деревом поиска в ширину или, короче, b-деревом. Аналогично, если G произвольный обыкновенный граф, то поиск в ширину строит b-дерево в каждой компоненте связности графа G; объединяя эти деревья, мы получим остовный лес графа G, называемый в дальнейшем b-лесом этого графа.

На рисунках 1 и 2 показаны связный граф G и его b-дерево.

Рис.1. Связный граф

Рис.2. b-дерево

Пусть в графе G проведен поиск в ширину. Занумеруем вершины графа в соответсвии с порядком, в котором поиск в ширину обходит вершины. А именно, обозначим вершины графа через w_i, 1 ≤ i ≤ n, считая, что num[w_i] = i.

В леммах 1-5 изучаются некоторые свойства поиска в ширину, отличающие его от поиска в глубину.

Лемма 1.: Вершина w_k является отцом вершины w₁ тогда и только тогда, когда k = min{i|w_i ∈ list(w_i)}.

Из леммы 1 следует, что ребро, не являющееся древесным, никогда не соединяет предка с потомком в b-дереве; по этой причине такие ребра графа G будем называть поперечными ребрами.

Лемма 2.: Пусть вершины w_k, w_l являются отцами вершин w_p, w_q соответственно. Если р ≤ q, то k ≤ l.
Доказательство.: Предположим, что l < k. Из этого неравенства следует, что вершина w_l будет использована раньше, чем w_k. Поэтому вершина w_q, являющаяся сыном w_l, попадет в очередь раньше, чем сын w_p вершины w_k. Отсюда q < p, что невозможно.

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

Лемма 3.

Если 1 ≤ р < q ≤ n, то h(w_p) ≤ h(w_q).

Доказательство.

Требуемое неравенство очевидно, если w_p - корень b-дерева. Пусть w_p не является корнем. Обозначим через s наибольший из номеров p и q и применим индукцию по s. Рассмотрим вершины w_k, w_l, являющиеся отцами вершин w_p, w_q соответственно. В силу леммы 2 имеем k < l. Ясно, что к вершинам w_k, w_l применимо предположение индукции. Следовательно, h(w_k) < h(w_l). Отсюда

h(w_p) = h(w_k) + 1 ≤ h(w_l) +1 = h(w_q).

Поскольку база индукции (при s = 2), очевидно, выполняется, лемма доказана.

Лемма 4.

Если вершины w_p и w_q смежны в графе G и p < q, то h(w_q) - h(w_p) < 1.

Доказательство.

Пусть w_l - отец вершины w_q. Тогда из леммы 1 следует, что l < р. В силу леммы 3 имеем

h(w_l) ≤ h(w_p) ≤ h(w_q).

Поскольку h(w_q) - h(w_l) = 1, получаем

h(w_q) - h(w_p) ≤ h(w_q) - h(w_t) = 1.

Лемма 5.

Расстояние в графе G от вершины w₁ (т.е. от корня b-дерева) до произвольной вершины u равно h(u).

Пусть v₀ - корень b-дерева. Лемма (5) показывает, что простая (v₀, u)-цепь в b-дереве является кратчайшей (v₀, u)-цепью в графе G. Отсюда следует, что поиск в ширину может быть применен для решения следующей задачи: в связном графе G найти кратчайшую цепь, соединяющую данную вершину v₀ с произвольной вершиной u.

Для решения этой задачи необходимо в графе G из вершины v₀ провести поиск в ширину, а затем, используя массив father, построить требуемую кратчайшую цепь.

На следующем шаге мы рассмотрим алгоритм отыскания эйлеровой цепи в эйлеровом графе.

Предыдущий шаг Содержание Следующий шаг