如何使用递归实现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);

这个return

// 1    6   7   8   9

这是不正确的。它应该 return : [1 2 7 8 9 10 3 4 5 6]

图表如下，

我怎样才能改进我的代码？

Answer 1

你的代码完全正确，只是调用不正确。您在第 1 个节点上调用 dfs，但 root 位于第 0 个节点。

所以如果你只是替换

dfs(1, arr, visited);

和

dfs(0, arr, visited);

它会打印正确的索引顺序，这意味着每个元素都会比您需要的结果少一个，因为 Java 数组索引从 0 开始。

此外，无需初始化原始数组，因为 Java 原始数组已经初始化，布尔值的默认值为 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

如何使用递归实现dfs？

How to implement dfs using recursion?

java

algorithm

recursion

depth-first-search

graph-algorithm