読者です 読者をやめる 読者になる 読者になる

深さ優先探索をPerlで

Perl

深さ優先探索自体はどうでもいいんだけど(ぉ、Perlのデリィファレンス付近を復習しないと破滅なので深さ優先探索を題材に書いてみる。Rubyでも昔書いてた

package Graph;
use strict;
use warnings;
use Perl6::Say;
use Data::Dumper;

use base qw(Class::Accessor);

Graph->mk_accessors(qw(edges nodes));

sub new {
    my $class = shift;
    my $self = {
		edges => [],
		nodes => {}
	       };
    bless ($self, $class);
    return $self;
}

sub add_edge {
    my ($self, $edge) = @_;
    push @{$self->{edges}}, $edge unless grep{$_ eq $edge} @{$self->{edges}};
}

sub add_node {
    my ($self, $u, $v) = @_;
    $self->add_edge($u);
    $self->add_edge($v);
    push @{$self->{nodes}->{$u}}, $v unless grep{$_ eq $v} @{$self->{nodes}->{$u}};
}

sub dfs {
    my $self = shift;
    my $start = shift;
    my $has_approached = shift || [];
    my $indent = shift || 0;
    say " " x $indent, $start;
    push @$has_approached, $start;
    foreach my $node (@{$self->{nodes}->{$start}}) {
	unless(grep{$_ eq $node} @$has_approached) {
	    $self->dfs($node, $has_approached, $indent + 1);
	}
    }
}

1;

my $g = Graph->new();

$g->add_edge("1");
$g->add_edge("2");
$g->add_edge("3");
$g->add_edge("8");
$g->add_edge("3");
$g->add_node("3", "2");
$g->add_node("1", "5");
$g->add_node("1", "6");
$g->add_node("2", "6");
$g->add_node("1", "3");
$g->add_node("2", "9");

print Data::Dumper->Dumper($g);
$g->dfs("1");

実行結果。

/Users/syou6162/perl% perl dfs.pl

$VAR1 = 'Data::Dumper';
$VAR2 = bless( {
                 'edges' => [
                              '1',
                              '2',
                              '3',
                              '8',
                              '5',
                              '6',
                              '9'
                            ],
                 'nodes' => {
                              '1' => [
                                       '5',
                                       '6',
                                       '3'
                                     ],
                              '3' => [
                                       '2'
                                     ],
                              '2' => [
                                       '6',
                                       '9'
                                     ]
                            }
               }, 'Graph' );
1
 5
 6
 3
  2
   9