Коротко: задача — найти все пути между двумя вершинами в графе $G=(V,E)$. В худшем случае количество простых путей экспоненциально от числа вершин, например $O(c^{|V|})$. Ниже — подходы для четырёх парадигм, кратко: идея, типичный псевдокод/правило, сильные и слабые стороны, когда лучше применять.
1) Процедурное программирование
- Идея: императивный DFS/BFS с явными структурами данных (стек/очередь, массив visited, аккумулятор для путей).
- Псевдокод (DFS с бэктрекингом):
push start on stack; visited[start]=true;
while stack не пуст:
если вершина == target: сохранить текущий путь
для каждого соседа u:
если not visited[u]:
mark visited, рекурсивный вызов/вложенный цикл
при возврате unmark visited
- Плюсы: прямой контроль над памятью и порядком обхода, производительность, простота для небольших программ.
- Минусы: вручную управлять состоянием и копированием visited; меньше абстракций; код может быть громоздким при добавлении ограничений (например веса, критерии фильтрации).
- Когда выбирать: простые утилиты и скрипты, оптимизация производительности, когда нужен контроль над ресурсами.
2) Объектно‑ориентированное программирование
- Идея: представить граф, вершины и пути как объекты; инкапсулировать алгоритм в методах/итераторах; поддержать расширяемость (heuristics, visitor, strategy).
- Пример структуры:
class Graph { neighbors(v) }
class Path { nodes[]; add(node); clone() }
Graph.findAllPaths(s,t):
use recursive/iterative DFS, сохранять Path-объекты
- Плюсы: хорошая модульность и расширяемость, можно хранить дополнительные данные (метаданные пути, отладка), легко внедрять стратегии поиска и переиспользовать код.
- Минусы: больше шаблонного/слойного кода, возможный оверхед при создании объектов (особенно при экспоненциальном числе путей), сложнее добиться максимально низкого уровня оптимизации.
- Когда выбирать: большие проекты, где важна архитектура, поддержка расширений, тестируемость, интеграция с другими объектами системы.
3) Функциональное программирование
- Идея: использовать чистую рекурсию и неизменяемые структуры; представлять наборы путей как списки/стримы; применять композиции (map/flatMap/filter); при большом количестве путей — ленивые потоки.
- Псевдокод (чистая рекурсия):
findPaths(s,t,visited) =
if s == t then [[t]]
else for each u in neighbors(s) if u not in visited:
prepend s to each path in findPaths(u,t,visited ∪ {u})
- Плюсы: короткий декларативный код, удобство параллелизации и безопасного concurrency (иммутабельность), легко комбинировать фильтры/трансформации, ленивость уменьшает память.
- Минусы: при большом числе путей рекурсия и аллокации списков могут быть затратными; требуется внимание к хвостовой рекурсии или ленивым структурам; иногда сложнее контролировать порядок обхода и явные побочные эффекты.
- Когда выбирать: когда важна ясность, компоновка трансформаций, безопасная параллельность, или когда удобны ленивые вычисления (генераторы потоков).
4) Логическое программирование (Prolog‑подход)
- Идея: описать рёбра как факты и путь как правило, довериться механизмам поиска и бэктрекинга Prolog.
- Пример (Prolog‑стиль):
edge(a,b). edge(b,c). ...
path(X,Y,Visited,[X,Y]) :- edge(X,Y).
path(X,Y,Visited,[X|P]) :-
edge(X,Z),
\\+ member(Z,Visited),
path(Z,Y,[Z|Visited],P).
Запрос: ?- path(start, target, [start], P).
- Плюсы: очень краткая декларация правила, автоматический бэктрекинг и генерация всех решений, удобно добавлять логические ограничения (например свойства вершин), хороший инструмент для прототипирования и задач с логическими/правиловыми ограничениями.
- Минусы: масштабируемость и производительность могут быть хуже в больших графах; контроль порядка поиска и оптимизаций требует знаний о процедуре вывода; не всегда удобен для интеграции в императивную систему.
- Когда выбирать: когда задача — в первую очередь логические/ограничительные условия, прототипирование поисковых задач, системы экспертных правил, когда нужен быстрый способ описать поиск без реализации механики обхода.
Краткие рекомендации по выбору
- Нужен максимум скорости и контроль — процедурный (или низкоуровневый OOP).
- Нужна хорошая архитектура/расширяемость — OOP.
- Хочется чистоты, легкой параллельности и композиции — функциональный; если результирующий набор путей очень большой — использовать ленивые потоки.
- Задача — набор логических ограничений/правил или быстрый прототип — логическое программирование.
Учтите: само существование «всех путей» часто делает задачу экспоненциальной ($O(c^{|V|})$), поэтому важно выбирать стратегию представления результатов (ленивые генераторы, фильтрация, ограничение длины) вне зависимости от парадигмы.