РусҚаз

Графы и поиск пути

Информатика · 10 класс · 4 урока

Что изучают в теме

Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Уроки темы

  1. Что такое графПредставь схему метро: кружочки — станции, линии между ними — перегоны. Вот это и есть граф: набор вершин и рёбер, которые соединяют пары вершин. Графу неважно, где нарисован кружок, важно…
  2. Обход в ширинуБрось камешек в пруд — от него разойдутся круги: сначала маленький, потом побольше, потом ещё больше. Обход в ширину исследует граф точно так же, волнами: сначала старт, потом все его…
  3. Алгоритм ДейкстрыПредставь, что едешь через город: можно проехать три перекрёстка по пробкам, а можно пять по свободной дороге и успеть раньше. Алгоритм Дейкстры ищет не путь с меньшим числом участков, а…
  4. Графы вокруг насОткрой навигатор в телефоне — внутри него весь город хранится как граф: перекрёстки — вершины, улицы — рёбра, а вес — время в пути с учётом пробок. Графы вокруг нас повсюду: в интернете, в…

Что пройти до этой темы