CODEWITHSUNDEEP
algorithmgraphdirected-graph
prashu Gupta
prashu Gupta

Reputation: 15

Existence of cycle between any two vertices of graph

A problem to find Number of paths between two particular vertices of a directed graph and if there exists a cycle in between them then the number of paths are infinite, so I know the algorithm to find cycle in the whole graph but not any two particular vertices, so it will be helpful for me if anyone explain it.

Upvotes: 1

Views: 279

Answers (1)

akhem301
akhem301

Reputation: 99

So, we can divide this problem into two sub parts.
If there is a cycle between U (source) and V (destination) then the answer will be infinite. So in one DFS we will start from U until we get V. Similarly starting from V until we get U. If we get reach both from both the ways then the desired answer is infinite.

Now the main part. Run a normal DFS from source U and start visiting every node as true, if you encounter the destination node that is V don't mark it as true and then simply continue from there. (Cycles in between this process can easily be detected).

Upvotes: 1

Related Questions