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

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

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

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

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

Нахождение компонент связности

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

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

  • Топологической сортировкой называется присвоение номеров вершинам: любая дуга направлена из вершины с меньшим номером в вершину с бóльшим номером.
  • Почему это возможно?
  • Всегда найдётся вершина, в которую не входит ни одно ребро.
  • Такой вершине можно присвоить минимальное значение, после чего убрать её из графа.
Похожие материалы:

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

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