グラフ
グラフの内部表現で通常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; } }