欧拉路径,有向图

Question

晚上好.我真的是初学者,我正在努力实现欧拉路径.这意味着有向图的每个边(不是顶点)只能使用一次.出于某种原因,即使在纸上,它也无法覆盖所有顶点.它似乎忽略了一半的顶点或者根本没有将它们添加到电路中.

预期结果是:

6->7->8->9->6->3->0->2->1->3->4

不过,我得到的结果是:

6 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 9 9 9 9 9 9 9 3 3 3 3 3 3

我所拥有的代码如下:

my %edges={'6'=>['3','7'],'8'=>['9'],'1'=>['3'],'0'=>['2'],'3'=>['0','4'], '7' =>['8'],'9'=>['6'],'2'=>['1']}; 


    my $startvertex=6; #this i got from additional code
    my $location=$startvertex;
    my @stack = ($startvertex);
    my @circuit  = ();

        while (@stack)
        {
            if (@{$edges{$location}}[0])
                {
                    push @stack, $location;
                    my $newlocation=@{$edges{$location}}[0];
                    splice @{$edges{$location}},0,1;
                    $location=$newlocation;

                }
            else
                {
                push @circuit, $location;
                $location=pop @stack;
                } 

        }   

my @revcircuit= reverse @circuit;
print @revcircuit;

非常感谢您的见解.

Answer 1

问题出在这里:

if (@{$edges{$location}}[0])

调用0其中一个节点,在Perl中为false.因此,一旦到达零节点,程序就会继续,就像没有更多节点一样.改为使用定义.

这是一个工作版本,略有编辑(例如删除不必要的数组解除引用):

#!/usr/bin/perl
use warnings;
use strict;

my %edges = ( 6 => [3, 7],
              8 => [9],
              1 => [3],
              0 => [2],
              3 => [0, 4],
              7 => [8],
              9 => [6],
              2 => [1]);

my $startvertex = 6;

my $location = $startvertex;
my @stack = ($startvertex);
my @circuit;

while (@stack) {
    if (defined $edges{$location}[0]) {
        push @stack, $location;
        $location = shift @{ $edges{$location} };
    } else {
        push @circuit, $location;
        $location = pop @stack;
    }
}
my @revcircuit = reverse @circuit;
print "@revcircuit\n";

另请注意,它使用圆括号来定义%edges哈希.Curly braces引入了哈希引用,我得到了它们

Reference found where even-sized list expected at ./1.pl line 5.