All paths between two nodes in a directed graph
To find all possible paths between two nodes in a directed acyclic graph :
'path' is a list or array.
Add source_node to path ;
find_nodes ( source_node , path ) ;
find_nodes ( my_node , path )
{
if ( my_node == destination_node )
{
print path ;
return ;
}
Find all the possible nodes that are reachable directly
from my_node ;
For each such new_node found
{
Add this new_node to path ;
find_nodes ( new_node , path ) ;
Remove this new_node from path ;
}
return ;
}
This uses a technique called recursion. You might have heard that to iterate is human but to recurse, is divine.
'path' is a list or array.
Add source_node to path ;
find_nodes ( source_node , path ) ;
find_nodes ( my_node , path )
{
if ( my_node == destination_node )
{
print path ;
return ;
}
Find all the possible nodes that are reachable directly
from my_node ;
For each such new_node found
{
Add this new_node to path ;
find_nodes ( new_node , path ) ;
Remove this new_node from path ;
}
return ;
}
This uses a technique called recursion. You might have heard that to iterate is human but to recurse, is divine.
5 Comments:
Thank you very much...........
Due to my lack of knowledge on graphs I have spent around two days trying to develop an algorithm for this.
Ya ur right to use recursion is divine...
Thank you so much!
This comment has been removed by the author.
It is very helpful for me.
Thank you! God bless you..so simple, efficient and fast!
Post a Comment
<< Home