Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re^4: Short Circuiting DFS Graph Traversal

by Limbic~Region (Chancellor)
on Oct 29, 2010 at 15:04 UTC ( [id://868324] : note . print w/replies, xml ) Need Help??


in reply to Re^3: Short Circuiting DFS Graph Traversal
in thread Short Circuiting DFS Graph Traversal

choroba,
Most of what I know about graph theory I have learned here but I don't see why not. On the other hand, what you have just described is an unweighted graph which is stated as a given in my original node. I would be VERY impressed if an algorithm exists that can intuitively know not to follow paths that can lead to dead ends without keeping some sort of a cache of previously followed paths. If they can, then certainly they will be more efficient then what I propose and would love to learn about them.

Cheers - L~R

  • Comment on Re^4: Short Circuiting DFS Graph Traversal