Презентация Поиск в глубину в ориентированных графах Топологическая сортировка онлайн

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

Презентации » Образование » Поиск в глубину в ориентированных графах Топологическая сортировка

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

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

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

Тип файла:

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

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

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

878.50 kB
Просмотров:

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

0
Автор:

неизвестен

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

№1 слайд

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

№2 слайд

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

№3 слайд

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

№4 слайд

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

№5 слайд

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

№6 слайд

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

№7 слайд

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

№8 слайд

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

№9 слайд

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

№10 слайд

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

№11 слайд

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

Содержание слайда: Нахождение сильно связных компонент графа (ССК) Алгоритм на основе поиска в глубину Сильная связность (Strongly Connection) Определение. Орграф G сильносвязный, если любые две его вершины достижимы друг из друга.

№18 слайд

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

№19 слайд

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

№20 слайд

Содержание слайда: Соответствие «ССК – дерево» Утверждение Пусть Gi =(Vi, Ei) – ССК орграфа G, а F =(V, T) - глубинный остовный лес для G. Тогда узлы Vi орграфа G вместе с ребрами из Ei T образуют дерево. Т.о. «ССК  дерево», но «дерево  ССК» - не верно (см.пример) Хорошо бы при ПВГ обнаруживать корни деревьев, соответствующих ССК (!) Алгоритм Тарьяна (Tarjan R.E.) аналогичен ранее рассмотренному алгоритму нахождение двусвязных компонент. Мы рассмотрим далее другой алгоритм.

№21 слайд

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

№22 слайд

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

№23 слайд

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

№24 слайд

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

№25 слайд

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

№26 слайд

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

№27 слайд