ست درجات من Kevin لحم الخنزير المقدد في بيرل

Question

أولا نعم، هذا مشروع واجبات منزلية لفصل Perl الخاص بي. أنا لا أبحث عن الإجابة (على الرغم من أن ذلك سيكون الحلو). كما أفهمها، أحتاج إلى استخدام BFS وتعبير منتظم لتنظيم بياناتي للاستخدام. أحتاج إلى بعض الاتجاهات على هذا واحد. كيف يمكنني استخدام BFS؟ هل يمكنني استخدام مكدس ضخم وتذهب من خلال كل عنصر في المكدس؟ يجب أن أستخدم طاولة تجزئة عملاقة؟ هل عمل أي شخص في هذه المشكلة؟ كيف ذهبت عن القيام بذلك؟ أنا فقط بحاجة إلى بعض الاتجاه هو كل شيء. هل هذا مشابه ل BST؟ هل هذا ممكن دون استخدام وحدة الرسم البياني؟ هل هذا ممكن باستخدام قيم التجزئة؟

Answer 1

هذا ليس كذلك إجابه, ، لكنها تلميحات تجاه إجابتك.

أفضل خدمتك أولا في البحث عن ما هو البحث الأول من الاتساع في رسم بياني.

أيضا، إذا لم تكن قد أعطيت تعبيرا منتظما، فقد تنظر تكميلها مشكلة وتبدو ذلك. ربما لن تكون هناك حاجة. تحقق من المهمة ومعرفة ما إذا كان يمكنك فقط تسرع في الشراب في بعض المعلومات.

Answer 2

يرى رسم بياني.

#!/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 درجات الفصل بين كيفن لحم الخنزير المقدد و Yelena Maksimova Kevin Bacon - إليزابيث شي: جوفاء مان (2000) إليزابيث شوي - ليف بريغونوف: سانت، The (1997) ليف بريغونوف - يلينا ماكسيموفا: Bezottsovshchina (1976)