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

При решении прикладных задач часто возникает необходимость обхода вершин графа, связанная с поиском вершины, удовлетворяющей определенным свойствам. Обход графа – это некоторое систематическое перечисление его вершин (и/или ребер). Обычно обход по графу сопровождается нумерацией вершин графа в том порядке, в котором они отмечаются, а также определенной маркировкой ребер (или дуг) графа. Из обходов графа наиболее известны поиск в глубину и поиск в ширину, использующие локальную информацию (списки смежности вершин). Алгоритмы поиска в глубину и ширину лежат в основе многих конкретных алгоритмов на графах. Опишем стратегии поиска в глубину и ширину.

3.1. Поиск в глубину на графе

Поиск в глубину осуществляется следующим образом. Пусть поиск начинается с некоторой начальной вершины и мы достигли некоторой вершины (в начале процедуры ). Отмечаем вершину и просматриваем вершины из ее списка смежности (т. е. элементы множества ). Если в этом списке существует хотя бы одна неотмеченная вершина, то идем из первой вершины списка по ребру – «ныряем» вглубь, откладывая анализ других элементов списка «на потом» (в случае ориентированного графа, находясь в вершине , следует выбирать только дугу , выходящую из вершины ). Если же в списке неотмеченных вершин нет, то возвращаемся из вершины в вершину , из которой в нее попали, и исследуем список смежности вершины . Процедура заканчивается, когда вернемся в начальную вершину и все вершины окажутся отмеченными, либо окажется, что неотмеченные вершины есть, но они несмежные с вершиной . В последнем случае возможно продолжение поиска из новой вершины или остановка. Для связного графа описанная процедура определяет единственный обход графа, а в случае несвязного графа – его компоненту, содержащую вершину . Для получения полного обхода несвязного графа необходимо начинать процесс в каждой связной компоненте. С помощью этого метода можно также определить число компонент связности графа.

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

Алгоритм 3.1.1 (поиск в глубину).

Вход: граф G = (V, E), представленный списками смежности вершин.

Выход: последовательность обхода вершин.

1. procedure

2. begin

3.

4. for do

5. if then

6. begin

7. ; father

8. end

9. else if and father then

10.

¹ DFS – depth first search

11. end;

12. begin

13. ;

14. for do num ;

15. for do

16. if then

17. begin

18. father

19. end

20. end.

Алгоритм поиска в глубину в графе G начинается с некоторой начальной вершины (с этого момента вершина считается просмотренной). Далее алгоритм просматривает вершины графа G в определенном порядке. Для того чтобы зафиксировать этот порядок используется массив . При этом естественно считать, что , если начальная вершина, и , если вершина просматривается сразу после того, как просмотрена вершина u. Равенство означает, что вершина еще не просмотрена. Через father[u] обозначается та вершина x, из которой попали в вершину u. Ребро в этом случае называется древесным; T – множество древесных ребер. Все остальные ребра графа называются обратными, и их множество обозначается через B.

Пример 3.1.1. Результат поиска в глубину на графе и орграфе проиллюстрирован на рисунках 3.1.1 (a, б). При поиске помечаем вершины, присваивая им номера. Каждая новая вершина получает номер на единицу больший, чем текущая. Вершине присвоен номер 1. Номера остальных вершин, присвоенные им в процессе поиска, приведены на графах.

Подробнее рассмотрим обход в глубину на простом графе (рис. 3.1.1, а). В качестве начальной вершины взята вершина . Список смежности вершины . Отмечаем вершину и просматриваем вершины из ее списка смежности . В этом списке вершина неотмеченная, отмечаем ее и просматриваем список смежности вершины : , причем вершина – отмеченная. Поэтому отмечаем вершину . Далее , отмечаем вершину , список смежности которой , и из вершины идем в неотмеченную вершину . . Отмечаем вершину . В списке смежности неотмеченных вершин нет, поэтому возвращаемся в вершину и идем из нее в вершину . Обход графа в глубину закончен, так как неотмеченных вершин нет.