Алгоритмы на графах

Тематический план

• 

  Общее

  • Объявления Форум
• 

  Тема 1

  Основные понятия. Способы задания графов

  • Условия задач
  • Матрица смежности и список ребер - Условия задач
• 

  Тема 2

  Обход в глубину

  • Теоретический материал: реализация и применение обхода в глубину (М.Иванов) Гиперссылка
  • Теоретический материал: Топологическая сортировка (М.Иванов) Гиперссылка
  • Реализация топологической сортировки Книга
  • Теоретический материал: Поиск компонент связности (М.Иванов) Гиперссылка
  • Теоретический материал: Поиск компонент сильной связности (М.Иванов) Гиперссылка
  • Реализация поиска сильно связных компонент в графе Книга
  • Теоретический материал: Поиск мостов (М.Иванов) Гиперссылка
  • Теоретический материал: Поиск точек сочленения (М.Иванов) Гиперссылка
  • Реализация поиска Эйлерова цикла в графе Книга
  • Условия задач
  • Условия задач
• 

  Тема 3

  Обход в ширину

  • Теоретический материал: Реализация и приложения обхода в ширину (М.Иванов) Гиперссылка
  • Условия задач
• 

  Тема 4

  Алгоритм Дейкстры

  • Теоретический материал: алгоритм Дейкстры (М.Иванов) Гиперссылка
  • Реализация Книга
  • Условия задач
  • Условия задач
• 

  Тема 5

  Алгоритм Флойда

  • Условия задач
  • Условия задач
  • Теоретический материал: Алгоритм Флойда-Уоршелла. Гиперссылка
• 

  Тема 6

  Алгоритм Форда-Беллмана

  • Условия задач
  • Теоретический материал: алгоритм Форда-Беллмана (М.Иванов) Гиперссылка
• 

  Тема 8

  Минимальный каркас: алгоритмы Прима и Краскала

  • Реализация Книга
  • Условия задач
  • Условия задач
  • Теоретический материал: Алгоритм Прима Гиперссылка
  • Теоретический материал: Алгоритм Краскала Гиперссылка
• 

  Тема 9

  Поиск максимального потока

  • Теоретический материал: Поиск максимального поток методом Эдмондса-Карпа (М. Иванов) Гиперссылка
  • Теоретический материал: Алгоритм Диница (М. Иванов) Гиперссылка
  • Реализация алгоритма Форда—Фалкерсона Книга
  • Условия задач
• 

  Тема 10

  Задача о назначениях

  • Теоретический материал Книга
  • Реализация поиска максимального паросочетения Книга
  • Реализация поиска максимального потока методом проталкивания предпотока Книга
  • Конспект венгерского алгоритма и реализация на C++ от Д. А. Шведа Гиперссылка
  • Условия задач
  • Видеолекция Д. А. Шведа про венгерский алгоритм и минимальное вершинное покрытие в двудольном графе Гиперссылка