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

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

Поиск в глубину в ориентированных графах Топологическая сортировка, слайд №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

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

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

Слайд 3

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

Пример ПВГ в орграфе

Слайд 4

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

Пример ПВГ в орграфе

Слайд 5

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

Слайд 6

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

Слайд 7

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

Топологическая сортировка

Слайд 8

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

Пример 0

Слайд 9

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

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

Слайд 10

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

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

Слайд 11

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

Продолжение примера 0 (ПВГ) 1) Получение sn [*] из fn [*]: for (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 проходится в порядке, обратном топологической сортировке