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

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

Сначала пометим все вершины графа, как непосещенные. Поиск в глубину начинается с произвольной вершины графа, например с первой, обозначим ее v. При этом значение метки v меняется на противоположное (вершина уже посещалась). Затем, для каждой вершины, смежной с v, которая ранее не посещалась, рекурсивно вновь применяется поиск в глубину. Легко показать, что при этом все вершины, достижимые из начальной, то есть образующие одну компоненту связности, будут пройдены. Если некоторые вершины оказались непройденными, то граф не связан. Для полного его обхода выбираем любую еще непосещенную вершину и поиск продолжается. Очевидно, что таким образом можно не только проверять связность графа, но и подсчитывать количество компонент связности. Приведем процедуру поиска в глубину и фрагмент основной программы, решающей эту задачу. Считаем, что граф задан с помощью матрицы булевской матрицы смежности a (см. предыдущую лекцию), а метятся вершины графа с помощью массива vert: array[1..nmax] of boolean.

procedure d_f_s(v:byte);

var i:byte;

begin

{ writeln(v); или другая обработка вершины v}

vert[v]:=false;{вершина посещена}

for i:=1 to n do

if a[v,i] and vert[i] then

d_f_s(i)

end;

begin

…{заполняем матрицу смежности}

{метим все вершины как непосещенные}

fillchar(vert,sizeof(vert),true);

cnt:=0;{счетчик компонент связности}

for i:=1 to n do

if vert[i] then

begin

inc(cnt);

d_f_s(i)

end;

writeln(cnt)

end.

Подсчитаем вычислительную сложность предложенной реализации алгоритма. Так как для каждой вершины процедура d_f_s вызывается ровно один раз, а количество операций в ней пропорционально N — количеству вершин в графе, то количество операций в алгоритме есть O (N ²), а его применимость ограничена лишь размером памяти, необходимой для представления матрицы смежности. Ниже будет приведена и более эффективная реализация данного алгоритма.

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

При решении многих задач, касающихся ориентированных графов, необходим эффективный метод систематического обхода вершин и дуг орграфов. Таким методом является метод поиск в глубину. Метод поиска в глубину является основой многих эффективных алгоритмов работы с графами. Предположим, что есть ориентированный граф , в котором первоначально все вершины помечены меткой " ". Поиск в глубину начинается с выбора начальной вершины орграфа , для этой вершины метка " " меняется на метку " ". Затем для каждой вершины, смежной с вершиной и не посещаемой раньше, рекурсивно применяется поиск в глубину. Когда все вершины, которых можно достичь из вершины , будут рассмотрены, поиск заканчивается. Если некоторые вершины остались не посещенными, то выбирается одна из них и алгоритм повторяется. Этот процесс продолжается до тех пор, пока не будут обойдены все вершины орграфа .

Метод получил свое название - поиск в глубину, поскольку поиск не посещенных вершин идет в направлении вглубь до тех пор, пока это возможно. Например, пусть является последней посещенной нами вершиной. Выбираем очередную дугу (ребро), выходящую из вершины . Возможна следующая альтернатива: вершина помечена меткой " "; вершина помечена меткой " ". Если вершина уже посещалась, то отыскивается другая вершина, смежная с вершиной ; иначе вершина метится меткой " " и поиск начинается заново от вершины . Пройдя все пути, которые начинаются в вершине , возвращаемся в вершину , то есть в ту вершину, из которой впервые была достигнута вершина . Затем процесс повторяется, то есть продолжается выбор нерассмотренных дуг, исходящих из вершины , и так до тех пор, пока не будут исчерпаны все эти дуги.

Лекция № 9