CODEWITHSUNDEEP
algorithmgraph-theory
user3684042
user3684042

Reputation: 671

Finding all the nodes between two certain vertices in a directed graph

I am looking for an algorithm to find all the nodes between two certain nodes of a directed graph. For example, the nodes between nodes "a" and "j" in the graph shown below are:

b c d e f g h i

P.S. The graph is directed and edges are upward (down to top).

enter image description here

Upvotes: 1

Views: 895

Answers (1)

templatetypedef
templatetypedef

Reputation: 372664

You're looking for the set of nodes where the start node s can reach the node and that node can reach the destination node t. One way to do this is to do a DFS from s to find all nodes reachable from s and a reverse DFS from t to find all nodes that can reach t, then to take the intersection of those two sets. If you maintain the sets by storing mark bits in the nodes themselves, this runs in linear time.

Hope this helps!

Upvotes: 2

Related Questions