extra space for recursive depth-first search to store paths

Question

I am using depth-first search to identify paths in a directed weighted graph, while revisiting nodes that belong to a cycle, and setting cutoff conditions based on total distance traveled, or stops from the source node.

As I understand, with recursion an explicit stack structure is not required for depth first search, so I was wondering if I could further simplify my code below by somehow doing without the explicit stack:

public class DFSonWeightedDirectedGraph {

    private static final String START = "A";
    private static final String END = "E";
    private int pathLength = 0;
    private int stops = 0;

    public static void main(String[] args) {
        //this is a directed weighted graph
        WeightedDirectedGraph graph = new WeightedDirectedGraph();
        graph.addEdge("A", "B", 15);
        graph.addEdge("A", "D", 15);
        graph.addEdge("A", "E", 27);
        //(...) more edges added


        Stack<String> visited = new Stack<String>();        
        visited.push(START);

        new DFSonWeightedDirectedGraph().depthFirst(graph, visited);
    }

    private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) {

        Collection<Map.Entry<String, Integer>> tree_of_children 
            = graph.get_tree_of_children(visited.peek());

        for (Map.Entry<String, Integer> child : tree_of_children) {


            if(pathLength + child.getValue()>= 20){
                continue;
            }       


            visited.push(child.getKey());
            pathLength += child.getValue();
            stops += 1;         

            if (child.getKey().equals(END)) {
                printPath(visited);
            }

            depthFirst(graph, visited); 
            visited.pop();  
            pathLength -= child.getValue();
            stops -= 1; 
        }
    }

    private void printPath(Stack<String> visited) {
        for (String node : visited) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println("[path length: "+pathLength +
                " stops made: " + stops +"]");
    }
}

However, other recursive implementations without an explicit stack structure usually take into account already visited nodes, by coloring them white, gray or black. So, in my case where revisiting is allowed, and the path needs to be recorded, is an explicit stack absolutely required? Thanks for any suggestions of simpler alternatives.

Answer 1

If you have to save the path, you need a data structure for this. Your stack is OK; you could replace it with another data structure, but not get rid of it.

If it would be OK to directly print the path (and not record it), you do not need a stack. Then you can change the method signature to just get the graph and the actual node (and perhaps the actual path length and the "stops").