Презентация Особенности поиска в глубину (ПВГ) в ориентированных графах онлайн

На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Особенности поиска в глубину (ПВГ) в ориентированных графах абсолютно бесплатно. Урок-презентация на эту тему содержит всего 38 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.

Презентации » Образование » Особенности поиска в глубину (ПВГ) в ориентированных графах

Просмотр ВСЕЙ презентации! ЖМИТЕ

Оцените презентацию от 1 до 5 баллов!

Смотреть онлайн
Скачать

Тип файла:

ppt / pptx (powerpoint)
Всего слайдов:

38 слайдов
Для класса:

1,2,3,4,5,6,7,8,9,10,11
Размер файла:

1.12 MB
Просмотров:

47
Скачиваний:

0
Автор:

неизвестен

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

№1 слайд

Содержание слайда: Построение и анализ алгоритмов Лекция 11 Раздел: Алгоритмы на графах Тема лекции: Поиск в глубину в ориентированных графах (напомнить!) Топологическая сортировка Сильно связные компоненты (сл.17…)

№2 слайд

Содержание слайда: Особенности поиска в глубину (ПВГ) в ориентированных графах

№3 слайд

Содержание слайда: Пример ПВГ в орграфе

№4 слайд

Содержание слайда: Пример ПВГ в орграфе

№5 слайд

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

№6 слайд

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

№7 слайд

Содержание слайда: Топологическая сортировка

№8 слайд

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

№9 слайд

Содержание слайда: Продолжение примера 0 (ПВГ)

№10 слайд

Содержание слайда: Продолжение примера 0 (ПВГ)

№11 слайд

Содержание слайда: Продолжение примера 0 (ПВГ) 1) Получение sn [*] из fn [*]: for i := 1..n do sn [ i ] := n - fn [ i ] + 1; 2) Получение tn [*] из sn [*]: for i := 1..n do tn [sn [ i ]] := i; -------------------------------------------------- Или получение tn [*] сразу из fn [*]: for i := 1..n do tn [n - fn [ i ] + 1] := i ;

№12 слайд

Содержание слайда: Перестановки

№13 слайд

Содержание слайда: Выполнить ПВГ в орграфе G, заполнив массив fn[*]. Выполнить ПВГ в орграфе G, заполнив массив fn[*]. Пронумеровать вершины номерами (n - fn[v] + 1), т.е. заполнить sn [*] – вектор (последовательность) новых номеров в порядке топологической сортировки (sn [ i ] – новый номер вершины с исходным номером i). Перегруппировать вершины, т.е. заполнить tn [*] – вектор старых номеров в новом порядке (tn [ i ] – исходный номер вершины с номером i в порядке топологической сортировки)

№14 слайд

Содержание слайда: Алгоритм топологической сортировки Пример 1

№15 слайд

Содержание слайда: Алгоритм топологической сортировки Пример 2 (другие списки смежности)

№16 слайд

Содержание слайда: Продолжение на следующей лекции! (28 апреля)

№17 слайд

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

№18 слайд

Содержание слайда: Сильно связные компоненты (Strongly Connected Components) Сильно связная компонента – максимальный сильно связный подграф Сильно связная компонента = ССК

№19 слайд

Содержание слайда: ? При стягивании каждой сильно связной компоненты в одну вершину получается ациклический ориентированный граф. (Почему?)

№20 слайд

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

№21 слайд

Содержание слайда: Соответствие «ССК – дерево» Утверждение Пусть Gi =(Vi, Ei) – ССК орграфа G, а F =(V, T) - глубинный остовный лес для G. Тогда узлы Vi орграфа G вместе с ребрами из Ei T образуют дерево. Т.о. «ССК  дерево», но «дерево  ССК» - не верно (см.пример) + ещё примеры на след. слайдах

№22 слайд

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

№23 слайд

Содержание слайда: Ещё пример

№24 слайд

Содержание слайда: Вариант 1 (начало с «a»)

№25 слайд

Содержание слайда: Вариант 2 (начать с «b»)

№26 слайд

Содержание слайда: Вариант 3 (начать с «с»)

№27 слайд

Содержание слайда: Алгоритм на базе ПВГ (DFS) Хорошо бы при ПВГ обнаруживать корни деревьев, соответствующих ССК (!) Алгоритм Тарьяна (Tarjan R.E.) аналогичен ранее рассмотренному алгоритму нахождение двусвязных компонент. Мы рассмотрим далее другой алгоритм (Алгоритм Косарайю ).

№28 слайд

Содержание слайда: Sambasiva Rao Kosaraju is a professor of Computer Science at Johns Hopkins University, and division director for Computing & Communication Foundations at the National Science Foundation.He has done extensive work in the design and analysis of parallel and sequential algorithms. (From Wikipedia, the free encyclopedia)

№29 слайд

Содержание слайда: Обращение орграфа (понадобится далее), при этом ССК – те же (!)

№30 слайд

Содержание слайда: Алгоритм Косарайю (S.R.Kosaraju) нахождения ССК орграфа (на основе двух ПВГ) Выполнить ПВГ орграфа G и вычислить номера вершин в порядке их использования fn[*]. Сконструировать новый (обращенный) орграф GR , путем обращения всех дуг исходного графа. Выполнить ПВГ орграфа GR , начиная с вершины, имеющей наибольший номер fn[ ]. Если ПВГ не завершен, то продолжить, начиная с вершины, имеющей наибольший номер fn[ ] среди оставшихся. Каждое дерево полученного глубинного остовного дерева (леса) орграфа GR является ССК орграфа G.

№31 слайд

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

№32 слайд

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

№33 слайд

Содержание слайда: Основные факты (утверждения), на которые опирается доказательство правильности алгоритма Граф ССК GССК орграфа G – ациклический ССК орграфов G и GR совпадают (как множества вершин) При втором ПВГ граф ССК (GR)ССК орграфа GR проходится в порядке, обратном топологической сортировке

№34 слайд

Содержание слайда: Иначе говоря Если начать с вершины, которая лежит в стоке стянутого графа, то мы найдем компоненту, соответствующую стоку. Если мы нашли компоненту-сток, то мы можем выкинуть её из графа и продолжить поиск. Вершина графа с самым большим значением fn лежит в истоке стянутого графа. Сильно связные компоненты можно топологически упорядочить по максимальным значениям fn содержащихся в них вершин.

№35 слайд