Problem

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
Example input: 
A -> B
B -> C
C -> D
Example output: 
There is a route between A and D.

Solution

# Solution:
# This is a graph traversal problem. We can use a breadth-first search to find the shortest path between two nodes.
# The solution below is optimal because it uses a queue to store the nodes to visit.
# The queue is implemented using a list.
# The time complexity is O(n) because we visit each node once.
# The space complexity is O(n) because we store each node in the queue.

class Node:
    def __init__(self, name):
        self.name = name
        self.children = []

def find_route(start, end):
    queue = [start]
    visited = set()
    while queue:
        node = queue.pop(0)
        if node == end:
            return True
        visited.add(node)
        for child in node.children:
            if child not in visited:
                queue.append(child)
    return False

# Test
a = Node('A')
b = Node('B')
c = Node('C')
d = Node('D')
e = Node('E') a.children.append(b)
b.children.append(c)
c.children.append(d)
print(find_route(a, d))
print(find_route(a, e))