# 4.1. Route between nodes

> Given a directed graph and two nodes (S and E), is there a route from S to E?

A graph can be written like this:

```java
class Graph {
    public Node[] nodes;
}

class Node {
    public String name;
    public Node[] children;
}
```

The function to find a route from S to E:

```java
bool findRoute(Node S, Node E) {
    Node[] children = S.children;
    for (int i = 0; i < children.size(); i++){
        if (children[i] == E) {
            return True;
        }
        if (children[i].children == Null) {
            continue;
        }
        else if (findRoute(Node children[i].children, E)){
            return True;
        }
    }
    return False;
}
```

Example, Route from 5 to 11:

* 5
  * 2
    * 3
    * 4
  * 1
    * 9
    * 11
  * 6

1. children = [2, 1, 6]
   1. Recursive of 2, children = [3, 4]
   2. None of them have children, continue, return False
2. Back to main loop, continue with children
   1. recursive of 1, children = [9, 11]
   2. found in children[1] == E, return True
3. Back to main loop, return True

Looks good, O(N) where N = all elements in graph, well if the graph isn't balanced at all we might have to iterate through it all.

## Hints

Two well known algorithms can do this, what are the tradeoffs between them?

1. Depth-first search (mine)
   1. Check each node until the end
2. Breadth-first search
   1. Cheack each main children first, then go deep

## Solution

Remember to **mark the found nodes as visited to avoid cycles and repetitions of nodes**. 

For an iterative solution of breadh-first search, see Java files.

Depth-first search is a bit simpler to implement since it can be done with simple recursion. Breadth-first search can also be useful to find the shortest path, whereas depth-first search might traverse one adjacent node very deeply before ever going onto the immediate neighbors.