Презентация Скачать презентацию Алгоритмы на графах: определение наличия циклов в графе онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Скачать презентацию Алгоритмы на графах: определение наличия циклов в графе абсолютно бесплатно. Урок-презентация на эту тему содержит всего 10 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:10 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:854.00 kB
- Просмотров:57
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда:
№2 слайд
Содержание слайда: Домашнее задание
Какое максимальное количество рёбер может быть в ориентированном ациклическом графе с n вершинами?
Может ли быть так, что правильным результатом топологической сортировки графа оказывается любой порядок его вершин?
Решить задачу о производстве деталей с помощью DFS.
Как использовать топологическую сортировку для определения наличия циклов в графе?
№3 слайд
Содержание слайда: Циклы и топологическая сортировка
№4 слайд
Содержание слайда: Поиск циклов в графе
№5 слайд
Содержание слайда: Поиск циклов в графе
№6 слайд
Содержание слайда: Поиск циклов в графе
№7 слайд
Содержание слайда: Поиск циклов в графе
№8 слайд
Содержание слайда: Поиск циклов в графе
№9 слайд
Содержание слайда: Поиск циклов в графе
В первой строке файла input.txt заданы целые n и m — соответственно число вершин и число рёбер ориентированного графа (1 ≤ n ≤ 10 000, 0 ≤ m ≤ 50 000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами.
В файл output.txt вывести последовательность номеров вершин, соответствующих любому циклу в графе. Если граф ациклический, то вывести 0.
Ограничение по времени — 1 сек.
Ограничение по памяти — 16 Мб.
№10 слайд
Содержание слайда: Домашнее задание
Верно ли утверждение, что из всех циклов в графе, проходящих через начальную вершину, DFS прежде всего находит цикл минимальной длины? Привести доказательство или контрпример.
Решить задачу об определении наличия циклов в ориентированном графе проверкой рёбер: в выходной файл вывести 1, если в графе есть циклы, и 0 в противном случае.
Выполнить п. 2 для неориентированного графа.
Решить задачу об отыскании цикла в ориентированном графе с помощью DFS без использования второго стека.
Скачать все slide презентации Скачать презентацию Алгоритмы на графах: определение наличия циклов в графе одним архивом:
