Search the Community

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?