Разделы презентаций

Графы поиск в глубину ( DFS) Хранение графа в программе

Содержание

ОпределениеГраф – это набор вершин, некоторые пары из которых соединены между собой рёбрами.Связный граф – это граф, из любой вершины которого по рёбрам можно попасть в любую другую.Направленный граф – это

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

Слайд 1Графы поиск в глубину (DFS) Хранение графа в программе
Школа::Кода
Олимпиадное программирование

2020-2021 Таганрог

Графы поиск в глубину (DFS) Хранение графа в программеШкола::КодаОлимпиадное программирование2020-2021 Таганрог

Слайд 2Определение
Граф – это набор вершин, некоторые пары из которых соединены

между собой рёбрами.
Связный граф – это граф, из любой вершины

которого по рёбрам можно попасть в любую другую.
Направленный граф – это граф, по рёбрам которого можно передвигаться только в одном заданном направлении.
Ациклический граф – это граф, не содержащий циклов.
Дерево – это связный граф, имеющий N вершин и N-1 ребро.
Взвешенный граф – это граф, в котором каждое ребро имеет свой вес (обычно длину).
Компонента связности – максимальный по включению связный подграф.
ОпределениеГраф – это набор вершин, некоторые пары из которых соединены между собой рёбрами.Связный граф – это граф,

Слайд 3Задача:
Охарактеризуйте граф:
1
2
3
4
5
6
7
8

Задача:Охарактеризуйте граф:12345678

Слайд 4Задача:
Охарактеризуйте граф:
1
2
3
4
5
6
7
8
3
2
4
1
5
2
1

Задача:Охарактеризуйте граф:123456783241521

Слайд 5Задача:
Охарактеризуйте граф:
1
2
3
4
5
6
8
7

Задача:Охарактеризуйте граф:12345687

Слайд 6Поиск (обход) в глубину (DFS)
Для каждой вершины графа будем хранить

её цвет. Пусть изначально вершины будут белыми, когда мы в

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

Слайд 7Поиск в глубину. Пример. Шаг 0
7
2
6
5
8
3
4
1
1
3
2
5
4
6
7

Поиск в глубину. Пример. Шаг 0726583411325467

Слайд 8Поиск в глубину. Пример. Шаг 1
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 1726583411326754

Слайд 9Поиск в глубину. Пример. Шаг 2
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 2726583411326754

Слайд 10Поиск в глубину. Пример. Шаг 3
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 3726583411326754

Слайд 11Поиск в глубину. Пример. Шаг 4
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 4726583411326754

Слайд 12Поиск в глубину. Пример. Шаг 5
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 5726583411326754

Слайд 13Поиск в глубину. Пример. Шаг 6
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 6726583411326754

Слайд 14Поиск в глубину. Пример. Шаг 7
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 7726583411326754

Слайд 15Поиск в глубину. Пример. Шаг 8
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 8726583411326754

Слайд 16Поиск в глубину. Пример. Шаг 9
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 9726583411326754

Слайд 17Поиск в глубину. Пример. Шаг 10
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 10726583411326754

Слайд 18Поиск в глубину. Пример. Шаг 11
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 11726583411326754

Слайд 19Поиск в глубину. Пример. Шаг 12
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 12726583411326754

Слайд 20Поиск в глубину. Пример. Шаг 13
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 13726583411326754

Слайд 21Поиск в глубину. Пример. Шаг 14
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 14726583411326754

Слайд 22Поиск в глубину. Пример. Шаг 15
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 15726583411326754

Слайд 23Поиск в глубину. Пример. Шаг 16
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 16726583411326754

Слайд 24Поиск в глубину. Пример. Шаг 17
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 17726583411326754

Слайд 25Поиск в глубину. Пример. Шаг 18
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 18726583411326754

Слайд 26Поиск в глубину. Пример. Шаг 19
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 19726583411326754

Слайд 27Поиск в глубину. Пример. Шаг 20
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 20726583411326754

Слайд 28Поиск в глубину. Пример. Шаг 21
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 21726583411326754

