perl - Perl 中的 Kevin Bacon 六度

标签 perl data-structures graph-theory graph-traversal

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

最佳答案

参见 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)

关于perl - Perl 中的 Kevin Bacon 六度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1685063/

相关文章:

c - 递归反转单链表的函数中的段错误

algorithm - 计算最大独立集算法的正确性

.net - 让日志阅读更高效

perl - 将字符串转换为 CRC-32 时的不同结果

javascript - 前端 : html/css+javascript, 后端:perl

java - 单值映射 Java 的多个键

python - 在 Python 中比较和更新数组值

c++ - 来自梯度图像的邻接矩阵

algorithm - 计算DFS算法的时间复杂度

perl - 如何根据模块版本有条件地更改@INC?