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

发布时间：2020-12-15 22:06:03 所属栏目：大数据来源：网络整理

导读：我想找到从源到汇的所有路径.预期： (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 3

我想找到从源到汇的所有路径.预期：

(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,$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,[$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,$_ ]) } $g->successors($v);
    }
}

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!