prim最小生成树

oldmonst

1. #! /usr/bin/perl -w
   
2. 
   
3. use strict;
   
4. 
   
5. my $filepath = "input3";
   
6. my @matrix = ();
   
7. my $count;
   
8. my $max = 1000;
   
9. 
   
10. #read file from path
    
11. sub readfile{
    
12.         open(FD,$filepath) or die "$filepath not exitst!";
    
13.         foreach my $line (<FD>){
    
14.                 my @keys = split(";",$line);
    
15.                 my @path = ();
    
16.                 foreach my $key (@keys){
    
17.                         push(@path, $key);
    
18.                 }
    
19.                 push(@matrix,\@path);
    
20.         }
    
21. }
    
22. 
    
23. #change file from 0 to 1000
    
24. sub getpath{
    
25.         readfile;
    
26.         $count = $#matrix + 1;
    
27.         for ( my $i = 0 ; $i < $count ; $i++){
    
28.                 for ( my $j = 0; $j < $count ; $j++){
    
29.                         if ( $i != $j && $matrix[$i][$j] == 0 ){
    
30.                                 $matrix[$i][$j] = $max;
    
31.                         }
    
32.                 }
    
33.         }
    
34. }
    
35. 
    
36. sub prim{
    
37.         getpath;
    
38.         my $startnode = shift;#select where to start
    
39.         my @dist = (); #select the min path
    
40.         my @mark = (); #mark whether it has been accessed
    
41.         my @path = (); #store the path
    
42.         my $sum = 0; #store the sum length
    
43. 
    
44. #init the first node
    
45.         for ( my $i = 0; $i < $count; $i++){
    
46.                 $dist[$i] = $matrix[$startnode][$i];
    
47.         }
    
48. 
    
49.         $mark[$startnode] = 0;
    
50.         push(@path, "$startnode");
    
51. 
    
52.     #start to add node
    
53.         for ( my $j = 1; $j < $count; $j++){
    
54.         #select the min node
    
55.                 my $min = $max;
    
56.                 my $location = -1;       
    
57.                 for ( my $i = 0; $i < $count; $i++){
    
58.                         print "       the $j dist is $dist[$i]\n";
    
59.                 }
    
60. 
    
61.                 for ( my $i = 1; $i < $count; $i++){
    
62.                         if( !defined($mark[$i]) and $dist[$i] < $min){
    
63.                                 $location = $i;
    
64.                                 $min = $dist[$i];
    
65.                         }
    
66.                 }
    
67. 
    
68.         push(@path, " --> $location");
    
69.                 $mark[$location] = 0;
    
70.                 $sum = $sum + $dist[$location];
    
71. 
    
72.                 #print " $j get location $location min $min \n";
    
73.                 #print "############################################\n";
    
74. 
    
75.         #update the dist
    
76.                 for ( my $i = 1; $i < $count; $i++){
    
77.                         if ( !defined($mark[$i]) and $matrix[$location][$i] < $dist[$i] ){
    
78.                                 $dist[$i] = $matrix[$location][$i];
    
79.                         }
    
80.                 }
    
81.         }
    
82. 
    
83.         print "the shortest path sum is: $sum\n";
    
84.         for ( my $i = 0; $i < $count; $i++){
    
85.                 print "from $i has $path[$i] ";
    
86.                 print "       the dist is $dist[$i]\n";
    
87.         }
    
88. }
    
89. 
    
90. 
    
91. prim(1);

复制代码