You are doing a
Depth First Search, so 'E' is the first result. Perhaps what you want is a
Breadth First Search?
Update: that still wouldn't give you what you expect though...I think BFS would return A, B, b, C, c, D, d, E, e).
Last Update?: What you want is DFS, but use $t->preorder instead of $t->dfs. This returns (A, b, c, d, e, B, C, D, E) which maybe acceptably close to what you are expecting.
Aha, and use the next_alphabetic option:
my $trav = Graph::Traversal::DFS->new($graph, next_alphabetic=>1);
my $v; print "$v\n" while $v = $trav->preorder;
__END__
A
B
C
D
E
b
c
d
e