Поиск в глубину с использованием матрицы смежности?

Я пытаюсь использовать рекурсию и 2D-массив для реализации поиска в глубину по матрице смежности и имею проблемы. Я все еще новичок в этом, извините, если моя ошибка слишком очевидна.

Мой код не читает строку, если все числа равны 0, и не показывает посещенные компоненты.

Например, матрица 10x10, в которой только 1 в строке, столбце (9,6) и также (6,9) соответственно. Все остальное 0.

Он должен выводить

Component: 1
Component: 2
Component: 3
Component: 4
Component: 5
Component: 6 9
Component: 7
Component: 8
Component: 10
Total number of Components: 9

Вот мой метод до сих пор.

public static void dfs(int i, int[][] G) {
    boolean [] visited = new boolean[10];

    if(!visited[i]){        
        visited[i] = true; // Mark node as "visited"
        System.out.println("Compnent: " );
        System.out.println( i+1 + " ");

        for (int j = 0; j < G[i].length-1; j++) {
            if (G[i][j]==1 && !visited[j]) {   
                dfs(j, G); // Visit node
            }
        }
    }   
}

Единственное, что отображается выше, — это Компонент 1, после чего метод останавливается.


java recursion multidimensional-array adjacency-matrix depth-first-search
person JohnMurphy27    schedule 17.03.2017    source источник
comment
Пожалуйста, покажите мне, как вы вызываете метод dfs?   -  person Phi Luu    schedule 17.03.2017
comment
Я вызываю это, используя dfs(0, array); по основному методу. массив представляет собой двумерную матрицу.   -  person JohnMurphy27    schedule 17.03.2017

Ответы (1)


arrow_upward
4
arrow_downward

В вашем примере нет соединения между первым узлом и другими узлами. Следовательно, мы не можем никуда уйти из первого узла.

Код должен быть примерно таким:

public static void dfs(int i, int[][] graph, boolean[] visited) {
    if(!visited[i]){        
        visited[i] = true; // Mark node as "visited"
        System.out.print(i+1 + " ");

        for (int j = 0; j < graph[i].length; j++) {
            if (graph[i][j]==1 && !visited[j]) {   
                dfs(j, graph, visited); // Visit node
            }
        }
    }   
}

public static void main(String[] args) {
    // your matrix declare
    boolean [] visited = new boolean[10];
    int count = 0;
    for(int i = 0; i < graph.length; i++) {
        if(!visited[i]) {
            System.out.println("Compnent: " );
            dfs(i,graph,visited);
            ++count;
        }
    }
    System.out.println("Total number of Components: " + count);
}
person Phi Luu    schedule 17.03.2017