Кратко — алгоритм, корректность, сложность, затем практические варианты для слишком больших графов.
1) Описание алгоритма (BFS, уровень за уровнем)
- Вход: граф (ориентированный или неориентированный) $G=(V,E)$, стартовая вершина $s$.
- Поддерживаем очередь $Q$, массив расстояний $dist[v]$ (инициализируются $dist[v]=\infty$, $dist[s]=0$).
- Алгоритм: положить $s$ в $Q$; пока $Q$ не пусто — вынуть $u$, для каждого соседа $v$ если $dist[v]=\infty$ поставить $dist[v]=dist[u]+1$ и добавить $v$ в $Q$.
2) Доказательство корректности (коротко, инвариант)
Инвариант очереди: все вершины в очереди имеют известное конечное расстояние, и расстояния в очереди не убывают по времени извлечения.
Тезис: когда вершина $u$ извлекается из очереди, $dist[u]$ равно длине кратчайшего пути от $s$ до $u$.
Доказательство по индукции по количеству извлечений:
- База: $s$ извлекается с $dist[s]=0$, верно.
- Шаг: пусть для всех ранее извлечённых вершин утверждение верно. Рассмотрим очередное извлечение вершины $u$. Если существует путь короче, то он должен проходить через некоторую вершину $w$, которая была извлечена раньше (иначе все вершины на коротком пути были бы ещё не извлечены и имели бы расстояние $\infty$, противоречие). По предположению индукции $dist[w]$ — минимальное, и при обработке $w$ мы установили $dist[u]$ не больше этого кратчайшего значения плюс длина оставшейся части пути, значит $dist[u]$ уже равен истинному кратчайшему. Таким образом при извлечении $dist[u]$ окончателен.
Также BFS посещает вершины в порядке неубывания расстояния от $s$, поэтому присваиваемые значения — минимальные.
3) Сложность
- Временная сложность при представлении смежностей в виде списков смежности: каждое ребро рассматривается ровно один раз (в ориентированном графе) или два раза (в неориентированном), поэтому время $\Theta (|V|+|E|)$. В KaTeX:
$$T(n,m)=\Theta (n+m),$$ где $n=|V|,m=|E|$.
- Память: нужно хранить $dist$ и флаги посещения $\Rightarrow$ $\Theta (n)$ для вершин плюс пространство для представления ребер $\Theta (m)$. Итого $\Theta (n+m)$.
4) Графы, не помещающиеся в память одного узла — подходы и изменения алгоритма/данных
A. Сжатое представление / «встраивание»
- Цель: уменьшить потребность в памяти на одном узле. Подходы: сжатые представления (CSR/CSR+компрессия: delta-кодирование, Elias–Fano, WebGraph, k2-tree), хранение в виде векторных эмбеддингов (для задач поиска/оценки схожести) — но эмбеддинги не заменяют BFS, они дают приближённые результаты.
- Влияние на BFS: нужно декодировать соседей при обходе — CPU/память vs I/O компромисс. Часто используют CSR с delta-кодированием: быстро стримить соседей по одному буферу.
- Подходит, если уменьшение памяти важнее небольшой потери в скорости.
B. Внешняя память (out‑of‑core / semi‑external)
- Модель: оперативная память держит вершины и мета‑данные ($O(n)$), а список рёбер лежит на диске/SSD. При обходе читают блоками размером $B$.
- Наивный уровень-за-уровнем подход: для каждого уровня требуется сканировать все списки смежности, поэтому I/O:
$${\text{I/O}}_{\text{naive}}=O(d\cdot \lceil m/B\rceil ),$$ где $d$ — радиус/диаметр по уровням; в худшем случае это плохо.
- Оптимизации:
- Semi‑external BFS: хранить массив текущего фронтира в памяти и стримить только те блоки рёбер, которые нужны (буферизация, индекс по вершинам). Тогда можно приблизиться к
$$\text{I/O}=O(\lceil m/B\rceil )$$ в лучших реализациях (один или небольшое число проходов по рёбрам) при условии эффективной индексации/буферизации.
- Push vs Pull: push — проход по вершинам фронтира и выдача сообщений соседям; pull — для каждой вершины проверять, есть ли у неё сосед в фронтире (инвертированная проверка). Pull удобен при большом фронтире, т.к. позволяет фильтровать многие записи (уменьшает I/O).
- Бакетирование обновлений, компрессия фронтира, проброс пред-вычисленных индексов на диск, использование SSD вместо HDD.
- Практическая рекомендация: semi‑external модель (вершины в RAM, рёбра на диске) + буферизация и push/pull гибрид — часто даёт хорошую масштабируемость.
C. Распределённый граф (кластер)
- Модель: граф разбивается по $p$ узлам (partitioning). Два основных подхода:
- 1D (vertex‑cut по вершинам): каждая вершина и её список соседей целиком на одном узле;
- 2D/Cartesian: матрица смежности разбивается по двум измерениям, уменьшает коммуникацию для очень больших кластеров.
- Корректность: та же — уровень-за-уровнем глобально; нужно согласовывать frontier между узлами.
- Коммуникационные расходы: основная метрика — число сообщений/пакетов через границы партиций. Время выполнения (упрощённо) можно представить как сумма по уровням:
$$T\approx \sum _{k=0}^d(T_{\text{comp}}^k+T_{\text{comm}}^k),$$ где $T_{\text{comp}}^k$ — локальная обработка (пропорциональна локальным ребрам фронтира), $T_{\text{comm}}^k$ — обмен сообщениями. Часто
$$T_{\text{comm}}^k=\alpha \cdot \#\text{msgs}+\beta \cdot \text{bytes},$$ с латентностью $\alpha$ и стоимостью передачи на байт $\beta$.
- Оптимизации:
- Минимизировать ребра на границе (качественная партиция, метрики: edge‑cut, vertex‑cut).
- 2D партиционирование (уменьшает коммуникативную нагрузку, особенно при больших кластерах).
- Direction‑optimizing BFS (Beamer): переключение push↔pull в зависимости от размера фронтира — экономит коммуникацию и локальные сканы.
- Аггрегация сообщений, асинхронные обновления, использование ghost/replicated vertices (зеркала) для локального чтения и периодической синхронизации.
- Использовать BSP‑рамки (Pregel), графовые системы (GraphX, GraphLab, Galois) либо MPI‑реализации.
- Балансировка нагрузки: критична, т.к. фронтиры могут быть сильно неравномерными.
5) Практические рекомендации (кратко)
- Если можно держать хотя бы массив вершин и флаги в памяти — используйте semi‑external CSR на SSD и push/pull гибрид; это простая и часто эффективная схема.
- Для кластеров: 2D‑разбиение + direction‑optimizing BFS + батчирование сообщений.
- Для экономии памяти: компрессия списков смежности (CSR + delta) с on‑the‑fly декодированием.
- Если требуются приблизительные ответы или анализ свойств графа (а не точные кратчайшие пути), можно рассмотреть эмбеддинги/скрытые представления, но это уже другая задача (приближённые расстояния).
Если нужно, могу привести компактное псевдокод BFS, формулы I/O для конкретной внешней модели ($M,B$) или схему распределения (1D vs 2D) подробнее.