課題:深さ優先探索

gistfile1.pl

#再帰使うべきだったらしい

#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw/min/;

my @list = ([1],[0,2,3],[1,6],[1,4],[3,5],[4,6,7],[2,5,7],[5,6]);
my @already_passed = (0);
my @way = (0);
my $already_flag = 0;
my $deadend_flag = 1;
my $now_point=0;
my $point_quantity = 8;
my @tmp_next_list;
my $return_way = 1;

while(1){ 
  for my $next_point_candidate (@{$list[$now_point]}){
    for (@already_passed){if($next_point_candidate == $_ ){$already_flag = 1 }}
    if($already_flag == 0){push @tmp_next_list, $next_point_candidate; $deadend_flag = 0}
    $already_flag = 0;
  }
  if($deadend_flag == 1){
    $now_point = $way[$#way - $return_way];
    push @way,($now_point);
    $return_way += 2;
  }else{
    push @way , (min @tmp_next_list);
    push @already_passed ,(min @tmp_next_list);
    $now_point = min @tmp_next_list;
    $return_way = 1;
  }
  my %count;
  @already_passed = grep {!$count{$_}++} @already_passed;
  if(($#already_passed + 1 ) >= $point_quantity){last}
  @tmp_next_list = ();
  $deadend_flag = 1;
}

print "経路:";
for(@way){print $_+1,"→"}
print "終了\n";
print "通った点:";
for(sort @already_passed){print $_+1," "}
print "\n存在する点:";
for(0..($point_quantity-1)){print $_+1," "}