prim最小生成树

以下代码由PHP站长网 52php.cn收集自互联网

现在PHP站长网小编把它分享给大家，仅供参考

#! /usr/bin/perl -w

use strict;

my $filepath = "input3";
my @matrix = ();
my $count;
my $max = 1000;

#read file from path
sub readfile{
	open(FD,$filepath) or die "$filepath not exitst!";
	foreach my $line (<FD>){
		my @keys = split(";",$line);
		my @path = ();
		foreach my $key (@keys){
			push(@path,$key);
		}
		push(@matrix,@path);
	}
}

#change file from 0 to 1000
sub getpath{
	readfile;
	$count = $#matrix + 1;
	for ( my $i = 0 ; $i < $count ; $i++){
		for ( my $j = 0; $j < $count ; $j++){
			if ( $i != $j && $matrix[$i][$j] == 0 ){
				$matrix[$i][$j] = $max;
			}
		}
	}
}

sub prim{
	getpath;
	my $startnode = shift;#select where to start
	my @dist = (); #select the min path
	my @mark = (); #mark whether it has been accessed
	my @path = (); #store the path
	my $sum = 0; #store the sum length

#init the first node
	for ( my $i = 0; $i < $count; $i++){
		$dist[$i] = $matrix[$startnode][$i];
	}

	$mark[$startnode] = 0;
	push(@path,"$startnode");

    #start to add node
	for ( my $j = 1; $j < $count; $j++){
        #select the min node
		my $min = $max;
		my $location = -1;	
		for ( my $i = 0; $i < $count; $i++){
			print "       the $j dist is $dist[$i]n";
		}

		for ( my $i = 1; $i < $count; $i++){
			if( !defined($mark[$i]) and $dist[$i] < $min){
				$location = $i;
				$min = $dist[$i];
			}
		}

        push(@path," --> $location");
		$mark[$location] = 0;
		$sum = $sum + $dist[$location];

		#print " $j get location $location min $min n";
		#print "############################################n";

        #update the dist
		for ( my $i = 1; $i < $count; $i++){
			if ( !defined($mark[$i]) and $matrix[$location][$i] < $dist[$i] ){
				$dist[$i] = $matrix[$location][$i];
			}
		}
	}

	print "the shortest path sum is: $sumn";
	for ( my $i = 0; $i < $count; $i++){
		print "from $i has $path[$i] ";
		print "       the dist is $dist[$i]n";
	}
}


prim(1);

以上内容由PHP站长网【52php.cn】收集整理供大家参考研究

如果以上内容对您有帮助，欢迎收藏、点赞、推荐、分享。

（编辑：李大同）

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