use strict;
use Data::Dumper;

my @links = map { [/^(\w+)\s+(\w+)/] } split /\n/, <<LINKS;
apple bug unid1 unid2 
apple cat unid1 unid3 
bug dog unid2 unid4 
apple dog unid1 unid4
LINKS

# All links work both ways:
my %links;
for (@links) {
    my ($left,$right) = @$_;
    # We store all links in arrays
    $links{$left} ||= [];
    $links{$right} ||= [];

    # Links work both ways
    push @{$links{$left}}, $right;
    push @{$links{$right}}, $left;
};

sub find_joins {
    my ($start, $goal, $prefix, $visited) = @_;

    $visited ||= {}; # our breadcrumb trail so we don't run around in circles
    $prefix ||= [];  # the path so far
    my $curr = $start;

    warn "[@$prefix] $start => $goal";

    my @results; # All the paths that lead from $start to $end
    $visited->{$start} = 1;

    for my $link (grep { ! $visited->{$_} } @{$links{$start}}) {
        if ($link eq $goal) {
            push @results, [@$prefix,$start,$goal];
        } else {
            my %v = %$visited;
            push @results, find_joins($link,$goal,[@$prefix,$start],\%v);
        };
    };

    # Sort by length, then asciibetically
    @results = sort { scalar @$a <=> scalar @$b or $a->[0] cmp $b->[0] } @results;

    return @results;
};

print Dumper find_joins( apple => 'bug' );
print Dumper find_joins( apple => 'dog' );
print Dumper find_joins( cat => 'dog' );

__END__
[] apple => bug at tmp.pl line 31.
[apple] cat => bug at tmp.pl line 31.
[apple] dog => bug at tmp.pl line 31.
$VAR1 = [
          'apple',
          'bug'
        ];
$VAR2 = [
          'apple',
          'dog',
          'bug'
        ];
[] apple => dog at tmp.pl line 31.
[apple] bug => dog at tmp.pl line 31.
[apple] cat => dog at tmp.pl line 31.
$VAR1 = [
          'apple',
          'dog'
        ];
$VAR2 = [
          'apple',
          'bug',
          'dog'
        ];
[] cat => dog at tmp.pl line 31.
[cat] apple => dog at tmp.pl line 31.
[cat apple] bug => dog at tmp.pl line 31.
$VAR1 = [
          'cat',
          'apple',
          'dog'
        ];
$VAR2 = [
          'cat',
          'apple',
          'bug',
          'dog'
        ];