Графы. Поиск в глубину

Пятница, 28 октября 2016
Таймс, 4 этаж

Описание

  • Хранение графа (матрица смежности, список рёбер)

  • Собственно dfs (алгоритм, время работы, поиск компонент связности)

  • Классификация рёбер для оррафа, неорграфа: прямые, обратные, перекрёстные

  • Топологическая сортировка. Определение, алгоритм за время O(V+E).

  • Покраска в два цвета

  • Алгоритм поиска цикла в ориентированном графе (бело-серо-чёрный dfs), только орграф! неор будет на практике

  • Сильная связность: определение, наивный алгоритм за O(VE), алгоритм за O(V+E)