Алгоритмы на графах Тема лекции: Поиск по графу

лекции:
Поиск по графу

леса)
из текущей вершины (на рисунке - красная) доступны смежные

(на рисунке - синие) и ещё не помеченные;
они помечаются и заносятся в специальное множество;

из множества извлекается очередная вершина, она посещается (обрабатывается), и процесс повторяется, пока множество не станет пустым.

// рабочее множество вершин графа
bool newVert [n];
global setVert V; //множество вершин

графа G=(V,E), Card(V)=n
listVert adj [n]; //списки смежности
for (∀v∈V) newVert[v] = true; //пометить вершины как необследованные
Q = { v0 }; NewVert[v0] = false;
while (Q ≠ { }) {
v = произвольный элемент из Q;
удалить v из Q;
посетить ( v );
for (∀ u ∈ Adj[v]) {
if (NewVert[u]) {
Q = Q + {u};
NewVert[u] = false;
} // if
}//for
// вершина v - использована
} //while
} //search

O(n + m)
каждая вершина один раз заносится в множество и один раз исключается
Каждое ребро при анализе пометки проверяется дважды

Vert );
var Q : SetVert;
NewVert : Array [1..n] of

Boolean;
global V : SetVert; {множество вершин графа G=(V,E), Card(V)=n }
Adj: array  [1..n] of  ListVert; { списки смежности }
begin
for ∀ v ∈ V do NewVert[v] := True; { - пометить все вершины как необследованные }
Q := { v0 }; NewVert[v0] := False;
While Q ≠ { } do
begin
v := произвольный элемент из Q; удалить v из Q;
посетить ( v );
for ∀ u ∈ Adj[v] do
if NewVert[u] then
begin
Q := Q + {u}; NewVert[u] := False
end {if-for}
{ вершина v - использована }
end {while}
end { Search }

O(n + m)
каждая вершина один раз заносится в множество и один раз исключается
Каждое ребро при анализе пометки проверяется дважды

)

Множество Q реализуется очередью q (раньше посетили - раньше использовали).
Заодно

строится остовное дерево (T – множество древесных ребер)

search_BFS (vert v0)
{ queueVert q;
bool newVert [n];
global setVert V; //множество вершин графа G=(V,E), Card(V)=n
listVert adj [n]; //списки смежности
setBr T; // множество ветвей (branch) дерева

вершины как необследованные
Create(q); 
q ← v0;
newVert[v0] =false;
T =

{ };
while ( !Null( q )) {
v ← q;
посетить ( v );
for (∀u∈Adj[v] ) {
if (newVert[u] ) { 
q ← u;
newVert[u] =false;
T = T + { };
// predVert[u] = v
} //if
} //for вершина v - использована
} //while
} // searchBFS

∈ V do  NewVert[v] := True;
{ - пометить все

вершины как необследованные }
Create(q);  q ← v0;
NewVert[v0] := False; T := { };
While not Null( q ) do
begin 
v ← q; посетить ( v );
for  ∀ u ∈ Adj[v]  do
if NewVert[u]  then
begin 
q ← u; NewVert[u] := False;
T := T + { }
{ PredVert[u] := v }
end {if-for}
{ вершина v - использована }
end {while}
end { BFS }

= (V, E) и
(V, T) – BFS-остов графа G.
Тогда путь

в (V, T) из v∈V до корня остова r является кратчайшим путем из v в r в графе G.
Док-во по индукции (по этапам волны или по порциям записи в очередь).

//множество вершин графа G=(V,E), Card(V)=n
listVert adj [n];

//списки смежности
setBr T; // множество ветвей (branch) дерева
посетить v;
newVert[v] =false;
for (∀u∈Adj[v] ) 
if (newVert[u]) searchDFS(u);
//v - использована
} // searchDFS

ПОИСК В ГЛУБИНУ
( Depth First Search - DFS )
Q = Stack. Можно сразу рекурсивно.

