in case you need to deal with newly added keys, I'll suggest you to create a simple stack and loop until it's empty:

for (my @stack = keys %links; $#stack>=0; ) {
  my $current = shift @stack;
  next if $links{$current}{visited};
  if (something_happens()) {
    push @stack, "another key";
  }
}
[download]

Courage, the Cowardly Dog