Кратко: базовая сложность обхода графа — $O(|V|+|E|)$. Дальше — как каждая парадигма реализует обход, какие структуры/абстракции предпочитает и в каких задачах она принципиально облегчает решение.
1) Процедурное (императивное)
- Подход: шаг за шагом меняем состояние (метки вершин, очередь/стек), явные циклы и мутабельные контейнеры.
- Структуры: списки смежности или матрица смежности, булев массив visited, стек/очередь, карта parent/dist.
- Абстракции: функции/процедуры для push/pop, mark/visit; явное управление контролем.
- Пример: итеративный BFS с очередью; DFS с явным стеком.
- Когда удобнее: низкоуровневая оптимизация памяти/времени, императивная среда (C, embedded), когда важен контроль над побочными эффектами и производительностью.
2) Объектно-ориентированное
- Подход: модель графа как набора объектов (Node, Edge, Graph) с методами (neighbors(), visit(), iterator()) — инкапсуляция поведения и состояния.
- Структуры: объекты-узлы с коллекциями соседей; интерфейсы Iterator/Visitor; возможно сопоставление типов (DirectedGraph, WeightedGraph).
- Абстракции: паттерны (Iterator для обхода, Visitor для операций над узлами, Strategy для выбора алгоритма обхода).
- Пример: метод Graph.bfs(start, visitor) где visitor.visit(node) вызывается при обходе; подклассы меняют стратегию обхода.
- Когда удобнее: большая кодовая база, требуется расширяемость/полиморфизм (разные виды графов/визиторов), инкапсуляция метаданных вершин/ребер, поддержка объектной модели домена.
3) Функциональное
- Подход: избегание мутаций, рекурсия/хвостовая рекурсия, ленивые последовательности/генераторы, композиция функций и высшего порядка.
- Структуры: неизменяемые списки/множества visited, Map для расстояний, ленивые стримы обхода; стек в параметрах рекурсивной функции или в аккумуляторе.
- Абстракции: чистые функции, монады состояния/эффектов (State, ST), хвостовая рекурсия, fold/map/filter, lazy streams для бесконечных графов.
- Пример: рекурсивный DFS, BFS через очереди в функциональном стиле или ленивый поток вершин (yield-like).
- Когда удобнее: рассуждать о корректности, легко параллелить (без shared mutable state), работать с потоками/ленивыми структурами, когда нужен чистый код и формальная верификация; удобен для persistent undo/history.
4) Логическое (декларативное, например Prolog)
- Подход: описываем отношения/правила (edge/2, path/2) и используем механизм разрешения запросов (backtracking, unification).
- Структуры: факты и правила; внутренние индексы движка (таблица предикатов) для быстрого поиска.
- Абстракции: предикаты, рекурсивные правила, ограничители (cuts), табулирование (memoization) для предотвращения зацикливания.
- Пример (Prolog):
path(X,Y) :- edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).
(добавить visited или табулирование для простановки посещённых)
- Когда удобнее: поиск/вывод с ограничениями, сочетание поиска и логического вывода (напр., маршрут с предикатами «безопасно», «стоимость < C»), естественно моделируется backtracking; кратко выражает сложные правила и ограничения.
Сравнительные замечания и сценарии, где одна парадигма принципиально облегчает задачу:
- Если нужна максимальная производительность и контроль памяти — процедурный/императивный код проще и эффективнее.
- Для больших extensible систем с разными типами графов/поведований — OOP даёт удобные точки расширения (полиморфизм, паттерны).
- Для корректности, параллелизма и работы с ленивыми/бесконечными графами — функциональный стиль с неизменяемыми структурами облегчает рассуждение и распараллеливание.
- Для задач, где поиск + сложные логические условия/ограничения важны (напр., конфигурационные ограничения, дедуктивный поиск маршрутов) — логическое программирование (Prolog, Datalog) часто короче и выразительнее: решается декларацией правил, а движок сам делает backtracking/tabling.
- Если нужно сочетать: часто практично гибридизировать — использовать чистые функции для логики обхода внутри объектной модели, или логический движок для выражения ограничений поверх императивного графа.
Итого: алгоритмическая основа одна ($O(|V|+|E|)$), но выбор парадигмы влияет на удобство выражения, масштабируемость, верифицируемость и способность естественно формулировать дополнительные требований (параллелизм, ограничения, расширяемость).