DFS )
// cобственно  поиск в глубину  в графе G=(V,E)
{…
setVert V;

//множество вершин графа G=(V,E), Card(V)=n
listVert adj [n]; //списки смежности
for (∀v∈V) newVert[v] = true;
// - пометить все вершины как необследованные
for (∀v∈V)  
if  (newVert[v] ) searchDFS(v);
}

деле это очень гибкий и мощный алгоритм (схема), который можно

применять для решения многих трудных задач обработки графов

(Седжвик)

07.04.2014

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

графа G=(V,E), Card(V)=n }
int numComp [n1];
//вершина помечается номером своей

связной компоненты
int iC ; //номер связной компоненты

for (∀v∈V) numComp[v] = 0;
// - пометить все вершины как необследованные
iC = 0;
for (∀v∈V)
if  (numComp[v] == 0) {
iC++;
comp(v);
} //if
} // for
}

связных компонент графа

comp (vert v)
{global int numComp [n1];
listVert adj

[n]; //списки смежности
iC : Num; //номер связной компоненты
numComp[v] = iC;
for (∀u∈Adj[v])
if  (numComp[u] == 0) comp(u);
// v - использована
} //comp

закончен!

графа:
Прямые (древесные)
Обратные (к ранее пройденным вершинам)

лекции 5, решающий задачу связности, тоже строит связные компоненты
Алгоритм DFS-ПВГ

сложности O (n +m) эффективнее.
Динамический алгоритм эффективнее в ситуации, когда ребра графа добавляются последовательно, т.к. не требует заново применять ПВГ.

поиске в глубину ( Tree of Depth First Search -TDFS )
treeDFS

(vert v, vert u)
{ // посещаем вершину v и т.д.; u = Отец(v)
global
int numVert [n];
listVert Adj [n]; // списки смежности
int iV; /*текущий порядковый номер посещения вершины*/
setBrT; // множество ветвей остовного дерева
setBr B; // множество хорд (обратных ребер)

iV;
for (∀w∈Adj[v]) {
if (numVert[w]==0) {
// -

ребро (ветвь) остовного дерева
T = T + { };
treeDFS( w, v);
}
else // w - уже посещалась
if ((numVert[w] < NumVert[v]) && (w!=u))
// - обратное ребро (хорда) }
B = B + { };
}// v - использована }
}// treeDFS

V; //множество вершин графа G=(V,E), Card(V)=n
int numVert [n];

listVert Adj [n]; // списки смежности
int iV; //текущий порядковый номер посещения вершины setBrT; // множество ветвей остовного дерева
setBr B; // множество хорд (обратных ребер)

for (∀v∈V) numVert[v] = 0;
// - пометить все вершины как необследованные
iV = 0;
T = { }; B = { };
for (∀v∈V)
if (numVert[v]==0) treeDFS(v, v );
}

использования
Обход закончен!

графа, в т. ч. построить остов и обратные ребра:
Начиная

с любой другой вершины
Изменив списки смежности (порядок элементов в списке)

Построение «глубинного» остовного дерева пример

– DFS-остов графа G = (V, E) и пусть {u,

v} ∈ E. Тогда либо u потомок v (в дереве), либо v потомок u.

Доказательство.
Пусть v посещена раньше, чем u. По завершении treeDFS(v) будет numVert[v] < numVert[u], т.к. {u,v} ∈ E. Но это значит, что в TDFS добавились ребра, содержащие путь из v в u. Отсюда следует, что v лежит на пути от корня в u, т.е. u потомок v.
Аналогично рассуждаем в случае, если u посещена раньше, чем v.

раньше, чем u
numVert[v] < numVert[u]
r – корень TDFS


v






u



r
Свойство

TDFS-остова (глубинного остовного дерева)

вершины
f[v] - номер использованной (завершенной – finish) вершины
t – такт

времени (шаг алгоритма)
Единая нумерация:
t++; p[v] = t;
…
t++; f[v] = t;

07.04.2014

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

из трех утверждений:
Отрезки [p[u],f[u]] и [p[v],f[v]] не пересекаются, и ни

