Как реализовать 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 на 1-м узле, но 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 
       } 
      } 
     } 
    } 
} 

Выходные