Routes Between Two Nodes Of A Graph Using BFS And DFS

We can have a directed graph like the below image and our task will be to find if their's a path or route between two given nodes.

We can achive this using BFS and DFS.

Directed Graph

BFS Algorithm: 

1. The implementation below is using BFS.
2. Create a queue and a visited array initially filled with 0, of size V where V is a number of vertices.
3. Insert the starting node in the queue, i.e. push u in the queue and mark u as visited.
4. Run a loop until the queue is not empty.
5. Dequeue the front element of the queue. Iterate all its adjacent elements. If any of the adjacent elements is the destination return true. Push all the adjacent and unvisited vertices in the queue and mark them as visited.
6. Return false as the destination is not reached in BFS.

Output

 There is a path from 1 to 3
 There is no path from 3 to 1

Complexity Analysis:  

• Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.
• Space Complexity: O(V). 
  There can be atmost V elements in the queue. So the space needed is O(V).

DFS Algorithm:

1. if start==end return 1 since we have to reached our destination.
2. Mark start as visited.
3. Traverse directly connected vertices of start and recur the function dfs for every such unexplored vertex.
4. return 0 if we do not reach our destination.

Complexity Analysis:  

Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.
Space Complexity: O(V). 
There can be atmost V elements in the stack. So the space needed is O(V).

Trade-offs between BFS and DFS: 

Breadth-First search can be useful to find the shortest path between nodes, and depth-first search may traverse one adjacent node very deeply before ever going into immediate neighbours.