java - 如何检查Graph是否已连接

Question

我有一个无向图，想知道一个节点是否连接到另一个节点？

例如

0 1 0
1 0 1 
0 1 0

在此节点 1 连接到节点 3(因为存在从 1 到 2 和 2 到 3 的路径，因此 1-3 是连接的)

我已经编写了使用 DFS 的程序，但我无法弄清楚为什么会给出错误的结果。

我不想保留任何全局变量并希望我的方法返回真实的 id 节点使用递归程序连接

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;

    }
}