六度Perl的凯文培根

Question

首先是的，这是我的Perl类的一个家庭作业项目。我不是在寻找答案（虽然这将是甜蜜的）。据我了解，我需要使用BFS和正则表达式来组织我的数据以供使用。我需要这方面的一些指导。我如何使用BFS？我是否使用大量堆栈并遍历堆栈中的每个项目？我应该使用一个巨大的散列表吗？有没有人在解决这个问题？你是怎么做的？我只需要一些方向。这与BST类似吗？这可能没有使用图形模块？这可能使用散列值？

Answer 1

这不是一个答案，但它是对你的答案提示。

您最好先查找图中的宽度优先搜索。

另外，如果你还没有得到一个正则表达式，你可以考虑标记问题，然后看看。可能不需要。检查作业，看看你是否可以在某些信息中只需slurp。

Answer 2

请参阅Graph。

#!/usr/bin/perl 

use autodie; 
use strict; use warnings; 

use Graph; 
use Graph::TransitiveClosure::Matrix; 

my $dat = 'kevin-bacon.dat'; 

my $kbg = Graph->new(undirected => 1); 

open my $kbf, '<', $dat; 

my %movies; 

while (my $line = <$kbf>) { 
    last unless $line =~ /\S/; 
    chomp $line; 
    my ($u, $m, $v) = split /;/, $line; 
    $kbg->add_edge($u, $v); 
    $movies{"$u|$v"} = $movies{"$v|$u"} = $m; 
} 

my $tcm = Graph::TransitiveClosure::Matrix->new($kbg, 
    path_length => 1, 
    path_vertices => 1, 
); 

my ($u, $v) = ('Kevin Bacon', 'Yelena Maksimova'); 

if (my $n = $tcm->path_length($u, $v)) { 
    printf "%d degrees of separation between %s and %s\n", $n, $u, $v; 
} 

my @path = $tcm->path_vertices($u, $v); 

for my $i (0 .. @path - 2) { 
    my ($u, $v) = @path[$i, $i + 1]; 
    print qq{$u - $v: $movies{"$u|$v"}\n}; 
} 

来自Boost项目中使用kevin-bacon.dat：

 
3 degrees of separation between Kevin Bacon and Yelena Maksimova 
Kevin Bacon - Elisabeth Shue: Hollow Man (2000) 
Elisabeth Shue - Lev Prygunov: Saint, The (1997) 
Lev Prygunov - Yelena Maksimova: Bezottsovshchina (1976)