Find if Path Exists in Graph

easy bfs graph union find

Problem

Given undirected edges and two vertices source, destination, decide if any path connects them.

Inputn=3, edges=[[0,1],[1,2],[2,0]], source=0, destination=2

Outputtrue

0–1–2 or 0–2 directly.

edges (u,v;...)

src

dst

from collections import deque
def valid_path(n, edges, source, destination):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b); adj[b].append(a)
    visited = [False] * n
    q = deque([source]); visited[source] = True
    while q:
        u = q.popleft()
        if u == destination: return True
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True; q.append(v)
    return False

function validPath(n, edges, source, destination) {
  const adj = Array.from({length: n}, () => []);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
  const visited = new Array(n).fill(false);
  const q = [source]; visited[source] = true;
  let head = 0;
  while (head < q.length) {
    const u = q[head++];
    if (u === destination) return true;
    for (const v of adj[u]) if (!visited[v]) { visited[v] = true; q.push(v); }
  }
  return false;
}

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        boolean[] visited = new boolean[n];
        Deque<Integer> q = new ArrayDeque<>(); q.add(source); visited[source] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            if (u == destination) return true;
            for (int v : adj.get(u)) if (!visited[v]) { visited[v] = true; q.add(v); }
        }
        return false;
    }
}

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
    vector<int> visited(n, 0);
    queue<int> q; q.push(source); visited[source] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == destination) return true;
        for (int v : adj[u]) if (!visited[v]) { visited[v] = 1; q.push(v); }
    }
    return false;
}

Explanation

We just need to know whether you can walk from the source vertex to the destination vertex along the edges. A plain breadth-first search (BFS) answers exactly that: explore outward from the start and see if we ever land on the target.

First we turn the edge list into an adjacency list adj. Since the graph is undirected, each edge [a, b] is added both ways: adj[a] gets b and adj[b] gets a.

Then we start a queue holding just the source and mark it visited. We repeatedly pop a vertex u; if it equals destination we return true. Otherwise we push every unvisited neighbor and mark it visited so we never revisit a node.

Example: n=3, edges [[0,1],[1,2],[2,0]], source 0, dest 2. From 0 we reach 1 and 2; popping 2 matches the destination, so the answer is true.

If the queue drains without ever reaching the destination, the two vertices are in different connected pieces and we return false. The visited array guarantees each vertex and edge is touched at most once.

Time: O(n+e) Space: O(n)