How to implement dfs using recursion?
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
Arefe
Updated on June 11, 2022Comments
-
Arefe about 2 years
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,
-
11thdimension over 8 yearsIs the array you're using adjancency matrix ? If it is then is your graph a directed graph ? as 5 is connected to 6 but 6 is not connected to 5, same is true for 7->8 and 9->10
-
Arefe over 8 yearsYes, the array is indeed adjacency matrix and its uni-directional graph. I added a image of the graph with question.
-
mfaani about 3 yearsFWIW there’s no need to pass the adjacency matrix around. The value never changes
-
-
Arefe over 8 yearsThis is very helpful.