perl - 使用至少 K 个节点和给定起始节点的贪婪方法在有向图中查找路径

Question

我有一个非加权 DAG 图。我想做的是找到 贪婪的所有路径并且路径应至少包含 K 个节点， 和给定的起始节点。

是否有任何现有的算法/实现可以做到这一点？

例如我有下图:

my %graph =(36=>[31],31=>[30,22],30=>[20],22=>[20,8],20=>[1],8=>[5],5=>[2],2=>[1,20]);

所以如果我定义K=5，起始节点36，我希望得到:

{1,20,22,31,36}
{1,20,2,5,8,22,31,36}
{1,20,30,31,36}
{1,2,5,8,22,31,36}

Answer 1

这不是很困难。

use warnings;
use strict;
use Data::Dumper;

my @stack = ();

my %graph = (36=>[31],31=>[30,22],30=>[20],22=>[20,8],
             20=>[1],8=>[5],5=>[2],2=>[1,20]);

# add begin to stack
push(@stack, { node => 36, way => [36] });

while (@stack > 0) {

    my $node = pop(@stack);

    # way
    my $way = $node->{way};

    # complete way
    if ($node->{node} == 1) {
        print Dumper($node->{way});
    }

    # add next nodes
    my $nextArr = $graph{$node->{node}};

    for my $nextNod (@$nextArr) {
        # add way
        my @tmpWay = @$way;
        push(@tmpWay, $nextNod);

        # add to stack
        push(@stack, { node => $nextNod, way => \@tmpWay });
    }
}

因此您可以测试，如果节点是结束节点并保存所有路径(方式)。 你必须优化这个脚本

编辑

添加无限保存保护。

编辑2

你不需要无尽的保护。添加 shift 到 pop，然后你搜索不止一种方式来结束笔记 :)