In addition to all other suggestions, if you're walking through a fixed data structure and want to prevent going to the same node twice, it can be worthwhile to numify references to nodes. That is instead of trying to look at, say, $foo{$bar} and see if you've been there, look at 0 + \$foo{$bar} instead.

This tests whether the underlying scalar has been seen, and will not care if the value is, or looks like, one that you've seen before.