Algoritmo di teoria dei grafi efficiente per gli algoritmi di teoria dei grafi

Question

Ho appena letto sull'algoritmo breadth-first search nel libro Introduzione agli algoritmi e ho simulato manualmente l'algoritmo su carta. Quello che vorrei fare ora è implementarlo in codice per fare pratica extra.

Stavo pensando di implementare tutte le strutture dati da zero (lo adjacency list, gli array "colore", "distanza" e "genitore") ma poi mi sono ricordato che al momento ci sono librerie di grafici come il grafico Boost libreria e qualche altro graph APIs in Python. Ho anche provato a cercare alcuni problemi relativi a BFS su UVA e Sphere Judge Online ma non posso dire quali problemi richiederebbero una soluzione BFS.

La mia domanda è quale sarebbe il modo più indolore per praticare questi algoritmi grafico (non solo limitati a BFS, ma sarà anche venire in utile quando voglio implementare DFS, Dijkstra, Floyd-Warshall, ecc). I siti con problemi di pratica sono i benvenuti.

Answer 1

Personalmente penso che il modo migliore per comprenderli sarebbe implementare la rappresentazione grafica da zero.

Da un lato, ciò mostrerebbe le avvertenze di implementazione effettive da cui si impara perché o perché no un particolare algoritmo potrebbe essere interessante/buono/efficiente/qualunque. D'altra parte, penso che la comprensione dei grafici e il loro uso nella vita reale, comprese le sue implicazioni (ricorsione, prestazioni/scalabilità, applicazioni, alternative, ...), sia resa più facile dall'approccio bottom-up.

Ma forse sono solo io. Quanto sopra è un gusto molto personale.

Answer 2

Ho trovato la tua domanda interessante, ho cercato un po 'su google e ho trovato JGraphEd.

Non copre tutti gli algoritmi del grafico ma sembra un buon strumento per la sperimentazione.

Answer 3

Sono d'accordo con balpha. Il modo migliore per imparare veramente e capire gli algoritmi è quello di fare l'implementazione. Basta scegliere un algoritmo e implementarlo. Quando raggiungi un punto in cui ti trovi bloccato o non sei sicuro, guarda un certo numero di esempi esistenti. Sarai quindi in grado di confrontare il tuo pensiero con quello degli altri da una posizione di comprensione invece di accettare semplicemente ciò che viene offerto.

Una volta che hai imparato ciò che vuoi, il modo migliore per consolidare la tua comprensione è provare a insegnarlo oa descriverlo a qualcun altro. Potresti avere alcune persone disposte ad ascoltarti, o per lo meno potresti scrivere un post di blog per persone nuove all'algoritmo che hai appena studiato.

Ma se siete alla ricerca di "indolore", allora forse si dovrebbe stare alla larga di algoritmi del tutto ;-)

Answer 4

This site could help you

Qui si ha descrizione di ogni problema problemset ACM. Puoi vedere la categoria di ogni problema e suggerire di risolverlo. Basta cercare i problemi relativi al grafico. Un buon consiglio è di usare questi suggerimenti solo se hai provato a risolvere il problema da solo e hai fallito.

Answer 5

visualizzazione di alcuni brevi algoritmi di percorso su dati reali, in cui l'area esplorata è visualizzato in giallo:

• (bidirectional) Dijkstra
• A*