Finding goal in DepthFirstSearch

Question

I just wondering where to put this code

if(node == goal){
            System.out.print("Found path: ");
            for(int n : stack){
                System.out.print(n + " ");
            }
        }

in this method:

public void performRecursiveDFS(Graph G, int node, int goal) {
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(node);
    while (!stack.isEmpty()) {
        node = stack.pop();
         if (!visited[node]) {
            visited[node] = true;
            for (int w : G.adjList(node)) {
                stack.push(w);
            }
        }
    }
}

For the reason is, I want to print the path from the start node to the goal node. For example like this, Found path: 0 1 2 3 4 7. I tried putting it after node = stack.pop() but it showed me something like this Found path: 3. Any reason/suggestion? Is there something wrong with my code? If so, please direct me in detail. Questions are welcome. Thanks in advance.

Answer 1

You have implemented part of the DFS that keep track of visited nodes and you can extend it to know source path also that link to next node

Full DFS implementation will look something like below that will handle paths request also

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;


public class DirectedDFS {

    private final Digraph g;
    private final int source;

    private boolean[] marked;
    private int[] edgeFrom;

    public DirectedDFS(Digraph g, int source) {
        this.g = g;
        this.source = source;
        init(g);
        dfs(g, source);
    }

    private void init(Digraph g) {
        this.marked = new boolean[g.V()];
        this.edgeFrom = new int[g.V()];
        Arrays.fill(edgeFrom, -1);
    }

    private void dfs(Digraph g, int source) {

        marked[source] = true;
        for (int vertex : g.adj(source)) {
            if (!marked[vertex]) {
                edgeFrom[vertex] = source;
                dfs(g, vertex);
            }
        }
    }

    public boolean hasPath(int v) {
        return marked[v];
    }

    public Iterable<Integer> path(int v) {
        if (hasPath(v)) {
            final Deque<Integer> paths = new ArrayDeque<>();
            int vertex = v;
            paths.push(v);
            while ((vertex = edgeFrom[vertex]) != -1) {
                paths.push(vertex);
            }
            return paths;
        }
        return (Iterable<Integer>) Collections.emptyIterator();
    }

}