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

Question

注意：下面的代码现在反映了问题的有效解决方案，我发现了错误。

我正在尝试解决查看两个节点是否已连接的简单问题。有许多使用堆栈的可用解决方案，我可以找到许多递归的 DFS 代码，但没有使用递归并实际搜索某些内容和 return 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

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

由于您已经在布尔数组中跟踪您访问的所有节点，因此您在 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];

}

你的方法很好，我只是想提供一个替代方案。希望这会有所帮助。

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

How can I figure out if two nodes are connected in a graph with recursive depth first search in Java?

java

recursion

graph

microsoft-distributed-file-system