# Routes Between Node, Cracking the coding interview

I am going though Cracking the coding interview and trying to improve my coding interview skills.

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

I think the run time is N^2 but I could be wrong.

Is there a better way to do BFS?

package TreesAndGraph;

import java.util.Queue;

public class PathSearch
{
public static void main(String[] args)
{
int[][] matrix = {
{0, 1, 0, 0, 1, 1},
{0, 0, 0, 1, 1, 0},
{0, 1, 0, 0, 0, 0},
{0, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0}};

//Following are all true.
System.out.println("0 -> 1: " + routeBetweenNode(matrix, 0, 1));
System.out.println("0 -> 4: " + routeBetweenNode(matrix, 0, 4));
System.out.println("0 -> 5: " + routeBetweenNode(matrix, 0, 5));
System.out.println("0 -> 3: " + routeBetweenNode(matrix, 0, 3));
System.out.println("0 -> 2: " + routeBetweenNode(matrix, 0, 2));
System.out.println("1 -> 1: " + routeBetweenNode(matrix, 1, 1));
System.out.println("2 -> 4: " + routeBetweenNode(matrix, 2, 4));
System.out.println("1 -> 2: " + routeBetweenNode(matrix, 1, 2));

}

private static boolean routeBetweenNode(int[][] matrix, int start, int end)
{
if (traverseMatrix(end, q, matrix[start])) return true;

while (!q.isEmpty())
{
Integer activeVisited = q.remove();
if (traverseMatrix(end, q, matrix[activeVisited])) return true;
}
return false;
}

private static boolean traverseMatrix(int end, Queue<Integer> q, int[] currentArray)
{
for (int i = 0; i < currentArray.length; i++)
{
int value = currentArray[i];
if (value == 1)
{