我有一个无向图,想知道一个节点是否连接到另一个节点?
例如
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;
}
最佳答案
您无需对递归调用 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;
}
}
关于java - 如何检查Graph是否连接,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30140030/