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

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

Особенности поиска в глубину (ПВГ) в ориентированных графах, слайд №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

Содержание ▲

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

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

Слайд 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 содержащихся в них вершин.