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

[snorri123]

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?

[Guest]

Vajag klausīties ko pasniedzējs stāsta, vai arī iet ar lāpstu pa grāvjiem darboties...

[MarisO]

Pūku uztrauc tas, ka reizēm dodoties pastaigāties viņš aizmirst paņemt līdz medus podiņu, ar ko ceļā iestiprināties,

 

 

vai tad ir veselīgi tik daudz ēst medu?   cukurs tomēr lielos daudzumos nav labi.

Labots Janvāris 26, 2016 - MarisO

[japets]

Pats nav daudz ko darījis algoritma labā, ņemts no:

http://www.stoimen.com/blog/2012/11/12/computer-algorithms-kruskals-minimum-spanning-tree/

[Anonīms Alkoholiķis]

Lai iemācās taisīt debug output'u, uzzināt kas ir atkļūdošana un pašam saprast kur ir problēma. Savādāk būs kārtējais caurkritušais mūžīgais 1-kursa students datorikas fakultātē.