java 如何使用递归实现dfs？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/34553782/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to implement dfs using recursion?
提问by Arefe
I'm trying to implement DFS with recursion using the following code,
我正在尝试使用以下代码通过递归实现 DFS，
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]
这是不正确的。它应该返回：[1 2 7 8 9 10 3 4 5 6]
The graph is as following,
图形如下，
How can I improve my code ?
如何改进我的代码？
回答by 11thdimension
Your code is perfectly correct, just call is incorrect. You're calling the dfs on the 1st node, but root is at 0th node.
您的代码完全正确，只是调用不正确。您在第一个节点上调用 dfs，但 root 位于第 0 个节点。
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.
它会打印正确的索引顺序，这意味着每个元素都会比您所需的结果小 1，因为 Java 数组索引从 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.
也不需要初始化原始数组，因为 Java 原始数组已经初始化，布尔值的默认值为 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
1 2 7 8 9 10 3 4 5 6
