Графы: различия между версиями
Материал из Algocode wiki
Grphil (обсуждение | вклад) |
KiKoS (обсуждение | вклад) м |
||
| (не показано 11 промежуточных версий 3 участников) | |||
| Строка 1: | Строка 1: | ||
==Основные понятия теории графов== | ==Основные понятия теории графов== | ||
| + | |||
| + | * [[Графы - основные определения]] | ||
| + | * [[Хранение графа]] | ||
==Обходы графа и их применения== | ==Обходы графа и их применения== | ||
| + | * [[DFS]] | ||
| + | * [[BFS]] | ||
| + | * [[Топологическая сортировка]] | ||
| + | * [[Компоненты сильной связности]] | ||
==Структуры данных в задачах на деревья== | ==Структуры данных в задачах на деревья== | ||
| Строка 7: | Строка 14: | ||
==Алгоритмы поиска кратчайшего пути в графах== | ==Алгоритмы поиска кратчайшего пути в графах== | ||
| − | * [[ | + | * [[Алгоритм Дейкстры]] |
==Остовные деревья== | ==Остовные деревья== | ||
| + | * [[Остовное дерево]] | ||
| + | * [[Лемма о безопасном ребре]] | ||
| + | * [[Алгоритм Прима]] | ||
| + | * [[Алгоритм Краскала]] | ||
| + | * [[Алгоритм двух китайцев]] | ||
==Паросочетания в графе== | ==Паросочетания в графе== | ||
==Продвинутые алгоритмы в графах== | ==Продвинутые алгоритмы в графах== | ||
| + | * [[Дерево доминаторов]] | ||
==Потоки в сети== | ==Потоки в сети== | ||
| + | * [[Задача о максимальном потоке]] | ||
| + | * [[Алгоритм Форда-Фалкерсона]] | ||
| + | * [[Алгоритм Эдмондса-Карпа]] | ||
| + | * [[Алгоритмы поиска блокирующего потока]] | ||
| + | * [[Алгоритм Диница]] | ||
==Стоимостные потоки== | ==Стоимостные потоки== | ||
Текущая версия на 17:45, 5 ноября 2020
Содержание
Основные понятия теории графов
Обходы графа и их применения
Структуры данных в задачах на деревья
Алгоритмы поиска кратчайшего пути в графах
Остовные деревья
Паросочетания в графе
Продвинутые алгоритмы в графах
Потоки в сети
- Задача о максимальном потоке
- Алгоритм Форда-Фалкерсона
- Алгоритм Эдмондса-Карпа
- Алгоритмы поиска блокирующего потока
- Алгоритм Диница