Fra Vicious
23-12-2012, 18:42
Salve a tutti, vengo subito al problema, può sembrare banale ma ci sto sbattendo la testa da un paio di giorni, sapendo che devo calcolare un minimo albero ricoprente (e quindi la mia rappresentazione deve adattarsi a questo problema), ho in input una serie di casi test del tipo:
N (un intero positivo che rappresenta gli archi del grafo)
X - Y distanza
Y - Z distanza
X - Z distanza
non mi viene in mente niente per rappresentare in maniera efficiente questo tipo di input, anche perché non so di preciso quanti vertici potrò avere, essendo il grafo connesso con N archi posso teoricamente avere da N+1 a N*2 vertici (correggetemi se dico qualche cazzata). Il problema che mi affligge di più è: preso un vertice X dall'input controllare se è già presente nella mia rappresentazione, contando che N può arrivare fino a 1.000.000, può rilevarsi molto costoso se non implementato efficientemente...
Sostanzialmente data una lista di archi - non sapendo quanti vertici avrò di preciso - devo costruire una struttura che mi consenta di poter poi applicare in maniera furba kruskal o prim (sto ancora valutando vantaggi/svantaggi)...
Mi affido a voi per qualche suggerimento...
N (un intero positivo che rappresenta gli archi del grafo)
X - Y distanza
Y - Z distanza
X - Z distanza
non mi viene in mente niente per rappresentare in maniera efficiente questo tipo di input, anche perché non so di preciso quanti vertici potrò avere, essendo il grafo connesso con N archi posso teoricamente avere da N+1 a N*2 vertici (correggetemi se dico qualche cazzata). Il problema che mi affligge di più è: preso un vertice X dall'input controllare se è già presente nella mia rappresentazione, contando che N può arrivare fino a 1.000.000, può rilevarsi molto costoso se non implementato efficientemente...
Sostanzialmente data una lista di archi - non sapendo quanti vertici avrò di preciso - devo costruire una struttura che mi consenta di poter poi applicare in maniera furba kruskal o prim (sto ancora valutando vantaggi/svantaggi)...
Mi affido a voi per qualche suggerimento...