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

1.Выбираем вершину v₀. Помечаем ее как текущую. Полагаем D(v₀) = 1, k = 1.

i.Пусть x – текущая вершина.

i.1.Если существует непомеченное ребро xy, то а) если y уже имеет номер, то помечаем ребро xy как обратное и продолжаем поиск непомеченного ребра, инцидентного x б) если y не имеет номера, то k++, D(y) = k, переходим в y.

i.2. Если непомеченного ребра xy не существует, то возвращаемся в вершину, из которой x получила свою метку.

k:=1, v:=v₀, D(v):=k; push(Q,v), D(v):=-1 "uÎV(G)\{v}

while (Q¹Æ)

{

с = false;

v:=top(Q);

for (uÎN(v))

if (D(u)=-1)

uv – прямое; k++; D(v)=k; push(Q,u);

c = true; break;

else

uv – обратное

if (!c)

pop(Q);

}

Утверждение 1. Прямые ребра образуют корневое остовное дерево с корнем в начальной вершине.

Утверждение 2. Обратное ребро направлено от вершины с большей меткой к вершине с меньшей меткой.

Применение поиска в глубину:

Проверка графа на связность, на двусвязность.

Граф называется двусвязным, если между любыми двумя его вершинами существуют два непересекающихся пути . Двусвязная компонента графа (или блок) – максимальный двусвязный подграф графа.

Трудоемкость - O(n+m)

Утв. Пусть V не явл-ся корнем. Тогда V точка сочленения  для некоторого ее сына s не существует ребра (x,y) что х – потомок s или =s, а y – предок V.