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
which is not correct. It should return : [1 2 7 8 9 10 3 4 5 6]
The graph is as following,
How can I improve my code ?
Depth-first search (DFS), is an algorithm for tree traversal on graph or tree data structures. It can be implemented easily using recursion and data structures like dictionaries and sets.
The non-recursive implementation of DFS is similar to the non-recursive implementation of BFS but differs from it in two ways: It uses a stack instead of a queue. The DFS should mark discovered only after popping the vertex, not before pushing it.
in general recursion is not dfs.
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With