Route Between Nodes (task 4.1 from "Cracking the Coding interview")

have_route_bfs.py

from collections import deque

def have_route(g, start_node, end_node):
    """Find out if there is a path in a directed graph g 
    between start_node and end_node
        
    Algo #1: BFS-based. 
        0. Check if start_node=end_node. If so, return True;
        1. Add start_node to queue and while queue is not empty 
            1.1. dequeue curr_node;
            1.2. for all neigh_node of curr_node, check if neigh=end_node. If found, return True
            immediately. If not, mark it as visited and enqueue;
        2. We checked the whole connected component of start_node and haven't found end_node 
           => return False.

    Complexity
    ----------
    time: O(E+V), space: O(V) - because you need to store visited elements + queue
    
    Potential algo #2: DFS-based.
    
    
    -> always ask what kind of graph we are dealing with!
    
    Corner cases
    ------------
    1. Empty graph;
    2. 1 node;
    3. start_node==end_node (same as 2?)
    4. either start_node or end_node is not in the graph
    
    
    Parameters
    ----------
    g: dict
        dictionary containing nodes and their neighbours, i.e. {0:[1, 2], 1:[2]}
    start_node: int
        starting node of the route
    end_node: int
        end node of the route
    
    Returns
    -------
    boolean
        True if there is a route between 2 paths
    """
    
    q = deque([])
    visited = set()
    
    if start_node==end_node:
        return True
    q.append(start_node)
    visited.add(start_node)
    
    while len(q)!=0:
        curr_node = q.popleft()
        for neigh_node in g[curr_node]:
            if neigh_node==end_node:
                return True
            else:
                q.append(neigh_node)
                visited.add(neigh_node)
        
    return False

g = {0:[1], 1:[2], 2:[3], 3:[]}
have_route(g, 2, 0)
have_route(g, 0, 3)