Neorientēts grafs - atrast minimālo šķautnu summu

[snorri]

Ir mājasdarbs (http://susurs.mii.lu.lv/juris/courses/Alg2015/Hw/progr_assign_2015.pdf), kuru pildu izmantojot PHP. Ievaddati tiek ņemti no txt faila

 

šāds ir kods:

function Kruskal(&$G) {
    $len = count($G);
 
    // 1. Make T the empty tree
    $T = array();
 
    // 2. Make a single node trees (sets) out of each vertex
    $S = array();
    foreach (array_keys($G) as $k) {
        $S[$k] = array($k);
    }
 
    // 3. Sort the edges
    $weights = array();
    for ($i = 0; $i < $len; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if (!$G[$i][$j]) continue;
 
            $weights[$i . ' ' . $j] = $G[$i][$j];
        }
    }
    asort($weights);
    $weights = array_reverse($weights);
    var_dump($weights);
    $summa = 0;
    foreach ($weights as $k => $w) {

        list($i, $j) = explode(' ', $k);
 
        $iSet = find_set($S, $i);
        $jSet = find_set($S, $j);
        if ($iSet != $jSet) {
            $summa += $w;
            $T[] = "Edge: ($i, $j)";
            union_sets($S, $iSet, $jSet);
        }
    }
    var_dump($summa);
 
    return $T;
}
 
function find_set(&$set, $index) {
    foreach ($set as $k => $v) {
        if (in_array($index, $v)) {
            return $k;
        }
    }
 
    return false;
}
 
function union_sets(&$set, $i, $j) {
    $a = $set[$i];
    $b = $set[$j];
    unset($set[$i], $set[$j]);
    $set[] = array_merge($a, $b);
}
 
$mst = Kruskal($matrix);

foreach ($mst as $v) {
    echo $v . "<br>";
}

šāds sanāk masīvs ar grafu, kuru padod funkcijai Kruskal:

$G = array(
    0 => array( 0,40,36,0,97,-77,0,81,0,36),
    1 => array( 40,0,0,0,50,41,0,57,69,4),
    2 => array( 36,0,0,26,36,82,55,0,87,0),
    3 => array( 0,0,26,0,14,75,0,61,1,58),
    4 => array( 97,50,36,14,0,2,55,66,15,76),
    5 => array( -77,41,82,75,2,0,0,0,18,0),
    6 => array( 0,0,55,0,55,0,0,0,0,0),
    7 => array( 81,57,0,61,66,0,0,0,0,93),
    8 => array( 0,69,87,1,15,18,0,0,0,99),
    9 => array( 36,4,0,58,76,0,0,93,99,0),
);

Summai vajadzētu būt 615, bet man sanāk 738. Kur varētu būt problēma?

[jurchiks]

Deru, ka kāds tūlīt sāks fleimot par to, ka noteikumi neatļauj izmantot funkcionālās valodas.

[php newbie]

Atnāks codez un uzrakstīs risinājumu scalā 1 rindiņā kuru neviens nesapratīs.

Man pirmais kas iekrita acīs ir ieejas dati. Kā no tā ieejas masīva $G atšķirt vai šķautne neeksistē, vai eksistē ar svaru 0? 

[spainis]

https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm