ANALYSIS of ALGORITHMS, Bulletin Board

# BFS set of a graph G=(V, E). (II)

```
Greetings.

The BSF routine that I posted (message "BFS set of a graph G=(V, E).")
computes a hash table at every iteration of a loop although the hash
table never changes. I fixed this in the version that is included with
this message.

Regards,

Marko Riedel

sub bfs {
my (\$g, \$marked, \$stack, \$perm, \$perms) = @_;
my (\$n) = (scalar @\$g);

if(not defined \$marked){
\$perms = {}; \$marked = [0 x \$n];
for(my \$i=0; \$i<\$n; \$i++){
\$marked->[\$i] = 1;
bfs(\$g, \$marked, 0, [\$i], \$perms);
\$marked->[\$i] = 0;
}
return \$perms;
}

my (%next);
for(my \$j=\$stack; \$j<scalar @\$perm; \$j++){
foreach my \$v (@{ \$g->[\$perm->[\$j]]}){
\$next{\$v} = 1 if not \$marked->[\$v];
}
}

foreach my \$v (keys %next){
\$marked->[\$v] = 1;
}

my (\$stackperms) = permute([@\$perm[\$stack..\$#\$perm]]);
foreach my \$stackperm (@\$stackperms){
@\$perm[\$stack..\$#\$perm] = @\$stackperm;

if(scalar @\$perm==\$n){
\$perms->{"@\$perm"} = \$perm;
next;
}

bfs(\$g, \$marked, scalar @\$perm, [@\$perm, keys %next], \$perms);
}

foreach my \$v (keys %next){
\$marked->[\$v] = 0;
}

return;
}
```

Date Prev | Date Next | Date Index | Thread Index