java - 如何通过 Java 中的递归深度优先搜索确定图中两个节点是否相连？

Question

注意:下面的代码现在反射(reflect)了问题的有效解决方案，我找出了错误。

我正在尝试解决查看两个节点是否连接的简单问题。有许多使用堆栈的解决方案，我可以找到很多递归的 DFS 代码，但没有使用递归并实际搜索某些内容并返回 true/false。任何帮助，将不胜感激。谢谢!

  public static boolean routeBetween(int[][] graph, int startNode, int targetNode){

  //where we can keep track of the visited vertices
  int numberOfVertices = graph[0].length;
  boolean[] visited = new boolean[numberOfVerticies];

  //set all verticies to not visited
  for(int i=0; i<visited.length; i++){
    visited[i] = false;
  }

  return dfs(graph, visited, startNode, targetNode);
}

//where the actual dfs / recursion will happen, need this to keep track of
//visited
public static boolean dfs(int[][] graph, boolean[] visited, int startNode, int targetNode){

  if(startNode == targetNode){
    return true;
  }
  boolean foundNode = false;

  if(!visited[startNode]){
    visited[startNode] = true;
    for(int i=0; i<graph[startNode].length;i++){
      if(graph[startNode][i] ==1){
        boolean currentChild = dfs(graph, visited, i, targetNode);
        foundNode = currentChild || foundNode;
      }
    }
  }
  return foundNode;
}

这是我用来测试上述代码的一些代码:

  int [][] matrix = {
      {0, 1, 0, 0, 1, 1, 0, 0},
      {1, 0, 0, 0, 0, 1, 1, 0},
      {0, 0, 0, 1, 0, 0, 1, 0},
      {0, 0, 1, 0, 0, 0, 0, 1},
      {1, 0, 0, 0, 0, 1, 0, 0},
      {1, 1, 0, 0, 1, 0, 0, 0},
      {0, 1, 1, 0, 0, 0, 0, 1},
      {0, 0, 0, 1, 0, 0, 1, 0}
    };

    System.out.println(GraphTools.routeBetween(matrix,0,1));
    System.out.println(GraphTools.routeBetween(matrix,0,2));

Answer 1

我知道您已经解决了问题，但有时看到事情以不同的方式解决是值得的。

由于您已经在 boolean 数组中跟踪您访问的所有节点，因此您在 dfs 方法中所做的大部分工作都是多余的。

另一种方法如下:

public static boolean dfs2(int[][] graph, boolean[] visited, int startNode, int targetNode) {

    // if you have not visited the current node or the target node
    // then visit this node and recursively explore its unvisited 
    //neighbors
    if (!visited[startNode] && !visited[targetNode]) {
        // visit the start node
        visited[startNode] = true;
        for (int i = 0; i < graph[startNode].length; i++) {
            if (graph[startNode][i] == 1) {
                return dfs(graph, visited, i, targetNode);
            }
        }
    }
    // otherwise we just return whether or not we have visited the
    // target node and continue... If we have visited the target node 
    //we never go into the if-statement and we always return true

    return visited[targetNode];

}

你的方法完全没问题，我只是想提供一个替代解决方案。希望这有帮助。