Grafi, MST, e algoritmi vari
Salve sto studiando per l'esame di algoritmi e strutture dati e sto guardando i grafi, avrei alcune domande:
1) per calcolare un MST oltre gli algoritmi di Kruskal e Prim posso usare anche DFS, BFS e Dijkstra?
2) funzionano tutti su grafi orientati e non, oppure alcuni hanno delle limitazioni? ad esempio mi pare di aver capito che Kruskal funziona solo su grafi non orientati, e Dijstra solo su grafi con una funzione di peso positiva. Gli altri hanno delle limitazioni?
3) Se ad esempio |v|=|e| quale algoritmo andrebbe meglio per calcolare un MST su un grafo orientato e pesato? BFS e DFS possono essere usati su grafi pesati?
Scusate se son domande forse elementari ma ho questi dubbi che non mi fanno capire bene alcuni esercizi
Grazie mille a chi mi aiuta
1) per calcolare un MST oltre gli algoritmi di Kruskal e Prim posso usare anche DFS, BFS e Dijkstra?
2) funzionano tutti su grafi orientati e non, oppure alcuni hanno delle limitazioni? ad esempio mi pare di aver capito che Kruskal funziona solo su grafi non orientati, e Dijstra solo su grafi con una funzione di peso positiva. Gli altri hanno delle limitazioni?
3) Se ad esempio |v|=|e| quale algoritmo andrebbe meglio per calcolare un MST su un grafo orientato e pesato? BFS e DFS possono essere usati su grafi pesati?
Scusate se son domande forse elementari ma ho questi dubbi che non mi fanno capire bene alcuni esercizi
Grazie mille a chi mi aiuta
Risposte
Vediamo:
1. l'algoritmo di Prim prende lo schema di visita in ampiezza perciò su una BFS, molto informalmente perchè se guardi l'algoritmo di prim, di una BFS a ben poco (v. strutture dati usate)
Questo per dirti, che si può usare un tipo di visita BFS, ma devi comunque scigliere l'arco "migliore" (da difinire) uscente dal nodo. Una DFS la vedo dura, comunque un tipo di risoluzione diversa Prim e Kruskal devi implementarla con una visita, di che tipo sia, sta a te mettere le condizioni sul problema.
Dijkstra risolve il problema dei "cammini minimi".
2. cosa funzionano tutti?
Un grafo orientato può essere trasformato in un grafo non orientato e vice-versa, sta all'algoritmo e al problema stabilie cosa usare.
3. m = archi, n = nodi
Kruskal sei legato alle strutture Merge-Find, e non vedo possiblità di miglioramento sei $O(mlogn)$ se $m=O(n)$ allora $O(nlogn)$ (v. compressione dei percorsi e rango)
Prim puoi migliorare e sciegliere una struttura dati ad-hoc per il tuo problema, se hai il grafo sparso ($m=O(n)$) utilizzi min-heap e la complessità diviene $O(nlogn)$
se hai i grafi densi ($m=Theta(n^2)$) utilizzi le liste di priorità.
se hai dubbi basta chiedere.
PS: ma il caro vecchio Cormen, non c'è più?
1. l'algoritmo di Prim prende lo schema di visita in ampiezza perciò su una BFS, molto informalmente perchè se guardi l'algoritmo di prim, di una BFS a ben poco (v. strutture dati usate)
Questo per dirti, che si può usare un tipo di visita BFS, ma devi comunque scigliere l'arco "migliore" (da difinire) uscente dal nodo. Una DFS la vedo dura, comunque un tipo di risoluzione diversa Prim e Kruskal devi implementarla con una visita, di che tipo sia, sta a te mettere le condizioni sul problema.
Dijkstra risolve il problema dei "cammini minimi".
2. cosa funzionano tutti?
Un grafo orientato può essere trasformato in un grafo non orientato e vice-versa, sta all'algoritmo e al problema stabilie cosa usare.
3. m = archi, n = nodi
Kruskal sei legato alle strutture Merge-Find, e non vedo possiblità di miglioramento sei $O(mlogn)$ se $m=O(n)$ allora $O(nlogn)$ (v. compressione dei percorsi e rango)
Prim puoi migliorare e sciegliere una struttura dati ad-hoc per il tuo problema, se hai il grafo sparso ($m=O(n)$) utilizzi min-heap e la complessità diviene $O(nlogn)$
se hai i grafi densi ($m=Theta(n^2)$) utilizzi le liste di priorità.
se hai dubbi basta chiedere.
PS: ma il caro vecchio Cormen, non c'è più?
Ciao intanto grazie della risposta =)
Cormen non l'abbiamo fatto.. solo gli algoritmi citati sopra..
Io sto provando a capire questo esercizio, se mi dai una mano magari capisco meglio.
Es.
Sia G grafo pesato e orientato, dire quale algoritmo efficiente si può usare per calcolare un MST:
a) tutti gli archi di G pesano k
b) $|E|=|V|$
c) i pesi degli archi sono valgono tra 0 e k con k costante
Allora io ho pensato:
prima cosa, essendo orientato, Kruskal dà qualche problema durante l'uso?
a) se valgono tutti uguali i pesi posso anche non "contarli" e potrei usare una visita tra DFS o BFS, dipende dal grafo, e avrei complessità massima $O(|V|)$
b) qua userei Prim avendo cosi una complessità, come detto da te sopra, $O(nlogn)$
c) qua non saprei proprio cosa usare, mi verrebbe in mente Dijkstra visto che funziona con pesi degli archi positivi (se k è positivo)
Grazie
Cormen non l'abbiamo fatto.. solo gli algoritmi citati sopra..
Io sto provando a capire questo esercizio, se mi dai una mano magari capisco meglio.
Es.
Sia G grafo pesato e orientato, dire quale algoritmo efficiente si può usare per calcolare un MST:
a) tutti gli archi di G pesano k
b) $|E|=|V|$
c) i pesi degli archi sono valgono tra 0 e k con k costante
Allora io ho pensato:
prima cosa, essendo orientato, Kruskal dà qualche problema durante l'uso?
a) se valgono tutti uguali i pesi posso anche non "contarli" e potrei usare una visita tra DFS o BFS, dipende dal grafo, e avrei complessità massima $O(|V|)$
b) qua userei Prim avendo cosi una complessità, come detto da te sopra, $O(nlogn)$
c) qua non saprei proprio cosa usare, mi verrebbe in mente Dijkstra visto che funziona con pesi degli archi positivi (se k è positivo)
Grazie
Cormen è un famoso e molto usato libro di algoritmi.
a) se hai i pesi uguali, non si tratta più di un MST, ma solo di un "albero di copertura" che sia pesato o meno non conta, e che sia minimo men che meno. Perciò utilizzi una BFS (visita in profondità); domanda la complessità allora cosa diviene?
b) ti ho già risposto nel primo post
c) qua bisogna stare un po' attenti se si utlizza Prim, perchè se si hanno pesi a $0$ la struttura dati può portare a qualche errore se non limitato a dovere. Ma comunque vale lo stesso discorso di (b)
Dijkstra risolve il problema dei "cammini minimi" (Shortest Path) e non centra nulla con MST.
Se hai dubbi basta chiedere
PS: strano che ad un corso di algoritmi non venga accennato al libro "Introduzione agli algoritmi e strutture dati" di Cormen & Co., che libro usi o hanno consigliato?
b) ti ho già risposto nel primo post
c) qua bisogna stare un po' attenti se si utlizza Prim, perchè se si hanno pesi a $0$ la struttura dati può portare a qualche errore se non limitato a dovere. Ma comunque vale lo stesso discorso di (b)
Dijkstra risolve il problema dei "cammini minimi" (Shortest Path) e non centra nulla con MST.
Se hai dubbi basta chiedere
PS: strano che ad un corso di algoritmi non venga accennato al libro "Introduzione agli algoritmi e strutture dati" di Cormen & Co., che libro usi o hanno consigliato?
a) ok, la complessità è $ O(|V|+|E|) $ BFS (visita in ampiezza non profondità o sbaglio) giusto? usando le liste chiaramente
b) ok
c) tu cosa useresti quindi?
sisi quel libro è quello che consigliano.. conoscevo il titolo del libro ma non l'autore.. e ce l'avevo ma l'ho prestato e chissa quando me lo tornano
Grazie mille
b) ok
c) tu cosa useresti quindi?
sisi quel libro è quello che consigliano.. conoscevo il titolo del libro ma non l'autore.. e ce l'avevo ma l'ho prestato e chissa quando me lo tornano
Grazie mille
c) a naso qui entra in gioco un counting sort con Kruskal
"eusebi":
c) a naso qui entra in gioco un counting sort con Kruskal
potresti esser più preciso, in quale punto dell'algoritmo ritieni che un ordinamento sia necessario per risolvere il problema in questione?
Kruskal effettua un ordinamento iniziale sulla base del loro peso e poi man mano li estrae. Se i vertici dell'arco appartengono a sottografi differenti fà la union dei due sottografi e così via. La complessità dell'ordinamento sarà normalmente dell'ordine
di O(|E| log |E|) dove E insieme degli archi mentre usando il counting sort in questo caso scende. Resta da considerare il peso delle union.
di O(|E| log |E|) dove E insieme degli archi mentre usando il counting sort in questo caso scende. Resta da considerare il peso delle union.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo