DFS：检查节点 A 和节点 B 之间是否存在路径

Question

在双向图中检查节点 A 和节点 B 之间是否存在路径。

我的代码不适用于某些输入（下面提供的示例）。这个实现是正确的还是我漏掉了什么？

bool[] visited = null;
public bool ValidPath(int n, int[][] edges, int start, int end) {
    IList<int>[] adjacencyList = new List<int>[n];
    visited = new bool[n];
    
    // create adjacency list
    for(int i = 0; i < edges.Length; i++){
        int a = edges[i][0];
        int b = edges[i][1];
        
        if(adjacencyList[a] == null)
            adjacencyList[a] = new List<int>();
        adjacencyList[a].Add(b);
        
        if(adjacencyList[b] == null)
            adjacencyList[b] = new List<int>();
        adjacencyList[b].Add(a);            
    }
    
    return DFS(adjacencyList, start, end);
}

private bool DFS(IList<int>[] adjacencyList, int start, int end){
    if(start == end) return true;
    
    if(!visited[start]){
        visited[start] = true;
        foreach(var v in adjacencyList[start]){
            if(v == end) return true;
            if(!visited[v])
                DFS(adjacencyList, v, end);
        }
    }
    return false;
}

这适用于以下示例：

输入：n = 3，边 = [[0,1]，[1,2]，[2,0]]，开始 = 0，结束 = 2 输出：真

输入：n = 6，边 = [[0,1]，[0,2]，[3,5]，[5,4]，[4,3]]，开始 = 0，结束= 5 输出：假

不适用于以下情况（预期 return 值为 true 但我得到 false）：

输入：10，边 = [[4,3],[1,4],[4,8],[1,7],[6,4],[4,2],[7 ,4],[4,0],[0,9],[5,4]], 开始 = 5, 结束 = 9

Answer 1

该方法是正确的，唯一的问题是在递归 DFS 内部，您需要跟踪所有后续 DFS 调用的结果。如果任何递归调用 return 为真，那么解决方案应该 return 为真（而不是直接 return 为假）。这是 DFS 函数的稍微修改后的版本：

private bool DFS(IList<int>[] adjacencyList, int start, int end){
  if(start == end) return true;

  bool status = false;
  if(!visited[start]){
    visited[start] = true;
    foreach(var v in adjacencyList[start]){
        if(v == end) {
            return true;
        }
        if(!visited[v]) {
            status = status || DFS(adjacencyList, v, end);
        }
    }
  }
  return status;
}

更新： 感谢评论中的建议。如果任何相邻顶点的 DFS return 为真，则该方法可以直接 return 为真（而不是对其他相邻顶点进行 DFS 调用并保持 status).这给了我们 DFS 的另一种变体：

private bool DFS(IList<int>[] adjacencyList, int start, int end){
  if (start == end) return true;

  bool status = false;
  if(!visited[start]){
    visited[start] = true;
    foreach(var v in adjacencyList[start]){
        if(v == end) {
            return true;
        }
        if(!visited[v] && DFS(adjacencyList, v, end)) {
            return true;
        }
    }
  }
  return status;
}

DFS：检查节点 A 和节点 B 之间是否存在路径

DFS: Check if path exists between node A and node B

c#

algorithm

graph-theory

depth-first-search