сти можно выяснить, содержит ли ориентированный граф «сток» (sink) - вершину, в которую ведут рёбра из всех других вершин и из которой не выходит ни одного ребра. 23.1-7

Назовем матрицей инцидентности (incidence matrix) ориентированного графа G = (E,V) матрицу В = (68j) размера \V\ X \Е\, в которой

-1, если ребро j выходит из вершины i, 1, если ребро j входит в вершину г, О в остальных случаях.

Каков смысл элементов матрицы ВВТ? (Здесь Вт - транспонированная матрица.)

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

Поиск в ширину (breadth-first search) - один из базисных алгоритмов, составляющий основу многих других. Например, алгоритм Дейкстры поиска кратчайших путей из одной вершины (глава 25) и алгоритм Прима поиска минимального покрывающего дерева (раздел 24.2) могут рассматриваться как обобщения поиска в ширину.

Пусть задан граф G = (V, Е) и фиксирована начальная вершина (source vertex) s. Алгоритм поиска в ширину перечисляет все достижимые из s (если идти по рёбрам) вершины в порядке возрастания расстояния от s. Расстоянием считается длина минимального пути из начальной вершины. В процессе поиска из графа выделяется часть, называемая «деревом поиска в ширину» с корнем s. Она содержит все достижимые из s вершины (и только их). Для каждой из них путь из корня в дереве поиска будет одним из кратчайших путей (из начальной вершины) в графе. Алгоритм применим и к ориентированным, и к неориентированным графам.

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

Для наглядности мы будем считать, что в процессе работы алгоритма вершины графа могут быть белыми, серыми и чёрными. Вначале они все белые, но в ходе работы алгоритма белая вершина может стать серой, а серая - чёрной (но не наоборот). Повстречав новую вершину, алгоритм поиска красит её, так что окрашенные (серые или чёрные) вершины - это в точности те, которые уже обнаружены. Различие между серыми и чёрными вершинами используется алгоритмом для управления порядком обхода: серые вершины образуют «линию фронта», а чёрные - «тыл». Более точно, поддерживается такое свойство: если (и, v) £ Ежи чёрная,

то v - серая или чёрная вершина. Таким образом, только серые вершины могут иметь смежные необнаруженные вершины.

Вначале дерево поиска состоит только из корня - начальной вершины s. Как только алгоритм обнаруживает новую белую вершину v, смежную с ранее найденной вершиной и, вершина v (вместе с ребром (и, v)) добавляется к дереву поиска, становясь ребёнком (child) вершины и, а и становится родителем (parent) v. Каждая вершина обнаруживается только однажды, так что двух родителей у неё быть не может. Понятия предка (ancestor) и потомка (descendant) определяются как обычно (потомки - это дети, дети детей, и т.д.). Двигаясь от вершины к корню, мы проходим всех её предков.

Приведенная ниже процедура BFS (breadth-first search - поиск в ширину) использует представление графа G = (V, Е) списками смежных вершин. Для каждой вершины и графа дополнительно хранятся её цвет color[u] и её предшественник тг[и]. Если предшественника нет (например, если и = s или и ещё не обнаружена), тг[и] = NIL. Кроме того, расстояние от s до и записывается в массив d[u]. Процедура использует также очередь Q (FIFO, раздел 11.1) для хранения множества серых вершин.

BFS$(G,s)$

1for (для) всех вершин $u\in V[G]-\{s\}$

2do $color[u] \leftarrow$ БЕЛЫЙ

3$d[u] \leftarrow \infty$

4$\pi [u] \leftarrow$ MIL

5$color[s] \leftarrow$ СЕРЫЙ

6$d[s] \leftarrow 0$

7$\pi [s] \leftarrow$ MILL

8$Q\leftarrow \{s\>$

9while $Q\ne \emptyset$

10do $u\leftarrow head[Q]$

11for (для) всех $v\in Adj[u]$

12do if $color[v]=$ БЕЛЫЙ

13then $color[v]\leftarrow$ СЕРЫЙ

14$d[v]\leftarrow d[u]+l$

15$\pi[v]\leftarrow u$

16Enqueue($Q,v$)

17Dequeue($Q$)

18$color[u]\leftarrow$ ЧЕРНЫЙ

На рис."23.3 привед\"~~а5н пример исполнения процедуры \textsc{BFS>.

\begin{figure}

\caption{

23.3

Исполнение процедуры \textsc{BFS} для неориентированного

графа. Р\"~~а5бра формируемого дерева показаны серыми.

Внутри каждой вершины $и$ указано значение $d[u]$.

Показано состояние очереди $Q$ перед каждым повторением

цикла в строках 9-18. Рядом с элементами очереди показаны расстояния

от корня.

>

\end{figure}

В строках 1-4 все вершины становятся белыми, все значения $d$ бесконечными, и родителем всех вершин объявляется \textsc{nil}. Строки 5-8 красят вершину $s$ в серый цвет и выполняют связанные с этим действия: в строке 6 расстояние $d[s]$ объявляется равным $0$, а в строке $7$ говорится, что родителя у $s$ нет. Наконец, в строке $8$ вершина $s$ помещается в очередь $Q$, и с этого момента очередь будет содержать все серые вершины и только их.

Основной цикл программы (строки 9-18) выполняется, пока очередь непуста, то есть существуют серые вершины (вершины, которые уже обнаружены, но списки смежности которых еще не просмотрены). В строке 10 первая такая вершина помещается в $и$. Цикл \textbf{for} в строках 11-16 просматривает все смежные с ней вершины. Обнаружив среди них белую вершину, мы делаем е\"~~а5 серой (строка 13), объявляем $и$ е\"~~а5 родителем (строка 15) и устанавливаем расстояние равным $d[u]+l$ (строка 14). Наконец, эта вершина добавляется в хвост очереди $Q$ (строка 16). После этого уже можно удалить вершину $и$ из очереди $Q$, перекрасив эту вершину в ч\"~~а5рный цвет (строки 17-18).

Анализ

Начн\"~~а5м с более простого --- оценим время работы описанной

процедуры. В процессе работы вершины только темнеют, так что каждая вершина клад\"~~а5тся в очередь не более одного раза (благодаря проверке в строке 12). Следовательно, и вынуть е\"~~а5 можно только один раз. Каждая операция с очередью требует $0(1)$ шагов, так что всего на операции с очередью уходит время $0(V)$. Теперь заметим, что список смежных вершин просматривается, лишь когда вершина извлекается из очереди, то есть не более одного раза. Сумма длин всех этих списков равна $Е$, и всего на их обработку уйдет время $0(Е)$. Инициализация требует $0(V)$ шагов, так что всего получается $0(V+E)$. Тем самым время работы