2

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

4

2 回答 2

6

请参阅图表。

#!/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从 Boost 项目中使用：

凯文·培根和叶莲娜·马克西莫娃之间的 3 度分离
凯文培根 - 伊丽莎白舒：空心人（2000）
Elisabeth Shue - Lev Prygunov: Saint, The (1997)
列夫·普里古诺夫 - 叶莲娜·马克西莫娃：Bezottsovshchina (1976)
于 2009-11-06T02:46:18.947 回答
5

这不是一个答案，但它暗示了你的答案。

最好先在图表中查找广度优先搜索的内容。

此外，如果您没有获得正则表达式，您可以考虑标记化问题并进行查找。可能就不需要了。检查作业，看看你是否可以啜饮一些信息。

于 2009-11-06T02:56:52.327 回答