У меня есть двудольный граф с узлом источника и синхронизации на каждом конце в качестве начального и конечного узлов. У меня возникли проблемы с реализацией следующего Java-кода для рекурсивного поиска путей расширения с использованием DFS. Любые предложения или исправления к моему коду были бы великолепны.
List<Edge> Dfs(Node start, Node end, List<Edge>result){
if(start.equals(end))
return result;
}
for (Edge e : start.node_edges){
e.start.visited = true;
if(e.end.visited ==true){
continue;
}
if(e.end.visited == false){
if(e.capacity-e.flow > 0){
result.add(e);}
}
e.end.visited = true;
if(result!=null){
return Dfs(e.end, end, result);
}
result.remove(e);
}
return null;
}
}
Проблема более подробно:
Я стремлюсь реализовать алгоритм максимального потока, но он требует увеличения путей через граф, то есть, где эта DFS входит. Он будет искать все пути, которые имеют емкость больше нуля, от начальной до конечной вершины. Мне нужна рекурсия для эффективной проверки всех возможных путей!
Что не так с этим кодом?
Если я смогу заставить эту функцию найти все пути, то я установил, что остальная часть кода безупречна. Ну, это не возвращение всех путей. Существует проблема с маркировкой узлов как посещенных и нахождением разных маршрутов, проходящих через один и тот же узел. Мне кажется, я просто неправильно вызываю функцию, используя рекурсию.