gpt4 book ai didi

perl - 如何在有向图中找到从源到汇的所有路径?

转载 作者:行者123 更新时间:2023-12-04 14:22:33 24 4
gpt4 key购买 nike



我想找到从源到汇的所有路径。预期的:

(3 11 17 24 32 39 45)
(3 11 18 26 33 39 45)
(3 11 18 26 33 40 46)
(3 11 18 26 33 40 47)
(3 11 19 27 33 39 45)
(3 11 19 27 33 40 46)
(3 11 19 27 33 40 47)
(3 11 19 27 34 40 46)
(3 11 19 27 34 40 47)
(6 12 20 27 33 39 45)
(6 12 20 27 33 40 46)
(6 12 20 27 33 40 47)
(6 12 20 27 34 40 46)
(6 12 20 27 34 40 47)

在我的代码中,我知道如何访问每个顶点,但如何正确记住和组合完整路径?
use 5.028;
use feature 'signatures';
use strictures;
use Graph qw();

my $g = Graph->new(directed => 1);
for my $edge_tuple (qw(
3-11 6-12 11-17 11-18 11-19 12-20 17-24 18-26 19-27 20-27 24-32 26-33
27-33 27-34 32-39 33-39 33-40 34-40 39-45 40-46 40-47
)) {
my ($from, $to) = split '-', $edge_tuple;
$g->add_edge($from, $to);
}
say join ';', $g->source_vertices;
say join ';', $g->sink_vertices;

sub visit($g, $v, $p) {
push @$p, $v;
if ($g->is_sink_vertex($v)) {
return;
} else {
for my $s ($g->successors($v)) {
visit($g, $s, $p)
}
}
}

my $p = [];
for my $v ($g->source_vertices) {
visit($g, $v, $p);
}
use Data::Dumper; say Dumper $p;

最佳答案

我修改了您的代码以将部分路径传递到 visit()还有visit()从提供的部分路径返回所有可能的完整路径:

sub visit($g, $path) {
my $v = $path->[-1];
if ($g->is_sink_vertex($v)) {
return $path;
} else {
my @more;
for my $s ($g->successors($v)) {
push @more, visit($g, [ @$path, $s ])
}
return @more;
}
}

my @p;
for my $v ($g->source_vertices) {
push @p, visit($g, [$v]);
}
use Data::Dumper; say Dumper @p;

然后可以使用 map 减少循环:
sub visit($g, $path) {
my $v = $path->[-1];
if ($g->is_sink_vertex($v)) {
return $path;
} else {
return map { visit($g, [ @$path, $_ ]) } $g->successors($v);
}
}

my @p = map { visit($g, [$_]) } $g->source_vertices;

关于perl - 如何在有向图中找到从源到汇的所有路径?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52919516/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com