• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Алгоритмы на графах

• Алгоритм Дейкстры O(N²)
• Алгоритм Дейкстры с кучей O(MlogN)
• Алгоритм Форда-Беллмана O(N³)
• Алгоритм Левита O(NM)
• Алгоритм Флойда-Уоршала O(N³)

• Путь максимальной длины в графе
• Минимальный путь, содержащий все вершины полного графа, представимого на плоскости O(n²)
• Гамильтонов цикл O(N*N!)
• Эйлеров цикл O(M + N)

• Поиск мостов O(M + N)
• Поиск точек сочленения O(M + N)
• Поиск компонентов сильной связности O(M + N)

• Алгоритм Куна O(NM)
• Алгоритм Хопкрофта-Карпа O(sqrt(N)M)
• Минимальное вершинное покрытие

• Топологическая сортировка DAGа O(M + N)
• Поиск ближайшего общего предка двух вершин дерева O(H)
• Расстояние между двумя вершинами дерева O(H)
• Экстремальное остовное дерево - алгоритм Прима O(N²)
• Экстремально остовное дерево - алгоритм Краскала O(MlogM)

• Алгоритм Эдмондса-Карпа (метод Форда-Фалкерсона) O(NM²)
• Алгоритм проталкивания предпотока O(N⁴)
• Модифицированный алгоритм проталкивания предпотока O(N³)
• Поток с ограничениями O(N³)
• Поток минимальной стоимости O(N³M)
• Максимальный поток, заданной мощности

• Покраска графа тремя цветами
• Проверка двух графов на изоморфность
• Рёберная связность.
• Вершинная связность.