CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
xMilos
xMilos

Reputation: 2018

Graph check if path exist between three nodes

The problem is following we have to find path from A to C that goes thru node B or following example graph A-G-F-B-L-C.

Now to implement from A to C is easy using BFS, but I don't know how to make sure that this path passes thru B ?

Upvotes: 1

Views: 594

Answers (2)

Lior Kogan
Lior Kogan

Reputation: 20608

By 'path' you probably mean 'simple path' - a path with no repeating vertices.

First, ensure that A, B, and C are connected.

An A-...-B-..-C path exists iff:

  • There is no cut-vertex that splits A, B, and C into 3 different components
  • A is not a cut-vertex that splits B and C into different components
  • C is not a cut-vertex that splits B and A into different components

Upvotes: 1

guest3444343
guest3444343

Reputation: 9

First run a bfs to reach the intermediate node, then run a bfs from that intermediate node to your desired goal node.

Upvotes: 0

Related Questions