Графы
Граф — математическая модель из вершин и соединяющих их рёбер. Вершины представляют объекты, а рёбра — выбранные отношения между ними: например, станции и маршруты, люди и знакомства или задачи и зависимости. Рёбра могут быть направленными или иметь вес, если важно направление связи либо её стоимость. Графовая модель показывает структуру связей, но сама по себе не объясняет причины этих связей; алгоритмы обхода, маршрутизации и поиска компонент решают уже отдельные задачи над графом.
BFS (Breadth-First Search)
Обход графа в ширину с использованием очереди. Посещение всех соседей текущего узла перед переходом на следующий уровень. Сложность O(V + E). Применение: кратчайший путь в невзвешенном графе, уровни дерева.
DFS (Depth-First Search)
Обход графа в глубину с использованием стека (или рекурсии). Продвижение вглубь до упора, затем возврат. Сложность O(V + E). Применение: поиск циклов, топологическая сортировка, компоненты связности.
Алгоритм Дейкстры
Поиск кратчайшего пути из источника во все вершины во взвешенном графе с неотрицательными весами. Жадный алгоритм с priority queue. Сложность O((V + E) log V) с кучей. Эдсгер Дейкстра, 1956.
Алгоритм Беллмана-Форда
Поиск кратчайшего пути из источника, допускает отрицательные веса. Релаксация всех рёбер V-1 раз. Сложность O(VE). Обнаруживает отрицательные циклы. Медленнее Дейкстры, но универсальнее.
Алгоритм Прима — минимальное остовное дерево
Построение минимального остовного дерева (MST) жадным способом. Начало с произвольной вершины, добавление минимального ребра, соединяющего дерево с новой вершиной. Сложность O((V + E) log V) с кучей. Прим, 1957.
Алгоритм Крускала — минимальное остовное дерево
Построение MST сортировкой рёбер по весу, добавление ребра, если не образует цикл. Используется Union-Find для проверки циклов. Сложность O(E log E). Крускал, 1956.
Карта темы «Алгоритм Крускала — минимальное остовное дерево»
Поиск в ширину (BFS)
Обход графа "по слоям" с очередью (1959). O(V+E) время. Находит кратчайший путь в невзвешенном графе. Используется: компоненты связности, расстояния, веб-краулинг.
Поиск в глубину (DFS)
Рекурсивный обход "сначала вглубь" со стеком. O(V+E) время. Применения: топологическая сортировка, поиск циклов, компоненты сильной связности (алгоритм Косарайю).
Минимальное остовное дерево
Связывает все вершины с минимальным весом рёбер. Алгоритмы Краскала (O(E log E)) и Прима (O(E log V)). Применения: сети, кластеризация, аппроксимация TSP.