Ciao a tutti, sto cercando di implementare l’algoritmo di Kurskal per il calcolo del Minimum Spanning Tree di un grafo non orientato, come soluzione al problema “mst”. Ora, il procedimento dovrebbe essere giusto, almeno secondo i pochi casi di esempio che ho testato, ma ovviamente il sistema mi dice che azzecco solo il risultato dell’esempio e il successivo. Qualcuno sa dirmi dove sbaglio?
Grazie!
L’errore chiave è alla riga 90. Scegli di controllare solo un arco ogni due, presuppongo per evitare di controllare sia (u,v) che (v,u).
Tuttavia, dopo aver ordinato gli archi, questa proprietà (ovvero che se edges[i] rappresenta (u,v) allora edges[i+1] rappresenta (v,u)) può venire meno.
Questa correzione rende l’algoritmo formalmente corretto; per il massimo dei punti serve ridurre la complessità computazionale.
Al di là di ciò, osserva anche che 2^{42} supera il massimo rappresentabile con int.
1 Mi Piace
Grazie, purtroppo nei grafi che ho usato come test non si presentava mai questo problema e quindi non avevo proprio pensato che fosse per quel motivo.
EDIT: Anche io pensavo che 2^{42} superasse il massimo rappresentabile con un int, però il sistema non ha dato problemi di overflow. 
Mmm, in effetti ho guardato il generatore e il massimo peso che viene usato è 1000 invece di 2^{42}. Il testo rimane tecnicamente corretto (quindi non è necessario cambiare i testcase e rivalutare).
Volendo, comunque, puoi testare manualmente qualche input che causa overflow:
3 3
1 2 1000000000000
2 3 1000000000001
3 1 1000000000000
1 Mi Piace