### Problem :

Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second.### Solution

We have already seen solution to connectivity in undirected graph via bfs. Now lets see it on directed graph.__BFS to check the connectivity__

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; }

__Like wise we can also apply DFS.__

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; }

**Time complexity**: O(|V|+|E|). Space complexity: O(|V|).

Use Stack for DFS. Use Queue for BFS.

Why do you need to have 3 states ("Visited, "Unvisited", and "Visiting")? It seems like we do the same thing - adding the node to the queue - if it's unvisited, but there is no functional distinction between visited and visiting (in either state we skip it - we won't enqueue it and we won't check against it). So, aside from debugging, I don't see any benefit of having it. Am I wrong?

ReplyDeleteHi..I agree that only visited and unvisited was enough.Thanks.

Delete