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

Question

In a bidirectional graph check if a path exists between node A and node B.

My code does not work for certain input (samples provided below). Is this implementation correct or I missed something?

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;
}

This works for below examples:

Input: n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2 Output: true

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5 Output: false

Does not work for below (expected return value is true but I get false):

Input: 10, edges = [[4,3],[1,4],[4,8],[1,7],[6,4],[4,2],[7,4],[4,0],[0,9],[5,4]], start = 5, end = 9

Answer 1

The approach is correct, with the only issue being that inside the recursive DFS, you need to keep track of the result of all the subsequent DFS calls. If any of the recursive calls return true, then the solution should return true (instead of directly returning false). Here is the slightly modified version of the DFS function that works :

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;
}

Update : Thanks to the suggestion in the comments. If DFS for any of the adjacent vertices returns true, then the method can directly return true (instead of making DFS call for other adjacent vertices and keeping that status). That gives us another variation of 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;
}