Теория: Графы
- Определения
- Граф, орграф, неорграф, путь, кратные ребра, петли [ru-wiki]
- Обозначения O, o, Θ [ru-wiki]
- Асимптотика алгоритмов: на примере сортировок и бинпоиска
- Хранение графа
- Матрица смежности [ru-wiki]
- Список смежных вершин для каждой вершины
- dfs = поиск в глубину [e-maxx]
- Компоненты связности за O(E)
- Поиск цикла в неорграфе за O(V)
- Поиск цикла в орграфе за O(E) [e-maxx]
- Топологическая сортировка графа за O(E) [e-maxx]
- bfs = поиск в ширину, кратчайший путь [e-maxx]
- Дерево кратчайших путей, восстановление пути.
- Поиск от A до v. Поиск от v до A.
- Пример с поиском по матрице. Оптимизация памяти за счет циклической очереди.
Реализация циклической очереди на массиве.
- Модификации bfs-а
- 0-1 за O(E)
- 1-k за O(kE) (нужно разкатерить ребра)
- 1-k за O(E + kV) (много очередей)
- Дейкстра = поиск кратчайшего пути в графе без отрицательных ребер
- Реализация в лоб за O(V2) [e-maxx]
- Куча дает O(ElogV) [e-maxx]
- Фибоначева куча дает O(E + VLogV)
- ford-bellman = поиск кратчайшего пути в графе без отрицательных циклов [e-maxx]
- Реализация за O(VE). С док-вом.
- Реализация за O(kE).
- Реализация bfs-ом с циклической очередью. [wiki]
- Динамика на ацикличном графе (ДП)
- число путей
- мин путь
- макс путь
- Ацикличный граф кратчайших путей
- Построение графа: d[ae] + we = d[be]
- Если we > 0, можно посчитать число кратчайших путей (ДП на ацикличном графе)
- Д.З. Если we <= 0, то? (в полученном графе могут быть циклы) [на самом деле, очень простой вопрос]
- Флойд = поиск всех кратчайших путей в графе без отрицательных циклов [e-maxx]
- Алгоритм Прима = минимальный остов (почти Дейкстра, только остов). [e-maxx]
- Алгоритм Краскала = минимальный остов с СНМ (без объяснения, что такое СНМ). [e-maxx]
- Модификации dfs-а
- Сильная связность [e-maxx]
- Not read Ориентация графа
- Мосты [e-maxx]
- Not read Точки сочленения [e-maxx]
- Not read 2-связность (реберная и вершинная)
- Конденсация графа (любые классы, сильная связность, 2-связность)
- Not read Эйлеров путь и цикл [e-maxx]
- Not read Гамильтоновы путь и цикл
- Not read 2n n2 [src]
- Not read перебор
- Not read эвристика конем
- Not read эвристика связности
- Not read Циклы
- Not read Минимальной длины, граф не взвешенный (в неорграфе, в орграфе).
- Not read Минимальной длины, граф взвешенный
- Not read Отрицательный с помощью FB [e-maxx]
- Not read Отрицательный с помощью Floyd [e-maxx]
- Not read Цикл минимального среднего веса за O(VElog) (с бинпоиском)
- Not read Цикл минимального среднего веса за O(VE)
Задачи
- Найти путь из A в B : max вес ребра в пути минимален
- Not read Для каждой пары вершина A и B сделать (1)
- Найти в графе цикл длины три
- Найти кратчайший путь четной длины
- Найти самый длинный (не обязательно простой) путь в графе
- Not read Дополнить граф до связного
- Not read Дополнить граф до сильносвязного
- Not read Найти диаметр графа (2 самые удаленные вершины)
- Not read Найти диаметр дерева
- Not read Проверить, является ли граф деревом
- Not read Разбить кактус на циклы
- Not read Число способов пройти по шахматной доске конем из (1,1) в (N,N).
- Not read Маша и грибы (Маша ходит по матрице и собирает грибы, ходить можно только вниз и вправо, нельзя врезаться в деревья).
- Not read Найти расстояние от множества A до множества B в невзвешенном графе.
- Not read Найти расстояние от множества A до множества B во взвешенном графе.