Has Path

Has Path

A fundamental graph question: is there a route from node A to node B?

This is solved with a standard BFS or DFS traversal starting from the source, stopping early when the destination is found.

BFS Approach

from collections import deque

def has_path(graph, src, dst):
    if src == dst:
        return True
    seen = {src}
    queue = deque([src])
    while queue:
        node = queue.popleft()
        for nb in graph[node]:
            if nb == dst:
                return True
            if nb not in seen:
                seen.add(nb)
                queue.append(nb)
    return False

Disconnected Graphs

If the graph is disconnected (not all nodes reachable from each other), BFS/DFS will only explore the component reachable from src:

Component 1: 0 — 1      Component 2: 2 — 3

has_path(g, 0, 3)  →  False
has_path(g, 0, 1)  →  True

Time and Space

• Time: O(V + E) — worst case visits all nodes and edges
• Space: O(V) — the seen set

Your Task

Implement has_path(graph, src, dst) that returns True if there is a path from src to dst, False otherwise. Use BFS.