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

Question

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.

Accepted 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.