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

Содержание слайда: Построение и анализ алгоритмов Лекция 8 Раздел: Алгоритмы на графах Тема лекции: Поиск по графу

Содержание слайда:

Содержание слайда:

Содержание слайда: Поиск по графу. Алгоритм пометок search (vert v0) { setVert Q; // рабочее множество вершин графа 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

Содержание слайда: Поиск по графу. Алгоритм пометок Procedure Search ( v0: 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 }

Содержание слайда: ПОИСК В ШИРИНУ ПОИСК В ШИРИНУ ( Breadth First Search - BFS ) Множество 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) дерева

Содержание слайда: ПОИСК В ШИРИНУ ( O(n+m) ) for (vV) newVert[v]=true;//пометить вершины как необследованные 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 + { <v,u> }; // predVert[u] = v } //if } //for вершина v - использована } //while } // searchBFS

Содержание слайда: ПОИСК В ШИРИНУ ( O(n+m) ) begin for  v  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 + { <v,u> } { PredVert[u] := v } end {if-for} { вершина v - использована } end {while} end { BFS }

Содержание слайда: ПОИСК В ШИРИНУ Пример

Содержание слайда: ПОИСК В ШИРИНУ = Волновой алгоритм

Содержание слайда: searchDFS (vert v) searchDFS (vert v) { global bool newVert [n]; setVert V; //множество вершин графа 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 ) // 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); }

Содержание слайда: ПОИСК В ГЛУБИНУ пример

Содержание слайда: Применение ПВГ ПВГ с виду прост и его несложно реализовать На самом деле это очень гибкий и мощный алгоритм (схема), который можно применять для решения многих трудных задач обработки графов (Седжвик)

Содержание слайда: СВЯЗНЫЕ КОМПОНЕНТЫ (Поиск в глубину) СВЯЗНЫЕ КОМПОНЕНТЫ (Поиск в глубину) {… setVert V; //множество вершин графа 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 ++; // посетить v numVert[v] = iV; for (wAdj[v]) { if (numVert[w]==0) { // <v,w> - ребро (ветвь) остовного дерева T = T + { <v, w> }; treeDFS( w, v); } else // w - уже посещалась if ((numVert[w] < NumVert[v]) && (w!=u)) // <v,w> - обратное ребро (хорда) } B = B + { <v,w> }; }// v - использована } }// treeDFS

Содержание слайда: Продолжение Собственно поиск в глубину в графе G=(V,E): { setVert 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-остова (глубинного остовного дерева) Пусть (V, T) – DFS-остов графа G = (V, E) и пусть {u, v}  E. Тогда либо u потомок v (в дереве), либо v потомок u.

Содержание слайда: Свойство TDFS-остова (глубинного остовного дерева) Иллюстрация к доказательству: {u,v}  E v посещена раньше, чем u numVert[v] < numVert[u] r – корень TDFS

Содержание слайда: Замечания Раскраска вершин Нумерация посещенных и использованных

Содержание слайда: Другая формулировка свойства DFS p[v] – номер посещаемой (обрабатываемой – process) вершины f[v] - номер использованной (завершенной – finish) вершины t – такт времени (шаг алгоритма) Единая нумерация: t++; p[v] = t; … t++; f[v] = t;

Содержание слайда: Свойство DFS-остова Для любых двух вершин u, v выполняется ровно одно из трех утверждений: Отрезки [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]

Содержание слайда: Построение остовного дерева пример (еще раз)

Содержание слайда: Построение остовного дерева Единая нумерация

Содержание слайда: Замечание про прямую, обратную и противоположную теоремы (свойство ПВГ-дерева)

Содержание слайда: Алгоритм Борувки построения МОД O(m*log n) Вход : 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]

Содержание слайда: Идея алгоритма

Содержание слайда: Случай равных весов

Содержание слайда: { { T={ }; C={ {v1},...,{vn} }; while (Card(C)<>1) { // этап: 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] */ }

Содержание слайда: Продолжение (детализация) for ({u,v}E) { пусть i и j такие, что (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 ).

Содержание слайда: КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