六度凯文·培根在Perl的
-
18-09-2019 - |
题
首先,是的,这是我的Perl类家庭作业项目。我不是在寻找的答案(虽然这将是甜)。据我了解,我需要使用BFS和正则表达式来组织我的数据使用。我需要在这一个一个方向。如何使用BFS?我用一个巨大的堆和栈经过每一个项目?我应该使用一个巨大的哈希表?有没有人曾就这个问题?你是如何去这样做呢?我只是需要一些方向就是一切。这是类似于BST?这是可能的,而无需使用图形模块?这可能使用哈希值?
解决方案
这是不是一个的答案的,但它是提示对你的回答。
您最好先查找什么广度优先搜索是一个图形服务。
另外,如果你没有得到一个正则表达式,你可以考虑的标记化的问题,并期待这件事。可能不会是必要的。检查作业,看看你可以的啜食的一些信息。
其他提示
请参阅格拉夫。
#!/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};
}
从升压项目中使用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)
不隶属于 StackOverflow