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) {
			stack.push(start);

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

Comments:

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

Solution:

	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;
		q.add(start);
		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;
							q.add(v);
						}
					}
				}
				u.state = State.Visited;
			}
		}
		return false;
	}
Advertisements

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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: