# [LintCode] Route Between Two Nodes in Graph [DFS/BFS]

## Problem

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

## Example

Given graph:

A----->B----->C
\     |
\    |
\   |
\  v
->D----->E

for s = B and t = E, return true
for s = D and t = C, return false

## Solution

public class Solution {
public boolean hasRoute(ArrayList<DirectedGraphNode> graph,
DirectedGraphNode s, DirectedGraphNode t) {
Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>();
return dfs(s, t, visited);
}
public boolean dfs(DirectedGraphNode s, DirectedGraphNode t, Set<DirectedGraphNode> visited) {
if (s == null) return false;
if (s == t) return true;
for (DirectedGraphNode next: s.neighbors) {
if (visited.contains(next)) continue;
if (dfs(next, t, visited)) return true;
}
return false;
}
}

BFS

public class Solution {
public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) {
if (s == t) return true;
Deque<DirectedGraphNode> q = new ArrayDeque<>();
q.offer(s);
Set<DirectedGraphNode> visited = new HashSet<>();
while (!q.isEmpty()) {
DirectedGraphNode node = q.poll();