Check if there is a route between two nodes in a Diagraph

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

My initial thoughts:
Starting from the source, using DFS to traverse the graph to check if we arrive at the target.

My initial codes:

	public static boolean isRouteBetween(Digraph g, Integer start, Integer end) {
		Stack<Integer> stack = new Stack<Integer>();
		Set<Integer> visited = new HashSet<Integer>();
		if (start != null) {

			while (!stack.isEmpty()) {
				Integer curr = stack.pop();
				if (!visited.contains(curr)) {
					if (curr.equals(end))
						return true;
					else {
						for (Integer child : g.adj(curr))
		return false;


  • Time complexity: O(|V|+|E|). Space complexity: O(|V|).
  • Use Stack for DFS. Use Queue for BFS.


	public enum State {
		Unvisited, Visited, Visiting;

	public static boolean search(Graph g, Node start, Node end) {
		LinkedList<Node> q = new LinkedList<Node>(); // operates as Stack
		for (Node u : g.getNodes()) {
			u.state = State.Unvisited;
		start.state = State.Visiting;
		Node u;
		while (!q.isEmpty()) {
			u = q.removeFirst(); // i.e., pop()
			if (u != null) {
				for (Node v : u.getAdjacent()) {
					if (v.state == State.Unvisited) {
						if (v == end) {
							return true;
						} else {
							v.state = State.Visiting;
				u.state = State.Visited;
		return false;

1 Comment (+add yours?)

  1. Trackback: find if there is a path between two nodes | zhylog

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: