13 Пошук вглиб у графах
•
0 likes•4,599 views
Слайди лекції з курсу "Розробка та аналіз алгоритмів. Частина 1". Тема лекції: "Пошук вглиб у графах". http://edx.prometheus.org.ua/courses/KPI/Algorithms101/2015_Spring/about
13 Пошук вглиб у графах
- 1. Розробка та аналіз алгоритмів 13. Пошук вглиб • Алгоритм пошуку вглиб • Топологічне сортування • Компоненти сильної зв’язності (с) Олексій Молчановський, Prometheus.org.ua 1
- 2. Пошук вглиб (Depth-First Search, DFS) (с) Олексій Молчановський, Prometheus.org.ua 2
- 3. Пошук вглиб. Алгоритм (друга версія) (с) Олексій Молчановський, Prometheus.org.ua 3
- 4. Топологічне сортування • Топологічне сортування орієнтованого графу G=(V, E) називається таке впорядкування всіх його вершин, що якщо граф містить ребро (v, u), то вершина v в цьому впорядкуванні буде знаходитись перед вершиною u. (с) Олексій Молчановський, Prometheus.org.ua 4
- 5. Топологічне сортування. Приклад застосування (с) Олексій Молчановський, Prometheus.org.ua 5
- 6. Топологічне сортування. Ідея алгоритму (с) Олексій Молчановський, Prometheus.org.ua 6
- 7. Топологічне сортування. Алгоритм (с) Олексій Молчановський, Prometheus.org.ua 7
- 8. (с) Олексій Молчановський, Prometheus.org.ua 8
- 9. (с) Олексій Молчановський, Prometheus.org.ua 9
- 10. (с) Олексій Молчановський, Prometheus.org.ua 10