Слайд 29Поиск в глубину. Пример. Шаг 22
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 22726583411326754

Слайд 30Поиск в глубину. Пример. Шаг 23
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 23726583411326754

Слайд 31Поиск в глубину. Пример. Шаг 24
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 24726583411326754

Слайд 32Поиск в глубину. Пример. Шаг 25
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 25726583411326754

Слайд 33Поиск в глубину. Пример. Шаг 26
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 26726583411326754

Слайд 34Поиск в глубину. Пример. Шаг 27
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 27726583411326754

Слайд 35Поиск в глубину. Пример. Шаг 28
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 28726583411326754

Слайд 36Поиск в глубину. Пример. Шаг 29
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 29726583411326754

Слайд 37Поиск в глубину. Пример. Шаг 30
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 30726583411326754

Слайд 38Хранение графа в программе
Создадим собственную структуру Node для хранения информации

о вершине графа.
В Node будем хранить цвет самой вершины и

перечень смежных вершин.
Граф будем хранить в виде массива (вектора) вершин.
Хранение графа в программеСоздадим собственную структуру Node для хранения информации о вершине графа.В Node будем хранить цвет

Слайд 39Реализация поиска в глубину
Поиск в глубину реализуется в виде рекурсивной

функции, критерием остановки которой является повторное посещение вершины.

Реализация поиска в глубинуПоиск в глубину реализуется в виде рекурсивной функции, критерием остановки которой является повторное посещение

Слайд 40Ввод графа и запуск поиска в глубину
Пусть дан граф из

N вершин и M рёбер. Во входных данных сначала даются

числа N и M, а затем M пар чисел U и V – номера вершин графа, между которыми есть ребро. (1 ≤ U, V ≤ N)
Ввод графа и запуск поиска в глубинуПусть дан граф из N вершин и M рёбер. Во входных

Похожие презентации

Вид глагола Вид глагола 164
Формирование Древнерусского государства Формирование Древнерусского государства 518
реклама реклама 514
9_элективная_лекция.ppt 9_элективная_лекция.ppt 223
ПРЕЗЕНТАЦИЯ К ВЫПУСКНОЙ КВАЛИФИКАЦИОННОЙ РАБОТЕ НА ТЕМУ: Методические ПРЕЗЕНТАЦИЯ К ВЫПУСКНОЙ КВАЛИФИКАЦИОННОЙ РАБОТЕ НА ТЕМУ: Методические 168
Тема: Механическая кулинарная обработка сельскохозяйственной птицы и дичи Тема: Механическая кулинарная обработка сельскохозяйственной птицы и дичи 213
1 Кадры здравоохранения – важнейшая составляющая ресурсного обеспечения 1 Кадры здравоохранения – важнейшая составляющая ресурсного обеспечения 255
Культура XX века Культура XX века 318
ПОЛИГЛОТ ПОЛИГЛОТ 259
Проектирование индивидуальных образовательных маршрутов для  обучающихся с ТНР, Проектирование индивидуальных образовательных маршрутов для  обучающихся с ТНР, 249
Бурлящий сюрприз Бурлящий сюрприз 252
Четвертая промышленная революция и ее особенности. Киберфизические системы Четвертая промышленная революция и ее особенности. Киберфизические системы 338
Заголовок Подзаголовок презентации Цифровая 3D-медицина Результаты в области Заголовок Подзаголовок презентации Цифровая 3D-медицина Результаты в области 162
Параллелограмм Параллелограмм 261
Министерство образования и науки РФ Федеральное государственное бюджетное Министерство образования и науки РФ Федеральное государственное бюджетное 211
Виды опросов Виды опросов 360
Иван грозный Иван грозный 370
Deutschsprachiger Studiengang „Deutsches Recht“ (DSG) Deutschsprachiger Studiengang „Deutsches Recht“ (DSG) 248
Жизнь и творчество Владимира Семёновича Высоцкого Жизнь и творчество Владимира Семёновича Высоцкого 254
Великие географические открытия и их последствия Великие географические открытия и их последствия 297

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.

Для правообладателей

Яндекс.Метрика