Шаг 4.
Алгоритмы поиска на графах.
Поиск в ширину

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

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

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

    Поиск в ширину просматривает вершины в определенном порядке. Как и раньше, этот порядок фиксируется в массиве num. Если u - отец вершин u1, ..., up, то num[ui] = num[u]+i, 1 ≤ i ≤ p (для определенности мы полагаем, что сначала в очередь помещается u1, затем u2 и т.д.). Для начальной вершины 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 проведен поиск в ширину. Занумеруем вершины графа в соответсвии с порядком, в котором поиск в ширину обходит вершины. А именно, обозначим вершины графа через wi, 1 ≤ i ≤ n, считая, что num[wi] = i.

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

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

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

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

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

Лемма 3.
Если 1 ≤ р < q ≤ n, то h(wp) ≤ h(wq).
Доказательство.
Требуемое неравенство очевидно, если wp - корень b-дерева. Пусть wp не является корнем. Обозначим через s наибольший из номеров p и q и применим индукцию по s. Рассмотрим вершины wk, wl, являющиеся отцами вершин wp, wq соответственно. В силу леммы 2 имеем k < l. Ясно, что к вершинам wk, wl применимо предположение индукции. Следовательно, h(wk) < h(wl). Отсюда

h(wp) = h(wk) + 1 ≤ h(wl) +1 = h(wq).

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

Лемма 4.
Если вершины wp и wq смежны в графе G и p < q, то h(wq) - h(wp) < 1.
Доказательство.
Пусть wl - отец вершины wq. Тогда из леммы 1 следует, что l < р. В силу леммы 3 имеем

h(wl) ≤ h(wp) ≤ h(wq).

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

h(wq) - h(wp) ≤ h(wq) - h(wt) = 1.

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

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

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

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




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