Find if Path Exists in Graph

EasyDepth-First SearchBreadth-First SearchUnion FindGraph

Solution

export function validPath(
  n: number,
  edges: number[][],
  source: number,
  destination: number,
): boolean {
  const graph: number[][] = new Array(n).fill(undefined).map(() => []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }
 
  const queue = [source];
  const visited = new Array<boolean>(n).fill(false);
  visited[source] = true;
 
  while (0 < queue.length) {
    const currentVertex = queue.shift();
    if (currentVertex === undefined) {
      break;
    }
    for (const nextVertex of graph[currentVertex]) {
      if (!visited[nextVertex]) {
        queue.push(nextVertex);
        visited[nextVertex] = true;
      }
    }
  }
 
  return visited[destination];
}