Лаборатория графов и алгоритмов

Графы и их представления

Граф — это пара (V, E), где V — множество вершин, а E — множество рёбер. В программировании используются два представления: матрица смежности (V × V — память, но O(1) проверка ребра) и список смежности (V + E памяти, O(степени) проверка). Для разреженных графов (E ≪ V²) предпочтителен список — экономнее памяти.

Graph algorithms are among the most important and useful in computer science. Many real-world problems can be modeled as graph problems and solved efficiently using fundamental graph algorithms.— Cormen, Leiserson, Rivest, Stein «Introduction to Algorithms» (CLRS)

Поиск в ширину (BFS)

BFS исследует граф «слой за слоем» от стартовой вершины. Использует очередь (FIFO). Гарантирует кратчайший путь по числу рёбер в невзвешенном графе. Сложность O(V + E).

BFS(G, s):
    visited = {s}; queue = [s]
    while queue not empty:
        u = queue.dequeue()
        for v in adj[u]:
            if v not in visited:
                visited.add(v)
                parent[v] = u
                queue.enqueue(v)

Поиск в глубину (DFS)

DFS идёт «вглубь» по одной ветке, возвращается при тупике. Реализуется рекурсивно или через стек. Сложность O(V + E). Применения: топологическая сортировка, поиск компонент сильной связности (алгоритм Тарьяна), обнаружение циклов.

Алгоритм Дейкстры

Dijkstra находит кратчайший путь от стартовой вершины до всех остальных во взвешенном графе с неотрицательными весами. Жадный алгоритм: на каждом шаге выбирается вершина с минимальным расстоянием. Сложность с приоритетной очередью на бинарной куче — O((V + E) log V).

Применения в реальной жизни

• Яндекс-карты, 2ГИС, Google Maps — Dijkstra/A* для построения маршрутов.
• Соцсети — BFS для «друзья друзей», графы рекомендаций.
• Поисковые системы — PageRank на графе ссылок (модификация степенного метода).
• Маршрутизация в сетях — OSPF (Dijkstra), BGP (анализ путей).
• Компиляторы — DFS для топосортировки модулей, обнаружения циклов в зависимостях.
• Биоинформатика — графы белок-белковых взаимодействий.