Сигнал задачи
Когда применять
Когда базовых BFS, DFS и Dijkstra недостаточно: нужны остов, отрицательные веса, пути между всеми парами или структура связности графа.
Как выбрать подход
- Для MST в неориентированном графе Kruskal удобен со списком рёбер и DSU, а Prim — со списками смежности и при постепенном росте одного дерева.
- Bellman–Ford решает задачу из одного источника при отрицательных рёбрах и обнаруживает достижимый отрицательный цикл; Floyd–Warshall нужен для всех пар на сравнительно небольшом графе.
- SCC разбивает ориентированный граф на компоненты взаимной достижимости; Kosaraju делает два обхода, Tarjan — один DFS со стеком.
- Мосты и точки сочленения ищут в неориентированном графе по времени входа и low-link; это другая задача, чем SCC.
Сложность
- Kruskal: O(m log m) времени и O(n) памяти помимо рёбер. Prim с двоичной кучей: O((n + m) log n) времени и O(n + m) памяти.
- Bellman–Ford: O(nm) времени и O(n) дополнительной памяти помимо списка рёбер; дополнительный проход выявляет достижимое улучшение из отрицательного цикла.
- Floyd–Warshall: O(n³) времени и O(n²) памяти.
- Kosaraju, Tarjan, поиск мостов и точек сочленения: O(n + m) времени и O(n + m) памяти с представлением списками смежности.
Границы и ошибки
- На несвязном графе алгоритм MST строит минимальный остовный лес, а не одно дерево.
- Нельзя складывать INF с весом без проверки: получится переполнение или ложное улучшение в Bellman–Ford и Floyd–Warshall.
- Отрицательная диагональ после Floyd–Warshall указывает на отрицательный цикл; обычные кратчайшие расстояния через него не определены снизу.
- В графе с кратными рёбрами DFS мостов должен пропускать родительское ребро по идентификатору, а не все рёбра в родительскую вершину.