A simple DFS should give you this (populating the path as we do the traversal). Now only question is when we get a forward-edge, i.e. a convergence-point, we have two options,
(Assuming that while coming back after hitting n2, we keep marking vertices which have n2 in the fanout, similarly mark nodes which do not have n2 in the fanout). Suppose we hit vertex v which is already visited and it has n2 in the fanout, (if n2 is not in the fanout, nothing to do, go back) 1. Allow traversal via this node and let it hit n2 again. This is memory-efficient but would take more run-time. 2. When you are coming back after hitting n2, at any vertex where there are more than one in-arcs, i.e. a potential convergence point, keep the path v-onwards, which will lead to n2. Now this will get complex in case of re-convergence, because then there will be more than one paths from v to n2. ________________________________ From: ankur aggarwal <[email protected]> To: "i...@mca_2007" <[email protected]>; [email protected]; [email protected] Sent: Wednesday, 26 August, 2009 2:03:01 PM Subject: [algogeeks] path from n1 to n2 given a directed graph and node n1 and n2 find all possible path between them i think graph is acyclic .. otherwise there are infinte path we can write eg for node "a" and "d" are there we have a cycle node "b" to "c" and "c" to "b" a-> b->c->b->d a-> b->c->b->c->b->d etc Yahoo! recommends that you upgrade to the new and safer Internet Explorer 8. http://downloads.yahoo.com/in/internetexplorer/ --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
