logo
РГР_ПО_ДИСКРЕТКЕ

2.1. Алгоритмы поиска

Алгоритмы поиска в графе (или алгоритмы обхода графа) представляют методы обхода всех вершин и рёбер графа. Во многих случаях они являются основой разработки других быстрых алгоритмов на графах.

Пусть G - неограф и притом связный. В процессе поиска в глубину вершинам G присваиваются номера, а рёбра помечаются. Вначале рёбра не помечены, вершины не имеют номеров. Произвольной вершине присваивается номер P(v0)=1, выбирается произвольное ребро (v0,v1) и помечается как «прямое», а вершина v1 получает номер P(v1)=2.

После этого переходим в вершину v1. Пусть на каком-то шаге процесс привёл в вершину vk и P(vk)=k+1. Далее возможны следующие варианты:

  1. Имеется непомеченное ребро (vk,). Если у вершины уже есть номер, то ребро (vk,) помечается как «обратное» и продолжается поиск неотмеченного ребра, инцидентного vk. Если же вершина не имеет номера, то P()=k+2, ребро (vk,) помечается как «прямое» и переходят в вершину .

  2. Все рёбра, инцидентные вершине vk, помечены. В этом случае идёт возврат в вершину, из которой vk получила свой номер.

Процесс заканчивается, когда все рёбра будут помечены и произойдет возврат в v0.

Рассмотрим один из алгоритмов, обеспечивающих указанную трудоёмкость.

Граф задаётся списками смежности, то есть Nv – список вершин, смежных v. Вершина, получившая номер P, включается в список и исключается из него сразу, как только произойдёт возвращение из этой вершины. Результат работы алгоритма – четыре списка: P, F, T и B. P(v)-P-номер вершины v; F(v) – имя вершины, из которой вершина v получила свой номер; T и B – соответственно, списки «прямых» и «обратных» рёбер графа G. Эти рёбра получают ориентацию в результате работы алгоритма А1: если ребро XY помечается из вершины X как «прямое», то в Т заносится дуга (X,Y); если как «обратное», его дуга (X,Y) заносится в В.

Алгоритм поиска в глубину в неориентированном связном графе:

Шаг 1. P(v0):=1; (1):=v0; Т:=; В:=; F(v0):=; k:=1; p:=1,(k- последний присвоенныйP-номер,p-указатель конца списка, т.е.(р)- имя последней вершины из);

Шаг 2. v:= (р)(р-исследуемая вершина);

Шаг 3. Просматривая список Nv, найти такую вершину, что реброvне помечено и перейти к шагу 4. Если таких вершин нет, то перейти к шагу 5.

Шаг 4. Если вершина имеетР-номер, то пометить реброvкак «обратное» и занести дугу(v,)в списокВ. Перейти к шагу 3 и продолжить просмотр спискаNv. Иначеk:=k+1,Р()=k, F():=v,реброvпометить как «прямое» и дугу(v,)занести в списокТ; р:=р+1, (р):=(вершинаполучилаР-номер и занесена в). Перейти к шагу 2.

Шаг 5. р:=р+1(вершинаvвычеркнута из). Еслир=0, то конец. Иначе перейти к шагу 2

Пример: задан граф G и списки смежности (рис. 2.1), результат работы алгоритма приведен на рис 2.2.

Рис 2.1

Рис 2.2

N1=(3,2,5), N2=(1,5,4), N3=(1,5), N4=(2,5), N5=(1,2,3,4,6,7), N6=(5,7),

N7=(5,6)._________

P()=(1,2,3,4,5,6,7).

P(1)=1; Q(1)=1; T=; B; F(1)=.

N7=(5,6)._________

P()=(1,2,3,4,5,6,7).

1) P(1)=1; Q(1)=1; T=; B; F(1)=.

  1. P(3)=2; Q(2)=3; F(3)=1; T=(1,3).

  2. P(5)=3; Q(3)=5; F(5)=3; T=(1,3),(3,5).

  3. B=(5,1).

  4. P(2)=4; Q(4)=2; F(2)=5; T=(1,3),(3,5),(5,2).

  5. P(4)=5; Q(5)=4; F(4)=2; T=(1,3),(3,5),(5,2),(2,4).

  6. B=(5,1),(4,5).

  7. B=(5,1),(4,5),(2,1).

Одна из задач, решаемых с помощью этого алгоритма – выделение связных компонент графа. Для этого просматривается список вершин G и выполняются действия: если вершина vi имеет номер, то перейти к следующей. Иначе положить v0=v1, P(v0)=k+1, где k-последний присвоенный номер и т.д. После окончания поиска (т.е., выделения компоненты, содержащей vi) продолжить просмотр списка, перейти к вершине vi+1. Различать вершины разных компонент можно, например, по их номерам, если для каждой компоненты запомнить номер P.

Таким образом, дуги множества Т образуют ориентированный остов с корнем в вершине v0.