Question: Given an undirected graph `G = (V, E)`, such that `u`, `v`, `w` are some edges in G.

Describe an algorithm to determine whether

*"if there is a path from u to w that passes through v"*

A simple algorithm for that using DFS is given below:

```
bool checkFunction(){

  graph g; // containing u, w, v
  dfs(v);

  if(isVisited(u) && isVisited(w))
    return true;
  else
    return false;

}

```

For the above algorithm,

* time complexity : O(V+E)
* space complexity : O(V)

But can we reduce the time complexity?

Answer: 
Without any more constraints, there aren't any available optimizations that aren't kind of obvious.

A path exists iff *u*, *v*, and *w* are in the same connected component. That can be easily determined by running a BFS or DFS from any one to see if it finds the other two.

For some graphs there is an opportunity to do better when a path does *not* exist and one of the vertices is in a small connected component. You can do a single BFS from your initial 3 vertices, and when you discover a new vertex, remember which source it came from. You will also find connections when you discover a redundant edge from, for example, a *u* vertex to a *v* vertex. If you run out of edges from any one source before all 3 are connected, then you can stop, because you know that that vertex is isolated.
A naive way to do it is just to find all paths you can take from u to w, and then see if v exists in one of those sets.

Or just see if a path exists from u to v and a path exists from v to w