[SOLVED] Determine whether there is a path from vertex u to w passing through v

Determine whether there is a path from vertex u to w passing through v

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?

Solution

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.