如何使用递归实现DFS？ [英] How to implement dfs using recursion?

问题描述

我正在尝试使用以下代码通过递归实现DFS

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);

此返回值

// 1    6   7   8   9

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

which is not correct. It should return : [1 2 7 8 9 10 3 4 5 6]

图形如下，

如何改善代码？

How can I improve my code ?

推荐答案

您的代码完全正确，只是调用不正确。
您在第一个节点上调用dfs，但根在第0个节点上。

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(1, arr, visited);

与

dfs(0, arr, visited);

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

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.

此外，由于Java基本数组已经初始化并且布尔值的默认值为false，因此也不需要初始化基本数组。

Also there's no need to initialize a primitive array as Java primitive arrays are already initialized and default value of boolean is 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

1 2 7 8 9 10 3 4 5 6

这篇关于如何使用递归实现DFS？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！