Arefe Arefe - 4 years ago 179
Java Question

How to implement dfs using recursion?

I'm trying to implement DFS with recursion using the following code,

public static void dfs(int i, int[][] mat, boolean [] visited){

visited[i] = true; // Mark node as "visited"

System.out.print(i + "\t");

for ( int j = 0; j < visited.length; j++ ){

if ( mat[i][j] ==1 && !visited[j] ){

dfs(j, mat, visited); // Visit node
}

}
}


I have a matrix and an array for tracking visited nodes,

// adjacency matrix for uni-directional graph
int [][] arr = {
// 1 2 3 4 5 6 7 8 9 10
{ 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, // 1
{ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, // 2
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 3
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, // 4
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, // 5
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 6
{ 0, 0, 0, 0, 0, 0, 0, 1, 1, 0}, // 7
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 8
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, // 9
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} // 10
};


boolean [] visited = new boolean[10];

for (int i =0; i< visited.length; ){

visited[i++] = false;
}


I'm making the call as following,

dfs(1, arr, visited);


This return

// 1 6 7 8 9


// it should return : [1 2 7 8 9 10 3 4 5 6]

The graph is as following,

enter image description here
which is not correct. How can I improve my code ?

Answer Source

Your code is perfectly correct, just call is incorrect. You're calling the dfs on the 1st node, but root is at 0th node.

So if you just replace

dfs(1, arr, visited);

with

dfs(0, arr, visited);

it would print the correct order of indices, which means every element would be one less than your required result as Java array index starts at 0.

Also there's no need to initialize a primitive array as Java primitive arrays are already initialized and default value of boolean is false.

Following is the code after modifications

public class Dfs {
    public static void main(String[] args) {
        int[][] arr = {
                // 1 2 3 4 5 6 7 8 9 10
                { 0, 1, 1, 1, 0, 0, 0, 0, 0, 0 }, // 1
                { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 }, // 2
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, // 3
                { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 }, // 4
                { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 }, // 5
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, // 6
                { 0, 0, 0, 0, 0, 0, 0, 1, 1, 0 }, // 7
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, // 8
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, // 9
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } // 10
        };
        boolean [] visited = new boolean[10];

        dfs(0, arr, visited);

    }

    public static void dfs(int i, int[][] mat, boolean[] visited) {
        if(!visited[i]) {
            visited[i] = true; // Mark node as "visited"
            System.out.print( (i+1) + " ");

            for (int j = 0; j < mat[i].length; j++) {
                if (mat[i][j] == 1 && !visited[j]) {
                    dfs(j, mat, visited); // Visit node
                }
            }
        }
    }
}

Output

1 2 7 8 9 10 3 4 5 6
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download