如何使用递归实现dfs？

Question

我正在尝试使用以下代码实现递归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]

图如下,

我该如何改进我的代码？

Answer 1

您的代码完全正确,只是呼叫不正确.您在第一个节点上调用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