I wrote this last year. I hope it helps.
<?php
class KruskalsAlgorithm
{
public function shortest_path( $path_list )
{
$points = array();
$shortest_path = array();
foreach ( $this->sort_2d( $path_list , 2 ) as $path )
{
if ( !in_array( $path[ 0 ] , $points ) || !in_array( $path[ 1 ] , $points ) )
{
$shortest_path[] = $path;
if ( !in_array( $path[ 0 ] , $points ) )
$points[] = $path[ 0 ];
if ( !in_array( $path[ 1 ] , $points ) )
$points[] = $path[ 1 ];
}
}
return $shortest_path;
}
private function sort_2d( $records , $field , $reverse = false )
{
$hash = array();
foreach ( $records as $record )
{
$hash[ $record[ $field ] ] = $record;
}
( $reverse ) ? krsort( $hash ) : ksort( $hash );
$records = array();
foreach ( $hash as $record )
{
$records []= $record;
}
return $records;
}
}
$adjacency_list = array(
array(1,2,5),
array(2,3,4),
array(4,1,2),
array(2,1,5),
array(3,4,3),
array(1,4,2),
array(4,2,1)
);
$pa = new KruskalsAlgorithm();
print_r( $pa->shortest_path( $adjacency_list ) );
?>