totofugaのブログ

ネットワークとかc言語、perlの話。

グラフ

グラフの内部表現で通常c言語だと エッジの数によって隣接行列か隣接リストのどっちかで表すが、

メモリと速度をあまり気にしない場合perlだと ハッシュを使った下記のような形で作るのが簡単。

my $adj;

sub add_connect {
    my ($a, $b) = @_;

    $adj->{$a}->{$b} = 1;
}

sub del_connect {
    my ($a, $b) = @_;

    $adj->{$a}->{$b} = 0;
}

sub to_connects {
    my ($node) = @_;
    return grep { $adj->{$node}->{$_} } keys %{$adj->{$node}};
}

sub from_connects {
     my ($node) = @_;
     return grep { $adj->{$_}->{$node} } keys %$adj;
}

dfsとbfsだとこんな感じ。

# dfs(深さ優先探索)
my %mark;
sub dfs_search {
    my ($node) = @_;
    return 0 if $mark{$node}++;

    print $node. "|";

    foreach my $next_node ( to_connects($node) ) {
        dfs_search($next_node);
    }
    return 1;
}
# bfs(幅優先探索)
my %mark;
while (@a) {
    my $node = shift @a;

    next if ( $mark{$node}++ );
    print $node. "|";

    foreach my $next_node ( to_connects($node) ) {
        push @a, $next_node;
    }
}