For better efficiency I would use a hash instead of your sub _seen. Also, I'd organize the algorithm to be something like this:

my %seen;
my @nodes = ([$start, 0]); # $start is the starting node
while (@nodes) {
    my ($node, $dist) = @{shift(@nodes)};
    my @adj = ...nodes adjacent to $node...;
    for (@adj) {
        next if $seen{$_};
        $seen{$_} = 1;
        if ($dist < $MAX) {
            push(@nodes, [$_, $dist+1]);
            ...add $_ to list of interesting nodes...
        }
    }
}
[download]

This replaces the recursion with iteration.