如何在有向图中查找从源节点到汇节点的所有路径？

Question

我想要找出所有从起点到终点的路径。期望结果:

(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;

- daxim

---

我对Perl并不是特别熟悉，但是你在$p中已经有路径了，不是吗？在visit函数的返回语句之前（if ($g->is_sink_vertex($v)) { return; }），你应该能够将$p简单地添加到一个全局变量中，该变量随后保存所有路径。 - Johan

您可能还想查看 https://metacpan.org/pod/GraphViz2::Marpa::PathUtils - Jeffrey Kegler

Answer 1

我修改了您的代码，将部分路径传递给 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;

- Grant McLean