Поиск на графах

На практике часто возникают задачи, связанные с прохождением по вершинам графа. Например, необходимо ответить на вопрос: достижима ли вершина d из вершины a? То есть, существует ли путь из а в d. Если исходный граф неориентированный, то для ответа на данный вопрос достаточно определить, принадлежат ли вершины а и d одной связной компоненте. Выделить связные компоненты можно с помощью алгоритма Краскала. Если после завершения работы алгоритма Краскала вершины а и d принадлежат разным деревьям покрывающего леса (разным букетам – в терминах, используемых при формулировке алгоритма Краскала в разд. 5.1), то пути из вершины а в вершину d не существует, в противном случае - путь существует.

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

Существует два способа организации обхода: поиск в глубину и поиск в ширину.

Поиск в глубину

Поиск в глубину на графе G =(V, E) осуществляется по следующим правилам:

1. Начинаем поиск с произвольной вершины r. В качестве текущей вершины v берем вершину r.

2. Из текущей вершины v двигаемся в любую, ранее не пройденную вершину w, если такая вершина найдется (если вершины w нет, см. пункт 3). Запоминаем дугу, по которой мы попали в вершину w. В качестве текущей вершины v берем вершину w.

3. Если из вершины v мы не можем попасть в ранее не пройденную вершину w, то возвращаемся в вершину x, из которой мы попали в v. В качестве текущей вершины v берем вершину x.

4. Процесс поиска (пункты 2, 3) заканчивается, когда мы пытаемся вернуться назад из вершины, с которой начался поиск (вершина r).

Поиск в глубину проиллюстрирован на рис. 5.4.

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

При поиске в ширину порядок исследования дуг графа отличается. Поиск в ширину производится следующим образом:

1. Начинаем поиск с произвольной вершины r. Формируем множество текущих вершин A, включив в него вершину r.

2. Идем в ранее не пройденные вершины по всем дугам с начальной вершиной из множества A. Запоминаем эти дуги. Формируем множество A, включив в него конечные вершины пройденных дуг.

3. Процесс поиска (пункт 2) заканчивается, когда множество A станет пустым.

Поиск в ширину проиллюстрирован на рис. 5.5.

Упражнения:

1. Реализуйте алгоритм поиска в глубину и ширину. Оцените трудоемкость программ.

Указания:

Для хранения последовательности вершин обхода при использовании техники поиска в глубину следует использовать стек, а поиска в ширину – очередь.

Дуги, по которым осуществляется обход вершин графа, при использовании любой техники поиска образуют ориентированное дерево с корнем в начальной вершине. Это следует из того, что начальная вершина единственная и движение в ходе поиска не осуществляется в ранее пройденные вершины. Для хранения такого дерева целесообразно использовать массив P длины n, где n – число вершин графа. Если вершины графа пронумерованы числами 1,2,…, n, то элементы массива P определяются следующим образом: P_i =0, если i – начальная вершина (корень дерева); в противном случае P_i = k, где k – вершина, предшествующая вершине i на пути из корня в вершину i.

2. Используйте технику обхода в глубину и в ширину для построения алгоритмов выделения связных компонент графа.