3. Обход графов

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

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

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

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

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

Для наглядности будем считать, что в процессе работы алгоритма вершины графа могут быть белыми, серыми и черными. Вначале они все белые, затем в ходе работы алгоритма белая вершина может серой, а серая – черной.

Если вершина имеет серый или черный цвет, то она уже посещалась алгоритмом. Различие между серыми и черными вершинами используется для управления порядком обхода: серые вершины образуют «линию фронта», а черные – «тыл». Т.е. поддерживается такое свойство: если u черная вершина, то она может соединяться ребром только с черной или серой вершиной. Только серая вершина может иметь смежные белые (непосещенные) вершины.

Вначале работы алгоритма дерево поиска состоит только из корня – начальной вершины s, u=s. Как только алгоритм обнаруживает новую белую вершину v, смежную с ранее найденной вершиной u, вершина v вместе с ребром u->v добавляется к дереву поиска, становясь сыном вершины u, а u становится родителем v. Каждая вершина обнаруживается лишь однажды, так что двух родителей у нее быть не может.

Обычно процедуру, реализующую этот алгоритм, называют BFS(), что является сокращением от breadth-first search – поиск в ширину.

Для каждой вершины графа будем дополнительно хранить цвет и ее предшественника в массивах color[] и pi[]. Если предшественника нет или он еще не обнаружен, то pi[]=NULL.

Кроме того расстояние от s до u записывается в массив d[u]. Также будем использовать очередь Q для хранения серых вершин.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

BFS(GRAPH G, vertex s) { QUEUE Q; /* очередь для вершин */ Vertex u, v; For (для каждой вершины u графа G, кроме s ) { color[u]=WHITE; /*вершины становятся белыми */ pi[u]=NULL; /* родителем всех вершин считается NULL */ d[u]=MAXDISTANCE; /* все расстояния максимально возможные */ } /* for */ color[s]=GRAY; d[s]=0; pi[s]=NULL; ENQUEUE(s,Q); /* поместить s в очередь Q */ While(EMPTY(Q)) /* пока очередь не пустая */ { u=FRONT(Q); /* извлекаем первый элемент из очереди */ for(для всех вершин v смежных с u) if (color[v]==WHITE) { color[v]=GRAY; d[v]=d[u]+1; pi[v]=u; ENQUEUE(v,Q); /* поместить v в очередь Q */ } /*if*/ DEQUEUE(Q); /* удаляем элемент из очереди / color[u]=BLACK; } }

Основной цикл программы (строки 16-29) выполняется пока очередь не пуста, т.е. существуют серые вершины (вершины, которые уже обнаружены, но списки смежности которых еще не просмотрены). В строке 18 первая такая вершина помещается в u. Цикл 19-26 просматривает все смежные с ней вершины. Обнаружив среди них белую вершину, мы делаем ее серой (строка 22) объявляем u ее родителем (строка 24) и устанавливаем расстояние на 1 больше чем у родителя (строка 23). Эта вершина добавляется в хвост очереди Q (строка 25). После этого можно удалить u из очереди (строка 27), перекрасив эту вершину в черный цвет (строка 28).

Т.О., в результате работы программы получим два массива pi[] с родителем для каждой вершины и d[] с кратчайшим расстоянием до s.