u не является потомком v в DFS-лесу, ни v не является потомком u.
Отрезок [p[u],f[u]] полностью содержится в отрезке [p[v],f[v]], и u является потомком v в DFS-дереве.
Отрезок [p[v],f[v]] полностью содержится в отрезке [p[u],f[u]], и v является потомком u в DFS-дереве.
================================================
v - потомок u , ттогда, когда p[u] < p[v] < f[v] < f[u]

07.04.2014

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

(2 (3 (4 (5 (6 (7 17) (8 28) 36)

(9 49) 55) 64) 73) 82) 91)

(3 (4 (5 (6 (7 8) (9 10) 11) (12

13) 14) 15) 16) 17) 18)

графах
A ⇒ B
Пусть (V, T) – DFS-остов графа G =

(V, E). Пусть {u, v} ∈ E. Тогда либо u потомок v (в дереве), либо v потомок u.

? B ⇒ A
Пусть (V, T) – DFS-остов графа G = (V, E). Пусть либо u потомок v (в дереве), либо v потомок u. Тогда {u, v} ∈ E

? ¬A ⇒ ¬B
Пусть (V, T) – DFS-остов графа G = (V, E). Пусть {u, v} ∉ E. Тогда ни u не есть потомок v (в дереве), ни v не есть потомок u.

¬B ⇒ ¬A

V - множество вершин заданного графа G=(V,E)

E - множество ребер заданного графа G=(V,E)
D [1..n,1..n] - матрица весов (или ф-ия D(.,.) )
Выход: T - множество ребер МОД
Рабочие: C - множество связных компонент графа (V,T), т.е. леса;
C = {S1,...,Sk}, где Sj – связная компонента леса, т.е. дерево
Кратч[1..n] – массив ребер; Кратч[i] - ребро, кратчайшее из всех ребер, имеющих ровно один конец (вершину) в дереве (в связной компоненте) Si=(Vi,Ti);
Min[1..n] - вспомогательный массив для определения Кратч[i]

v∉V(a)}
W[b, c] = min {W[u, v]: u∈V(b), v∉V(b)}
W[c, a]

= min {W[u, v]: u∈V(c), v∉V(c)}

(W[b, c] < W[a, b]) &
(W[c, a] < W[b, c]) →
(W[c, a] < W[a, b]) !?!?

Это в случае, когда все веса различны

Пусть правильно построен некоторый остовный лес.
Находим Кратч[i] для всех поддеревьев и добавляем их.
Определяем получившиеся связные компоненты.
Итерацию повторяем.

a] = W[b, c]) & (W[c, a] = W[a, b])

Цикл !?!?

Разрыв цикла
При выборе минимума в случае равных весов выбирать ребро, соединяющее с компонентой, имеющей меньший номер.
Например, a < b < c.
Тогда компонента с максимальным номером (c) не будет выбрана (при равных весах)

{
// этап:
for (∀Si∈C) min[i]=+∞;
Для ∀Si∈C

найти Кратч[i] – кратч. из всех ребер, имеющих ровно один конец в дереве Si=(Vi,Ti) /*см. след.сл.*/
for (∀Si∈C) T = T + { Кратч[i] } ;
Найти множество C связных компонент графа (V,T);
} //while
/*Примечание: если при нахождении связных компонент вычислен массив numComp[ ] (см.сл.13-14),
то i и j, используемые далее, определяются так:
i =numComp[u]; j =numComp[v] */
}

Детализировано на следующем слайде

что (u ∈ Si) & (v ∈ Sj);
if

(i!=j) {
if (d(u,v) < min[i]) {
min[i] = d(u,v);
Кратч[i] ={u,v};
};
if (d(u,v) < min[j] ) {
min[j] := d(u,v);
Кратч[j] := {u,v};
};
} // if (i!=j)
} // for

не менее, чем вдвое (!).
Т. о. всего не более чем

log2 n этапов.
Каждый этап имеет стоимость O(m).
Общая сложность O(m log2 n ).

ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