Depth-first/breadth-first algorithm printing all nodes; how do I get it to only print nodes in the path?

Question

I have an adjacency matrix adj of the form below:

0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 
1 0 0 0 1 0 1 0 0 
0 0 0 1 0 1 0 0 0 
0 0 1 0 1 0 0 0 1 
0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 

This is the adjacency matrix for a maze with rules adj(x,y) = 1 if:

1. x != y
2. x is adjacent to y
3. neither x or y is a wall in the maze

The maze is as below (beside it are the element numbers):

S X E | 1 2 3
O O O | 4 5 6
O X O | 7 8 9
//S = starting position
//E = ending position
//X = wall

I have a DFS algorithm that will display the nodes to traverse from S to E, but it displays unnecessary nodes.

public static void main(String [] args){
    int[][] adj = //the adjacency matrix
    boolean[] visited = new boolean[adj.length];
    int n = adj.length;    
    int m = 1; //starting position
    int o = 3; //ending position
    DFS(adjMatrix, visited, n, m, o);
}

public static void DFS(int[][] adj, boolean[] visited, int n, int i, int o){
    System.out.print(" " + (i+1));
    visited[i]= true;
    if (i+1 != o) {
        for (int j = 0; j<n;j++){
            if(!(visited[j]) && adj[i][j]==1){
               DFS(adj, visited, n, j, o);
            }
        }
    }
}

public static void BFS(int[][] adj, boolean[] visited, int n, int i, int o){
    queue Q = new queue;
    visited[i]= true;
    Q.enqueue(i);
    while (!Q.isEmpty()) {
        //...
    }
}

This prints 1 4 5 6 3 9 7. I'm wracking my head around modifying it so that it will only print 1 4 5 6 3.

What have I done wrong here?

Answer 1

There are some major issues with the code, in addition to fixes needed for the DFS algorithm:

• You Start and end are wrong: it should be decreased by 1 (because the indices are 0 based)
• Your adjanecy matrix is wrong (it is of size 10X9 - it should be a squared matrix)(edit fixed it)
• Your solution should only print elements that are in the path. One way to do it would be to return a List<> (rather than void - that populates all the nodes in the current path. If you reached the destination, create the list, otherwise - return null. Attach elements only when the recursive call returns something that is not null. Code attached

Also note, it prints the nodes in the correct order (and not reversed order)

public static void main(String [] args){
    int[][] adj = {
            {0, 0, 0, 1, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 0, 1, 0, 0, 0}, 
            {1, 0, 0, 0, 1, 0, 1, 0, 0}, 
            {0, 0, 0, 1, 0, 1, 0, 0, 0}, 
            {0, 0, 1, 0, 1, 0, 0, 0, 1}, 
            {0, 0, 0, 1, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 0, 0, 0, 0, 0}, 
            { 0, 0, 0, 0, 0, 1, 0, 0, 0} 
    };
    boolean[] visited = new boolean[adj.length];
    int n = adj.length;    
    int m = 1-1; //starting position
    int o = 3-1; //ending position
    System.out.println(DFS(adj, visited, n, m, o));
}

public static List<Integer> DFS(int[][] adj, boolean[] visited, int n, int i, int o){
    visited[i]= true;
    if (i == o) return new LinkedList<Integer>(Arrays.asList(i+1));
    for (int j = 0; j<n;j++){
        if(!(visited[j]) && adj[i][j]==1){
            List<Integer> res = DFS(adj, visited, n, j, o);
            if (res != null) { 
                res.add(0, i+1);
                return res;
            }
        }
    }
    return null; //no path
}

Will result (as expected) with:

[1, 4, 5, 6, 3]

---

As a side note, though this solution is complete (will always find a solution if such exists), it is not optimal - it might return a longer solution than the shortest one.

If you want to find the shortest path from source to target, consider switching to a BFS