Mi sto preparando all'esame finale di Algorithms e ho una domanda, spero che voi ragazzi potete aiutarmi con.
Dato un grafico non orientato con pesi compresi tra 1 e 100, come posso trovare lo Spanning Spanning Tree minimo in un tempo lineare?
risposte:
0 per risposta № 1Potresti usare L'algoritmo di Kruskal con disgiunti-set e ordina i bordi usando conteggio sort, perché i tuoi pesi sono limitati.