Как проверить, подключен ли граф?

Question

У меня есть ненаправленный граф и вы хотите знать, что узел подключен к другому узлу или нет?

, например

0 1 0 
1 0 1 
0 1 0 

В этом узле 1 соединен с узлом 3 (потому, что существует путь от 1 до 2 и от 2 до 3, следовательно, 1-3 соединен)

я написал программы, использующие DFS, но я не могу понять, почему это приводит к неправильному результату.

Я не хочу, чтобы какой-либо глобальной переменной и хочу, чтобы мой метод вернуть истинный идентификатор узла соединены с помощью программы рекурсивный

public static boolean isConnectedGraph(int[][] graph, int start, int end, 
     int visited[]) { 
    visited[start] = 1; 
    if (graph[start][end] == 1) { 
     System.out.println("Yes connected...."); 
     return true; 
    } 
    for (int i = 0; i < graph[0].length; i++) { 
     if (graph[start][i] == 1 && visited[i] == 0) { 
      visited[i] =1; 
      isConnectedGraph(graph, i, end, visited); 

     } 
    } 
    return false; 
} 

Answer 1

Вы ничего не делаете с результатом из рекурсивный вызов isConnectedGraph(graph, i, end, visited);. Вы должны назначить его переменной, а если она равна true - возврат true.

Изменение основной цикл, чтобы что-то вроде:

for (int i = 0; i < graph[0].length; i++) { 
    if (graph[start][i] == 1 && visited[i] == 0) { 
     visited[i] =1; 
     if (isConnectedGraph(graph, i, end, visited)) return true; 

    } 
}