Route Between Nodes

Given a directed graph and two nodes (A and E), design an algorithm to find out whether there is a route from A to E.

Solution

This problem can be solved using a graph search, starting at node S. If node E is found during the graph search, we can return True. Otherwise, we will return False.

Let’s implement a breadth-first search, since it will be more efficient than a depth-first search. A DFS might be simpler to implement, but it will be less efficient. If the nodes are neighboring nodes, we might not know until the search algorithm has explored several branches.

def route_exists(graph, node_1, node_2):
  visited = set()
  queue = []

  if(node_1 == node_2):
    return True

  queue.append(node_1)

  while(queue):
    node = queue.pop(0)
    visited.add(node)

    if(node == node_2):
      return True

    for neighbor in graph[node]:
      queue.append(neighbor)

  return False