Главная Информатика школьная » Файлы » Презентации powerpoint » Информатика школьная [ Добавить материал ]

Презентация на тему "Алгоритмы на графах. Определение наличия циклов в графе"

[Скачать с сервера (633.9 Kb) - бесплатно] 13.12.2012, 14:14

Презентация на тему "Алгоритмы на графах. Определение наличия циклов в графе" по информатике в формате powerpoint. Данная презентация для школьников 10-11 класса представляет собой "продвинутый" уровень по изучению темы алгоритмы. Автор презентации: Югов Иван Олегович.


Фрагменты из презентации

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

  • Если граф ациклический, то можно выполнить топологическую сортировку.
  • Если в графе есть циклы, то топологическая сортировка невозможна.
  • Как с помощью топологической сортировки определить наличие циклов в графе?

Поиск циклов в графе

  • Используем DFS для нахождения графа.
  • Если из текущей вершины есть путь в серую вершину, то имеем цикл.
  • Если в графе есть цикл, то почему DFS обязательно его найдёт?
  • Рассмотрим цикл и момент, когда покидаем первую вершину в нём.
  • Возвращаться будем из вершины X в вершину Y, поочерёдно окрашивая вершины в цикле в чёрный цвет.
Как определить сам цикл?

Сделаем стек. При заходе в вершину помещаем её в стек, при выходе — забираем её оттуда.

  • массив stack длины n — стек вершин;
  • sp — указатель вершины стека (число элементов в нём).
Как запомнить все вершины, из которых выходим?

Сделаем второй стек. Если цикл найден, то помещаем во второй стек все покидаемые вершины, пока не встретим вершину cc.

  • массив stack2 длины n — стек вершин в прямом порядке;
  • sp2 — указатель вершины второго стека.
  • В первой строке файла input.txt заданы целые n и m — соответственно число вершин и число рёбер  ориентированного графа (1 ≤ n ≤ 10 000, 0 ≤ m ≤ 50 000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами.
  • В файл output.txt вывести последовательность номеров вершин, соответствующих любому циклу в графе. Если граф ациклический, то вывести 0.
  • Ограничение по времени — 1 сек.
  • Ограничение по памяти — 16 Мб.
Похожие материалы:

Добавил: gera (13.12.2012) | Категория: Информатика школьная
Просмотров: 5539 | Загрузок: 938 | Рейтинг: 0.0/0 |
Теги: презентация, алгоритмы на графах, средняя школа, циклы в графах, Алгоритмы, графы, Информатика школьная
Комментарии (0)

Имя *:
Email *:
Код *: