我正在尝试使用以下代码实现递归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 } } }
我有一个矩阵和一个数组用于跟踪被访问的节点,
// 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; }
我打电话如下,
dfs(1, arr, visited);
这回归
// 1 6 7 8 9
这是不正确的.它应该返回:[1 2 7 8 9 10 3 4 5 6]
图如下,
我该如何改进我的代码?
您的代码完全正确,只是呼叫不正确.您在第一个节点上调用dfs,但root是第0个节点.
所以如果你只是替换
dfs(1, arr, visited);
同
dfs(0, arr, visited);
它将打印正确的索引顺序,这意味着当Java数组索引从0开始时,每个元素将比您所需的结果少一个.
此外,不需要初始化基本数组,因为Java基本数组已经初始化,默认值为boolean为false.
以下是修改后的代码
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 } } } } }
产量
1 2 7 8 9 10 3 4 5 6