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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Алгоритмы на графах Тема лекции: Поиск по графу. Доклад-сообщение содержит 40 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

Слайд 3

Описание слайда:

Слайд 4

Описание слайда:

Поиск по графу. Алгоритм пометок 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

Слайд 5

Описание слайда:

Поиск по графу. Алгоритм пометок 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 }

Слайд 6

Описание слайда:

ПОИСК В ШИРИНУ ПОИСК В ШИРИНУ ( 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) дерева

Слайд 7

Описание слайда:

ПОИСК В ШИРИНУ ( 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 + { }; // predVert[u] = v } //if } //for вершина v - использована } //while } // searchBFS

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

ПОИСК В ШИРИНУ Пример

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

ПОИСК В ГЛУБИНУ (ПВГ) ( 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); }

Слайд 13

Описание слайда:

ПОИСК В ГЛУБИНУ пример

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

СВЯЗНЫЕ КОМПОНЕНТЫ (Поиск в глубину) СВЯЗНЫЕ КОМПОНЕНТЫ (Поиск в глубину) {… 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 }

Слайд 16

Описание слайда:

СВЯЗНЫЕ КОМПОНЕНТЫ (Поиск в глубину) Рекурсивная процедура (функция) нахождения связных компонент графа 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

Слайд 17

Описание слайда:

Пример (нахождение связных компонент)

Слайд 18

Описание слайда:

Пример (нахождение связных компонент)

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

Построение остовного дерева и множества обратных ребер при поиске в глубину ( 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; // множество хорд (обратных ребер)

Слайд 21

Описание слайда:

продолжение iV ++; // посетить v numVert[v] = 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

Слайд 22

Описание слайда:

Продолжение Собственно поиск в глубину в графе 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 ); }

Слайд 23

Описание слайда:

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

Слайд 24

Описание слайда:

Задание: Задание: Выполнить поиск в глубину для этого же графа, в т. ч. построить остов и обратные ребра: Начиная с любой другой вершины Изменив списки смежности (порядок элементов в списке)

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

Свойство 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]

Слайд 30

Описание слайда:

Построение остовного дерева пример (еще раз)

Слайд 31

Описание слайда:

Построение остовного дерева Единая нумерация

Слайд 32

Описание слайда:

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

Слайд 33

Описание слайда:

Алгоритм Борувки построения МОД 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]

Слайд 34

Описание слайда:

Идея алгоритма

Слайд 35

Описание слайда:

Случай равных весов

Слайд 36

Описание слайда:

{ { 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] */ }

Слайд 37

Описание слайда:

Продолжение (детализация) 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

Слайд 38

Описание слайда:

Алгоритм Борувки построения МОД Пример

Слайд 39

Описание слайда:

Сложность алгоритма На каждом новом этапе число деревьев уменьшается не менее, чем вдвое (!). Т. о. всего не более чем log2 n этапов. Каждый этап имеет стоимость O(m). Общая сложность O(m log2 n ).